Coding Interview Patterns
Eight patterns that cover most problems — each with the signal that tells you to reach for it, the brute force it replaces, and the timing that proves the difference.
Most interview problems are one of a small number of shapes. This lesson gives the signal that identifies each, and measures the improvement it buys.
1. Two pointers — signal: sorted array, find a pair
import time, random
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return (i, j)
return None
def two_sum_pointers(nums, target): # requires sorted input
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return (lo, hi)
if s < target:
lo += 1 # only moving lo can increase the sum
else:
hi -= 1
return None
nums = sorted(random.sample(range(1_000_000), 20_000))
target = nums[7_000] + nums[15_000]
t0 = time.perf_counter(); r1 = two_sum_brute(nums, target); t1 = time.perf_counter()
r2 = two_sum_pointers(nums, target); t2 = time.perf_counter()
print(f"brute O(n²) {t1-t0:8.4f}s {r1}")
print(f"pointers O(n) {t2-t1:8.4f}s {r2}")brute O(n²) 2.8412s (7000, 15000)
pointers O(n) 0.0009s (7000, 15000)The insight to say aloud: “because the array is sorted, if the sum is too small only moving the left pointer can help — so each step eliminates a whole row of the brute-force matrix.”
Unsorted input? Use a hash map instead — O(n) without needing the sort:
def two_sum_hash(nums, target):
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return (seen[target - x], i)
seen[x] = i
return None2. Sliding window — signal: contiguous subarray or substring
def longest_unique_brute(s):
best = 0
for i in range(len(s)):
seen = set()
for j in range(i, len(s)):
if s[j] in seen:
break
seen.add(s[j])
best = max(best, j - i + 1)
return best
def longest_unique_window(s):
last, start, best = {}, 0, 0
for i, ch in enumerate(s):
if ch in last and last[ch] >= start:
start = last[ch] + 1 # shrink from the left, never re-scan
last[ch] = i
best = max(best, i - start + 1)
return best
s = "".join(random.choices("abcdefghij", k=40_000))
t0 = time.perf_counter(); a = longest_unique_brute(s); t1 = time.perf_counter()
b = longest_unique_window(s); t2 = time.perf_counter()
print(f"brute O(n²) {t1-t0:8.4f}s → {a}")
print(f"window O(n) {t2-t1:8.4f}s → {b}")brute O(n²) 1.9204s → 10
window O(n) 0.0088s → 10“The window only ever moves right. Each character is added once and removed once, so it is O(n) despite the nested-looking logic — that amortised argument is the part worth stating.”
The fixed-size variant is the other common form:
def max_sum_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # add one, drop one — O(1) per step
best = max(best, window)
return best
print(max_sum_k([2, 1, 5, 1, 3, 2], 3))93. Hash map counting — signal: frequency, anagram, duplicate
from collections import Counter, defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w) # canonical form as the key
return list(groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
def first_non_repeating(s):
counts = Counter(s)
return next((c for c in s if counts[c] == 1), None)
print(first_non_repeating("swiss"))[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
wThe reusable idea: find a canonical form and use it as a key. Sorted letters for anagrams, a tuple of counts for permutations, a normalised string for near-duplicates.
4. Binary search — signal: sorted, or a monotonic answer space
The second signal is the one that separates candidates. The array need not be the thing you search:
import math
def min_capacity(weights, days):
"""Least ship capacity to deliver all packages within `days`. The answer space
is monotonic: if capacity C works, C+1 works — so binary search the answer."""
def days_needed(cap):
d, load = 1, 0
for w in weights:
if load + w > cap:
d, load = d + 1, 0
load += w
return d
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if days_needed(mid) <= days:
hi = mid # feasible — try smaller
else:
lo = mid + 1
return lo
w = [1,2,3,4,5,6,7,8,9,10]
print(f"capacity for 5 days: {min_capacity(w, 5)}")
print(f"search space was {max(w)}..{sum(w)} = {sum(w)-max(w)+1} values, "
f"~{math.ceil(math.log2(sum(w)-max(w)+1))} probes")capacity for 5 days: 15
search space was 10..55 = 46 values, ~6 probes“There is no sorted array here. What is sorted is the feasibility function — false, false, …, true, true — so I can binary search the answer itself. Any problem asking for a minimum or maximum value satisfying a monotonic condition is a binary-search problem.”
The bounds trap, worth mentioning: lo = mid + 1 and hi = mid (not mid - 1) with
while lo < hi converges without an infinite loop. Getting this wrong is the most common
binary-search bug.
5. BFS and DFS — signal: grid, tree, graph, shortest path
from collections import deque
def shortest_path(grid, start, goal):
"""BFS gives the shortest path in an unweighted graph. DFS does not."""
rows, cols = len(grid), len(grid[0])
q = deque([(start, 0)])
seen = {start}
while q:
(r, c), dist = q.popleft()
if (r, c) == goal:
return dist
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr,nc) not in seen:
seen.add((nr, nc))
q.append(((nr, nc), dist + 1))
return -1
grid = [
[0,0,0,1,0],
[1,1,0,1,0],
[0,0,0,0,0],
[0,1,1,1,0],
[0,0,0,0,0],
]
print(f"shortest path (0,0)→(4,4): {shortest_path(grid, (0,0), (4,4))} steps")shortest path (0,0)→(4,4): 8 steps“BFS for shortest path in an unweighted graph, because it explores by distance. DFS for ‘does a path exist’, cycle detection, or topological order. Both are O(V + E). The queue versus stack is the only structural difference, and mixing them up gives a path rather than the shortest path — which passes small tests and fails the real one.”
Counting connected components is the other very common form:
def count_islands(grid):
rows, cols, seen, count = len(grid), len(grid[0]), set(), 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r, c) not in seen:
count += 1
stack = [(r, c)] # iterative — no recursion limit
seen.add((r, c))
while stack:
cr, cc = stack.pop()
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
nr, nc = cr+dr, cc+dc
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1 and (nr,nc) not in seen:
seen.add((nr, nc)); stack.append((nr, nc))
return count
print(f"islands: {count_islands([[1,1,0,0],[1,0,0,1],[0,0,1,1],[0,0,0,1]])}")islands: 2Writing it iteratively rather than recursively is worth a sentence: “a 1000×1000 grid would exceed Python’s recursion limit, so I’m using an explicit stack.”
6. Heap — signal: “top k”, “k largest”, a running median
import heapq
def top_k_sort(nums, k): return sorted(nums, reverse=True)[:k]
def top_k_heap(nums, k): return heapq.nlargest(k, nums)
nums = [random.random() for _ in range(2_000_000)]
for k in (10, 500_000):
t0 = time.perf_counter(); top_k_sort(nums, k); t1 = time.perf_counter()
top_k_heap(nums, k); t2 = time.perf_counter()
print(f"k={k:>7,} sort O(n log n) {t1-t0:6.3f}s heap O(n log k) {t2-t1:6.3f}s")k= 10 sort O(n log n) 0.842s heap O(n log k) 0.104s
k=500,000 sort O(n log n) 0.851s heap O(n log k) 1.284sThe heap wins by 8× at k=10 and loses at k=500,000 — say the crossover rather than the complexity alone.
The two-heap median is the classic follow-up:
class MedianStream:
def __init__(self):
self.lo, self.hi = [], [] # max-heap (negated), min-heap
def add(self, x):
heapq.heappush(self.lo, -heapq.heappushpop(self.hi, x))
if len(self.lo) > len(self.hi):
heapq.heappush(self.hi, -heapq.heappop(self.lo))
@property
def median(self):
return self.hi[0] if len(self.hi) > len(self.lo) else (self.hi[0] - self.lo[0]) / 2
m = MedianStream()
for x in [5, 15, 1, 3]:
m.add(x)
print(f"added {x:>2} → median {m.median}")added 5 → median 5
added 15 → median 10.0
added 1 → median 5
added 3 → median 4.0“Two heaps keep the halves balanced, so the median is always at one of the two roots — O(log n) insert, O(1) read.”
7. Intervals — signal: meetings, ranges, overlaps
def merge_intervals(intervals):
if not intervals:
return []
intervals = sorted(intervals) # sorting first is the whole trick
out = [list(intervals[0])]
for start, end in intervals[1:]:
if start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return out
print(merge_intervals([(1,3), (8,10), (2,6), (15,18)]))
def min_rooms(meetings):
"""Sweep line: +1 at each start, -1 at each end."""
events = sorted([(s, 1) for s, _ in meetings] + [(e, -1) for _, e in meetings])
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
print(f"rooms needed: {min_rooms([(0,30), (5,10), (15,20)])}")[[1, 6], [8, 10], [15, 18]]
rooms needed: 2“Almost every interval problem starts with a sort, and the sweep line — sorting the boundaries rather than the intervals — handles the ‘how many at once’ family. Note the
-1sorts before+1at the same timestamp, which is what makes a meeting ending exactly when another starts not need two rooms.”
8. Dynamic programming — signal: overlapping subproblems, “how many ways”
from functools import lru_cache
def climb_naive(n):
return 1 if n <= 1 else climb_naive(n-1) + climb_naive(n-2)
@lru_cache(maxsize=None)
def climb_memo(n):
return 1 if n <= 1 else climb_memo(n-1) + climb_memo(n-2)
def climb_iter(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
for n in (25, 30):
t0 = time.perf_counter(); climb_naive(n); t1 = time.perf_counter()
climb_memo(n); t2 = time.perf_counter()
climb_iter(n); t3 = time.perf_counter()
print(f"n={n} naive {t1-t0:7.4f}s memo {t2-t1:.6f}s iterative {t3-t2:.6f}s")
print(f"\nclimb_iter(1000) has {len(str(climb_iter(1000)))} digits — "
f"and O(1) space")n=25 naive 0.0412s memo 0.000021s iterative 0.000004s
n=30 naive 0.4602s memo 0.000004s iterative 0.000005s
climb_iter(1000) has 209 digits — and O(1) spaceThe progression is the answer: “recursion shows the recurrence, memoisation removes the repeated work — O(2^n) to O(n) — and the bottom-up version removes the stack, which is O(n) space in the memoised version and O(1) here. I would write the recursion first to get the recurrence right, then convert.”
Recognising the pattern
SIGNAL IN THE PROBLEM REACH FOR
sorted array, find a pair/triple two pointers
contiguous subarray / substring sliding window
frequency, anagram, "seen before" hash map
sorted, or a monotonic yes/no answer binary search
grid, tree, graph, "shortest" BFS (DFS for existence/order)
"top k", "k closest", running median heap
meetings, ranges, overlaps sort + sweep line
"how many ways", "min/max cost path" dynamic programming
"next greater/smaller element" monotonic stack
"all combinations/permutations" backtrackingSay the signal out loud — “‘contiguous subarray’ says sliding window to me” — because pattern recognition is explicitly what the round tests.
When nothing matches
1. Write the brute force. State its complexity.
2. Find the repeated work — that is almost always what the optimisation removes.
3. Ask which tool removes that repetition:
repeated lookup → hash map
repeated scan → sorting, or two pointers
repeated subproblem → memoisation
repeated max/min → heap, or a monotonic stackStep 2 is the general technique behind every pattern above, and saying it is a better answer than naming a pattern you half-remember.
Practice
1. Solve two-sum on a sorted array both ways and time it.
brute O(n²) 2.8412s
pointers O(n) 0.0009s3,000×. And state why the pointer move is valid — that sortedness means only one direction can improve the sum.
2. Binary search an answer space with no sorted array.
capacity for 5 days: 15 (~6 probes over 46 candidate values)The feasibility function is monotonic, so binary search applies even though nothing is sorted. This is the variant that separates candidates.
3. Find where a heap stops beating a sort.
k=10 heap 8x faster
k=500,000 heap 1.5x slowerNaming the crossover is a better answer than naming the complexity, and it is the follow-up interviewers ask.
4. Convert a recursion to memoised and then to iterative.
naive 0.4602s → memo 0.000004s → iterative 0.000005s, O(1) spaceThree steps, two distinct wins: memoisation removes repeated work, the iterative form removes the stack. Say which each one buys.
Next: take-homes and live coding — the two formats with different rules.