Explaining Your Approach and Its Cost Out Loud

28 min · Intermediate

A coding interview scores how you think as much as the final code. This lesson gives you a fixed order to speak in, plain words for time and space, and the hidden costs of Python calls that interviewers listen for. To practise it, use the Python DSA 150 sheet at /learn/python/dsa-sheet.

Say your plan before you type

A think-aloud routine is a fixed order of spoken steps in a coding interview: restate, example, brute force, better idea, code, test, cost. It lets the interviewer follow and correct you early.

An interviewer cannot see your thoughts, so say them. A fixed order keeps you calm and shows how you think.

The order is: restate the problem, try one small example, say the slow way, find the repeated work, code the better way, then test it aloud. Revise: Brute force to better solutions (opens in a new tab)

Restate the input and output in your own words, and ask about empty input, duplicates and negative numbers.
Say the brute force with its cost first. It proves you can solve it, even if slowly.
Name the repeated work, then pick the tool that removes it: a set, a dict, sorting, two pointers or a heap.
Finish with one dry run on a small input, then state time and space.

Say time and space in plain words

Time cost is how the number of steps grows as the input size n grows. Space cost is how much extra memory you use beyond the input. Both are stated in Big O, such as O(n) or O(n log n).

Say what n means, then how the work grows with n. Then say how much extra memory you keep.

Python

1def has_duplicate(items):2    seen = set()           # extra memory: up to n items3    for item in items:     # one pass: n steps4        if item in seen:   # set lookup: one step on average5            return True6        seen.add(item)7    return False

Example 1 · Two sum, said aloud: brute force then dict

Python

1def two_sum_brute(nums, target):2    # Brute force: try every pair. O(n^2) time, O(1) space.3    for i in range(len(nums)):4        for j in range(i + 1, len(nums)):5            if nums[i] + nums[j] == target:6                return [i, j]7    return []8
9
10def two_sum(nums, target):11    # Repeated work: searching for the partner. A dict makes it O(1).12    seen = {}  # value -> index; O(n) space13    for i, value in enumerate(nums):14        if target - value in seen:15            return [seen[target - value], i]16        seen[value] = i17    return []18
19
20print(two_sum_brute([8, 3, 11, 5], 14))21print(two_sum([8, 3, 11, 5], 14))22print(two_sum([1, 2], 10))

Output

[1, 2]
[1, 2]
[]

What this code does

The comments are the sentences you would say. The brute force tries every pair, the dict version remembers each value and looks for its partner.
The dict version is one pass: O(n) time and O(n) space. Always test the no-answer case too.

Say it like this: "One pass over n items, and each set lookup is constant on average, so O(n) time. The set can hold n items, so O(n) space."

If asked for less memory, say that sorting first gives O(n log n) time with little extra space.

Know what Python operations really cost

A hidden cost is work done inside a single line of Python, such as a slice that copies a list or an in test that scans every item. Say it aloud so the interviewer knows you counted it.

Interviewers listen for the cost of the library calls you use. A one-line Python call can hide a loop. Revise: The real cost of Python operations (opens in a new tab)

x in some_list scans the list, O(n). x in some_set or a dict is O(1) on average.
a[1:] makes a copy, O(k) for k items. list.pop(0) and list.insert(0, x) shift every item, O(n); use collections.deque.
text += ch in a loop can be O(n squared) in the worst case; collect pieces in a list and call ''.join(pieces).
sorted(items) is O(n log n) time and O(n) space; items.sort() sorts in place but is still O(n log n) time.

Example 2 · The hidden cost of slicing in binary search

Python

1def search_slice(items, target):2    copied = 03    base = 04    while items:5        mid = len(items) // 26        if items[mid] == target:7            return base + mid, copied8        if items[mid] < target:9            items = items[mid + 1:]10            base += mid + 111        else:12            items = items[:mid]13        copied += len(items)14    return -1, copied15
16
17def search_index(items, target):18    low, high = 0, len(items) - 119    while low <= high:20        mid = (low + high) // 221        if items[mid] == target:22            return mid23        if items[mid] < target:24            low = mid + 125        else:26            high = mid - 127    return -128
29
30data = list(range(0, 2000, 2))31print(search_slice(data, 1998))32print(search_index(data, 1998))

Output

(999, 985)
999

What this code does

Both find index 999. The slicing version also reports how many items it copied on the way, so its real cost is far above O(log n).
Moving two indexes costs nothing extra. In an interview, prefer indexes and say why.

Example 3 · Use a deque when you remove from the front

Python

1from collections import deque2
3queue = deque(["t1", "t2", "t3"])   # support tickets waiting4queue.append("t4")5print(queue.popleft())   # O(1); list.pop(0) would be O(n)6print(queue.popleft())7print(list(queue))

Output

t1
t2
['t3', 't4']

What this code does

popleft removes from the front in O(1). A list would shift every remaining item.
Say "I use a deque because I remove from the front". It is a small sentence that shows you know the cost.

Average, worst case and amortised

Amortised cost is the average cost per operation over a long run of operations, even when a single operation is sometimes expensive. List append is O(1) amortised.

Say which case you mean. A dict lookup is O(1) on average but can degrade in a very unlucky case. Appending to a list is O(1) amortised: most appends are cheap and an occasional resize is costly, but the average per append stays constant.

Example 4 · Recursion depth is space, and Python has a limit

Python

1def total_recursive(n):2    if n == 0:3        return 04    return n + total_recursive(n - 1)5
6
7def total_loop(n):8    result = 09    for value in range(1, n + 1):10        result += value11    return result12
13
14try:15    print(total_recursive(5000))16except RecursionError:17    print("recursion too deep")18print(total_loop(5000))

Output

recursion too deep
12502500

What this code does

Each recursive call keeps a frame on the call stack, so this uses O(n) space. CPython stops at about 1000 frames by default.
The loop uses O(1) space. For deep input, say you would convert the recursion to a loop or an explicit stack.

Next step

Check your understanding

12 quick questions

Say your plan before you type

A think-aloud routine is a fixed order of spoken steps in a coding interview: restate, example, brute force, better idea, code, test, cost. It lets the interviewer follow and correct you early.

An interviewer cannot see your thoughts, so say them. A fixed order keeps you calm and shows how you think.

The order is: restate the problem, try one small example, say the slow way, find the repeated work, code the better way, then test it aloud. Revise: Brute force to better solutions

1def has_duplicate(items):2 seen = set() # extra memory: up to n items3 for item in items: # one pass: n steps4 if item in seen: # set lookup: one step on average5 return True6 seen.add(item)7 return False

1def two_sum_brute(nums, target):2 # Brute force: try every pair. O(n^2) time, O(1) space.3 for i in range(len(nums)):4 for j in range(i + 1, len(nums)):5 if nums[i] + nums[j] == target:6 return [i, j]7 return []8 9 10def two_sum(nums, target):11 # Repeated work: searching for the partner. A dict makes it O(1).12 seen = {} # value -> index; O(n) space13 for i, value in enumerate(nums):14 if target - value in seen:15 return [seen[target - value], i]16 seen[value] = i17 return []18 19 20print(two_sum_brute([8, 3, 11, 5], 14))21print(two_sum([8, 3, 11, 5], 14))22print(two_sum([1, 2], 10))

Know what Python operations really cost

A hidden cost is work done inside a single line of Python, such as a slice that copies a list or an in test that scans every item. Say it aloud so the interviewer knows you counted it.

Interviewers listen for the cost of the library calls you use. A one-line Python call can hide a loop. Revise: The real cost of Python operations

1def search_slice(items, target):2 copied = 03 base = 04 while items:5 mid = len(items) // 26 if items[mid] == target:7 return base + mid, copied8 if items[mid] < target:9 items = items[mid + 1:]10 base += mid + 111 else:12 items = items[:mid]13 copied += len(items)14 return -1, copied15 16 17def search_index(items, target):18 low, high = 0, len(items) - 119 while low <= high:20 mid = (low + high) // 221 if items[mid] == target:22 return mid23 if items[mid] < target:24 low = mid + 125 else:26 high = mid - 127 return -128 29 30data = list(range(0, 2000, 2))31print(search_slice(data, 1998))32print(search_index(data, 1998))

1from collections import deque2 3queue = deque(["t1", "t2", "t3"]) # support tickets waiting4queue.append("t4")5print(queue.popleft()) # O(1); list.pop(0) would be O(n)6print(queue.popleft())7print(list(queue))

Average, worst case and amortised

Amortised cost is the average cost per operation over a long run of operations, even when a single operation is sometimes expensive. List append is O(1) amortised.

1def total_recursive(n):2 if n == 0:3 return 04 return n + total_recursive(n - 1)5 6 7def total_loop(n):8 result = 09 for value in range(1, n + 1):10 result += value11 return result12 13 14try:15 print(total_recursive(5000))16except RecursionError:17 print("recursion too deep")18print(total_loop(5000))