Coding Interview Patterns

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 None

2. 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))

9

3. 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']]
w

The 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: 2

Writing 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.284s

The 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 -1 sorts before +1 at 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) space

The 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"          backtracking

Say 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 stack

Step 2 is the general technique behind every pattern above, and saying it is a better answer than naming a pattern you half-remember.

Practice

brute    O(n²)  2.8412s
pointers O(n)   0.0009s

capacity for 5 days: 15  (~6 probes over 46 candidate values)

k=10       heap 8x faster
k=500,000  heap 1.5x slower

naive 0.4602s → memo 0.000004s → iterative 0.000005s, O(1) space

Next: take-homes and live coding — the two formats with different rules.