Python · Lesson 12
Interview Patterns in Python
The coding-interview patterns written the Python way (hash maps, two pointers, sliding windows, prefix sums, stacks, BFS and DFS, binary search, heaps, intervals and dynamic programming), what each costs, how to recognise it, and how to talk through a solution.
In short
- Know the costs:
pop(0)andx in listare O(n) - Dicts and Counters replace inner search loops
- Windows and two pointers only move forward
- BFS with
deque; DFS with your own stack when deep - Heaps,
bisect, sort-then-sweep,@cacheand tables - Talk it through: brute force, bottleneck, pattern, cost
Most coding-interview questions are one of about a dozen patterns in disguise. Once you can name the
pattern, the solution is mostly known, and what's left is writing it cleanly and explaining what it costs.
Python is the best language for this: dict, Counter, deque, heapq, bisect and functools.cache
are each one import away, and the code stays short enough to say out loud.
This topic assumes you know the patterns from JavaScript, TypeScript or C# at least a little, and shows the idiomatic Python for each one, with its complexity and a "how to recognise it" line. It starts with what Python's built-ins cost, because an O(n) operation hiding inside a loop is the most common way a correct Python answer turns out O(n²).
Every snippet has a ▶ Try button. Predict the output first, then run it.
What Python's built-ins cost
Interviewers expect you to know these. "Average" means with a reasonable hash function, which is what you always get for ints, strings and tuples.
| Operation | Cost | Notes |
|---|---|---|
xs.append(x), xs.pop() | O(1) amortised | The end of a list is cheap |
xs[i], xs[i] = x, len(xs) | O(1) | A list is a dynamic array, like List<T> or a JS array |
xs.pop(0), xs.insert(0, x) | O(n) | Shifts every other element; use deque |
x in xs, xs.index(x), xs.count(x), xs.remove(x) | O(n) | A linear scan |
xs[a:b], xs.copy(), xs + ys | O(k) | Slicing and concatenation copy |
x in s, s.add(x) for a set | O(1) average | Hash lookup |
d[k], d[k] = v, k in d, del d[k] | O(1) average | Hash lookup; k in d checks keys |
dq.append, dq.appendleft, dq.pop, dq.popleft | O(1) | collections.deque |
heapq.heappush, heapq.heappop | O(log n) | h[0] peeks the smallest in O(1) |
heapq.heapify(xs) | O(n) | Faster than n pushes |
sorted(xs), xs.sort() | O(n log n) | Stable (Timsort); sort is in place |
bisect.bisect_left(xs, x) | O(log n) | insort is O(n): it still shifts elements |
min(xs), max(xs), sum(xs) | O(n) | Each one is a full pass |
s += t in a loop, for strings | O(n²) total | Strings are immutable; collect parts and "".join once |
Two of these cause most surprises. pop(0) on a list looks like a queue but shifts every element, and in
on a list looks like a set lookup but scans:
from collections import deque
queue = [1, 2, 3]
first = queue.pop(0) # O(n): moves 2 and 3 one slot left
dq = deque([1, 2, 3])
also_first = dq.popleft() # O(1)
print(first, also_first, queue, list(dq))
banned = ["spam", "scam", "phish"]
banned_set = set(banned) # build once: O(n)
print("scam" in banned, "scam" in banned_set) # O(n) scan vs O(1) hash lookup
Building a string with += in a loop can copy the whole string each time. Collect the pieces in a list and
join once:
parts = []
for i in range(5):
parts.append(str(i))
print("-".join(parts))
print(",".join(f"{n * n}" for n in range(4)))
(CPython sometimes optimises s += t in place, but only sometimes. Don't rely on it in an interview.)
Hash maps: counting and lookups
Recognise it: "have I seen this before?", "how many of each?", "find a pair that...", or any time a nested loop is searching for something. Trading O(n) memory for O(1) lookups is the most common optimisation there is.
Cost: O(n) time and O(n) space for one pass.
Two-sum in one pass: for each number, look up the partner you need, then remember the number.
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
seen: dict[int, int] = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen:
return (seen[target - n], i)
seen[n] = i
return None
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 3], 6))
print(two_sum([1, 2], 7))
collections.Counter counts in one line, and defaultdict groups without "is the key there yet?" checks:
from collections import Counter, defaultdict
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(Counter("mississippi").most_common(2))
groups: defaultdict[str, list[str]] = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w) # anagrams share a sorted key
print(list(groups.values()))
print(Counter("listen") == Counter("silent"))
most_common breaks ties by first appearance, which is why i comes before s (both appear 4 times).
Dicts keep insertion order, so groups.values() comes out in the order each group was first seen.
Two pointers
Recognise it: a sorted array and a pair or triple with some sum; reversing or checking a palindrome in place; merging two sorted lists; removing duplicates in place. Two indexes walk towards each other (or in the same direction) and each step rules out part of the input.
Cost: O(n) time, O(1) extra space (plus O(n log n) if you have to sort first).
def pair_with_sum(sorted_nums: list[int], target: int) -> tuple[int, int] | None:
lo, hi = 0, len(sorted_nums) - 1
while lo < hi:
total = sorted_nums[lo] + sorted_nums[hi]
if total == target:
return (sorted_nums[lo], sorted_nums[hi])
if total < target:
lo += 1 # need more: the smallest value can't be in any pair
else:
hi -= 1 # need less: the largest value can't be in any pair
return None
def is_palindrome(s: str) -> bool:
chars = [c.lower() for c in s if c.isalnum()]
return chars == chars[::-1]
print(pair_with_sum([1, 3, 4, 6, 9], 10))
print(pair_with_sum([1, 2, 3], 100))
print(is_palindrome("A man, a plan, a canal: Panama"))
chars[::-1] builds a reversed copy, which is O(n) space. When the interviewer asks for O(1) space, compare
s[lo] with s[hi] and move the pointers inward instead.
Sliding window
Recognise it: "contiguous subarray" or "substring" plus "longest", "shortest", "maximum sum" or "at most k".
A window [start, end] slides along the input, and you update a running total or count as elements enter and
leave, instead of recomputing it.
Cost: O(n) time; O(1) space for a running sum, O(k) for a dict of counts.
A fixed window adds the new element and removes the one that fell out:
def max_window_sum(nums: list[int], k: int) -> int:
window = sum(nums[:k])
best = window
for end in range(k, len(nums)):
window += nums[end] - nums[end - k]
best = max(best, window)
return best
print(max_window_sum([2, 1, 5, 1, 3, 2], 3))
A variable window grows at end and shrinks from start while it breaks a rule. Here: the longest
substring with at most k distinct characters.
from collections import Counter
def longest_with_k_distinct(s: str, k: int) -> int:
counts: Counter[str] = Counter()
start = best = 0
for end, ch in enumerate(s):
counts[ch] += 1
while len(counts) > k: # too many distinct: shrink from the left
counts[s[start]] -= 1
if counts[s[start]] == 0:
del counts[s[start]]
start += 1
best = max(best, end - start + 1)
return best
print(longest_with_k_distinct("eceba", 2))
print(longest_with_k_distinct("aabbcc", 1))
It's O(n) even with the inner while: start only moves forward, so across the whole run it moves at most
n times. Note the del: a Counter keeps keys whose count drops to zero, and len(counts) would count them.
Prefix sums
Recognise it: many "sum of the range i to j" questions on data that doesn't change, or "how many
subarrays sum to k" (especially with negative numbers, where a sliding window doesn't work).
Cost: O(n) to build, then O(1) per range query.
prefix[i] is the sum of the first i elements, so the sum of nums[i:j] is prefix[j] - prefix[i].
itertools.accumulate builds it:
from collections import Counter
from itertools import accumulate
nums = [3, -1, 4, 1, -5, 9]
prefix = [0, *accumulate(nums)]
print(prefix)
print(prefix[4] - prefix[1]) # sum of nums[1:4] = -1 + 4 + 1
def count_subarrays_with_sum(nums: list[int], k: int) -> int:
seen = Counter({0: 1}) # the empty prefix
total = count = 0
for n in nums:
total += n
count += seen[total - k] # earlier prefixes that leave exactly k
seen[total] += 1
return count
print(count_subarrays_with_sum([1, 1, 1], 2))
print(count_subarrays_with_sum([3, 4, -7, 3, 1, 3, 1, -4], 7))
The second function is two-sum again, run on prefix sums: a subarray sums to k when two prefixes differ by k.
Stacks
Recognise it: matching pairs (brackets, tags), undo, evaluating expressions, "the most recent unmatched
thing", and "the next greater/smaller element" (a monotonic stack). A Python list is the stack:
append pushes, pop pops, stack[-1] peeks, all O(1).
Cost: O(n) time, O(n) space.
def balanced(text: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack # anything left open is unbalanced
for t in ["f(a[1], {b: 2})", "(]", "((", ""]:
print(repr(t), balanced(t))
A monotonic stack keeps its elements in sorted order by popping everything a new element beats. Each element is pushed and popped at most once, so the nested loop is still O(n) overall. Next greater element:
def next_greater(nums: list[int]) -> list[int]:
result = [-1] * len(nums)
stack: list[int] = [] # indexes waiting for a greater value
for i, n in enumerate(nums):
while stack and nums[stack[-1]] < n:
result[stack.pop()] = n
stack.append(i)
return result
print(next_greater([2, 1, 2, 4, 3]))
Queues and BFS
Recognise it: "shortest path", "fewest steps", "minimum moves" when every step costs the same; anything "level by level" (a tree's levels, degrees of separation); spreading from several sources at once (rotting oranges, distance to the nearest exit). BFS visits nodes in order of distance, so the first time it reaches a node is the shortest way there.
Cost: O(V + E) time and O(V) space; on a grid, O(rows × cols).
Use collections.deque as the queue. Mark a node as seen when you enqueue it, so nothing is queued twice.
On a graph stored as an adjacency dict:
from collections import deque
graph = {
"ann": ["bob", "cat"],
"bob": ["dan"],
"cat": ["dan", "eve"],
"dan": ["fay"],
"eve": [],
"fay": [],
}
def hops(start: str) -> dict[str, int]:
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
print(hops("ann"))
On a grid, the neighbours are the four squares around you, inside the bounds and not blocked:
from collections import deque
def steps_to_exit(grid: list[str]) -> int:
rows, cols = len(grid), len(grid[0])
dist = {(0, 0): 0}
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
if (r, c) == (rows - 1, cols - 1):
return dist[(r, c)]
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
queue.append((nr, nc))
return -1
print(steps_to_exit(["..#",
"#..",
"#.."]))
print(steps_to_exit([".#",
"#."]))
Check the bounds before indexing: grid[-1] doesn't raise in Python, it quietly reads the last row.
DFS and recursion
Recognise it: "explore everything reachable" (count islands, connected components, flood fill), "all paths / all combinations / all subsets" (backtracking), tree problems (depth, path sums), cycle detection and topological order. DFS goes deep first; it does not find shortest paths.
Cost: O(V + E) time; O(V) space for seen, plus the recursion depth.
Recursive DFS is the shortest to write. Counting islands on a grid:
def count_islands(grid: list[str]) -> int:
rows, cols = len(grid), len(grid[0])
seen: set[tuple[int, int]] = set()
def sink(r: int, c: int) -> None:
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "#" or (r, c) in seen:
return
seen.add((r, c))
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
sink(nr, nc)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "#" and (r, c) not in seen:
islands += 1
sink(r, c)
return islands
print(count_islands(["##..",
"#..#",
"..##",
"#..."]))
The caveat: Python has no tail-call optimisation and a recursion limit of about 1,000 frames. A path,
a linked list or a degenerate tree a few thousand nodes deep raises RecursionError:
def depth(n: int) -> int:
return 0 if n == 0 else 1 + depth(n - 1)
print(depth(500))
try:
depth(5000)
except RecursionError as e:
print("RecursionError:", e)
sys.setrecursionlimit raises the limit, and since Python 3.11 plain Python recursion no longer uses the C
stack, so that often works. But each frame costs memory, and recursion that goes through C code (a @cache
wrapper, a key= function) still stops at a separate C limit. The safer answer is an explicit stack,
which turns recursion into a loop that reaches the same nodes (not always in the same order):
def reachable(graph: dict[int, list[int]], start: int) -> list[int]:
seen = {start}
order = []
stack = [start]
while stack:
node = stack.pop()
order.append(node)
for nxt in reversed(graph[node]): # reversed: visit neighbours in listed order
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return order
chain = {i: [i + 1] for i in range(100_000)}
chain[100_000] = []
print(len(reachable(chain, 0)))
print(reachable({1: [2, 3], 2: [4], 3: [], 4: []}, 1))
Swap the stack for a deque with popleft and the same loop is BFS. In an interview, write recursive DFS
when the depth is small (balanced trees, small grids) and mention the iterative version when it isn't.
Binary search
Recognise it: a sorted input and "find", "first", "last", "insert position" or "count in a range"; or, less obviously, "the minimum X such that something works" where bigger X always works if smaller X does. That second form is binary search on the answer.
Cost: O(log n) per search; O(f · log range) for search on the answer, where f is the cost of one check.
Don't hand-write the classic version: bisect does it, without off-by-one bugs. bisect_left returns the
first index where x could go (before equal elements), bisect_right the last (after them):
from bisect import bisect_left, bisect_right
scores = [10, 20, 20, 20, 35, 50]
print(bisect_left(scores, 20), bisect_right(scores, 20))
print(bisect_right(scores, 20) - bisect_left(scores, 20)) # how many 20s
i = bisect_left(scores, 36)
print(i, i < len(scores) and scores[i] == 36) # where 36 would go; not present
print(bisect_right(scores, 30) - bisect_left(scores, 15)) # count in [15, 30]
Search on the answer: the smallest eating speed that finishes all the piles within hours. Each check is an
O(n) simulation, and the range of speeds is searched with the low < high loop, which always ends on the
first value that works:
def min_speed(piles: list[int], hours: int) -> int:
def hours_needed(speed: int) -> int:
return sum((p + speed - 1) // speed for p in piles) # ceiling division
low, high = 1, max(piles)
while low < high:
mid = (low + high) // 2
if hours_needed(mid) <= hours:
high = mid # mid works: the answer is mid or smaller
else:
low = mid + 1 # mid fails: the answer is bigger
return low
print(min_speed([3, 6, 7, 11], 8))
print(min_speed([30, 11, 23, 4, 20], 5))
Python ints never overflow, so (low + high) // 2 is safe. In Java or C# you'd write low + (high - low) / 2.
Heaps
Recognise it: "top k", "k smallest/largest", "k closest", "the median of a stream", "merge k sorted lists", scheduling ("always process the earliest deadline next"), and Dijkstra's shortest path.
Cost: O(log n) push and pop, O(1) peek, O(n) heapify; top k of n items in O(n log k).
heapq works on a plain list and is a min-heap only. For a max-heap, push negated keys. Tuples compare
element by element, so (priority, tie_breaker, item) controls the order:
import heapq
tasks = [(3, "write tests"), (1, "fix prod"), (2, "review PR")]
heapq.heapify(tasks)
print(heapq.heappop(tasks))
print(tasks[0]) # peek at the next smallest
nums = [5, 1, 9, 3, 7, 2]
print(heapq.nlargest(3, nums), heapq.nsmallest(2, nums))
max_heap = [-n for n in nums]
heapq.heapify(max_heap)
print(-heapq.heappop(max_heap)) # the largest
Merging k sorted lists keeps one entry per list in the heap: the smallest remaining element overall is always at the front of some list.
import heapq
def merge_sorted(lists: list[list[int]]) -> list[int]:
heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapq.heapify(heap)
out = []
while heap:
value, i, j = heapq.heappop(heap)
out.append(value)
if j + 1 < len(lists[i]):
heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
return out
print(merge_sorted([[1, 4, 9], [2, 3, 10], [], [5]]))
print(list(heapq.merge([1, 4, 9], [2, 3, 10], [5]))) # the library version
The list index i in each entry breaks ties between equal values, so Python never has to compare the
things after it. That matters when those things are dicts or objects, which can't be compared and would
raise TypeError.
Intervals
Recognise it: meetings, bookings, time ranges, "merge overlapping", "insert an interval", "can one person attend all", "how many rooms". Almost always: sort by start, then sweep left to right.
Cost: O(n log n) for the sort, then O(n) for the sweep.
def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
merged: list[tuple[int, int]] = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]: # overlaps the last block
merged[-1] = (merged[-1][0], max(merged[-1][1], end))
else:
merged.append((start, end))
return merged
print(merge_intervals([(8, 10), (1, 3), (2, 6), (15, 18), (17, 20)]))
print(merge_intervals([(1, 10), (2, 3)]))
How many rooms do overlapping meetings need? Sort by start, and keep a heap of end times for the rooms in use. If the earliest-ending room is free by the time the next meeting starts, reuse it:
import heapq
def rooms_needed(meetings: list[tuple[int, int]]) -> int:
ends: list[int] = []
for start, end in sorted(meetings):
if ends and ends[0] <= start:
heapq.heapreplace(ends, end) # reuse the room that frees up first
else:
heapq.heappush(ends, end) # open another room
return len(ends)
print(rooms_needed([(0, 30), (5, 10), (15, 20)]))
print(rooms_needed([(9, 10), (10, 11)]))
Decide early whether touching intervals ((9, 10) and (10, 11)) overlap, and say it out loud. Here they
don't, so one room is enough.
Memoisation and dynamic programming
Recognise it: "how many ways", "minimum cost", "maximum value", "is it possible", over choices that build on smaller versions of the same problem, where a plain recursive solution recomputes the same subproblems again and again. Classics: climbing stairs, coin change, house robber, longest common subsequence, edit distance, knapsack.
Cost: (number of distinct subproblems) × (work per subproblem). Space is the size of the table or cache.
Top-down: write the recursion, then add @functools.cache (Python 3.9+; lru_cache(maxsize=None) before
that). The arguments become the cache key, so they must be hashable: pass tuples, not lists.
from functools import cache
@cache
def ways(n: int) -> int:
"""Ways to climb n stairs taking 1 or 2 steps at a time."""
if n <= 1:
return 1
return ways(n - 1) + ways(n - 2)
print(ways(5), ways(80))
print(ways.cache_info().currsize)
Without @cache, ways(80) makes more than 10¹⁶ calls; with it, each n is computed once, which is why
the cache holds 81 entries. The recursion limit still applies, though: ways(5000) on a cold cache raises
RecursionError.
Bottom-up: fill a table from the smallest subproblems up, with a loop and no recursion. Fewest coins to make an amount:
def fewest_coins(coins: list[int], amount: int) -> int:
INF = amount + 1 # more coins than could ever be needed
best = [0] + [INF] * amount # best[a] = fewest coins that make a
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return best[amount] if best[amount] != INF else -1
print(fewest_coins([1, 5, 10, 25], 63))
print(fewest_coins([2], 3))
print(fewest_coins([1, 3, 4], 6)) # greedy 4+1+1 would say 3; the answer is 3+3
That runs in O(amount × len(coins)) time and O(amount) space. For 2D tables, build the rows with a
comprehension, [[0] * (n + 1) for _ in range(m + 1)]. [[0] * (n + 1)] * (m + 1) repeats the same row
object, so writing one cell changes every row:
bad = [[0] * 3] * 2
good = [[0] * 3 for _ in range(2)]
bad[0][0] = 1
good[0][0] = 1
print(bad, good)
In an interview, start top-down (it falls out of the recursive definition), then offer bottom-up when the input is large or when you can shrink the table to one or two rows.
Recognising the pattern
| The problem says... | Reach for |
|---|---|
| "find a pair / have I seen it / count each" | dict, set, Counter |
| sorted input, pairs or in-place changes | two pointers |
| contiguous subarray or substring, longest/shortest/at most k | sliding window |
| many range sums, or subarrays summing to k with negatives | prefix sums + Counter |
| matching brackets, most recent unmatched, next greater | stack, monotonic stack |
| fewest steps, shortest path with equal costs, levels | BFS with deque |
| everything reachable, all paths or combinations | DFS (iterative if deep), backtracking |
| sorted lookups, or "minimum X that works" | bisect, binary search on the answer |
| top k, k-way merge, always take the smallest next | heapq |
| ranges of time or numbers | sort by start, then sweep |
| count ways, min cost, overlapping subproblems | @cache, then a bottom-up table |
Talking through a solution
Interviewers grade the conversation as much as the code. A routine that works:
- Restate and ask. Repeat the problem in your words. Ask about input size, empty input, duplicates, negatives, and what to return when there's no answer. The answers often pick the pattern for you: n up to 10⁵ rules out O(n²).
- Work an example by hand, including an edge case. It catches misunderstandings before any code exists.
- Say the brute force and its cost in one sentence ("check every pair, O(n²)"). It shows you can solve it at all, and it's the baseline to improve on.
- Name the bottleneck and the pattern. "The inner loop is searching for a partner; a dict makes that O(1)." Agree on the approach before typing.
- Write it cleanly, narrating the invariant ("
seenholds everything left ofi"). Use clear names and the standard library; nobody wants a hand-written heap. - Test it out loud on your example and an edge case, tracing the variables. Fix bugs calmly; finding your own bug is a good signal.
- State the time and space complexity, and mention the follow-ups you'd consider: streaming input, input too big for memory, or a recursion depth that needs the iterative version.
The exercises in this topic each take one pattern from the table above and dress it up as a realistic task. Name the pattern first, then write it.
Practise this lesson
In the app: a short video, 8 exercises checked by real tests and a 12-question concept check. Free with a GitHub account.
Open in the app