Data Structures and Algorithms by Pattern

22.1 Why patterns, not problems

There are effectively infinite algorithm questions and about eleven ideas. Preparation that targets questions scales linearly and runs out; preparation that targets ideas compounds, because every new question is a recombination of things you already know.

The evidence for this is uncomfortable but useful. Companies that interview at volume actively retire questions once they leak, so the specific problems circulating publicly are, almost by definition, the ones you will not be asked. What survives that churn is structural: the interviewer needs a problem that can be stated in two minutes, solved in twenty, and admits a naive solution plus at least one meaningful optimisation. That constraint is what generates the eleven patterns. It is far more stable than any individual question.

22.2 The first ninety seconds

What you do immediately after hearing the problem matters more than anything else in the interview, because it determines whether the next twenty minutes are spent solving the right problem. It is also the most commonly skipped step: the instinct under stress is to start coding, and that instinct is wrong.

22.3 Complexity as a search hint

Complexity analysis is usually taught as something you do after writing code, to describe it. In an interview it is far more valuable used in reverse: as a constraint that tells you what kind of algorithm can possibly work, before you have one.

The reasoning runs backwards from the input size. Roughly 10⁸ simple operations is the most that runs comfortably in a second, so the size of n implies a ceiling on the complexity, and the complexity implies a very short list of techniques.

22.4 The pattern recognition table

This is the index for the rest of the chapter: the signal in the problem statement, and the pattern it points to. The signals are structural, not lexical — each one describes something true about the problem, not a phrase to grep for.

22.5 Two pointers

The signal: the input is sorted (or you are allowed to sort it), and you are looking for a pair, triple, or partition with some property. Also: any time you would otherwise write two nested loops over the same array.

Why it works. The whole pattern rests on one observation: when the array is sorted, comparing the current pair to the target tells you unambiguously which pointer to move. If the sum is too small, no amount of moving the right pointer down will help — it only makes the sum smaller. So the left pointer must move up. That "unambiguously" is the entire justification, and it is what you should say out loud. Each step eliminates at least one candidate permanently, so the total work is linear.

def two_sum_sorted(a, target):
    """a is sorted ascending. Return the pair of indices summing to target."""
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == target:
            return (i, j)
        if s < target:
            i += 1        # too small: only moving i up can increase the sum
        else:
            j -= 1        # too big: only moving j down can decrease the sum
    return None

The invariant worth naming: every pair not yet examined lies strictly between i and j. When they meet, the space is exhausted, which is why returning None at that point is provably correct rather than a guess.

22.6 Sliding window

The signal: the word contiguous (or "subarray" or "substring") plus a superlative — longest, shortest, maximum, or "contains at most k distinct".

Why it works. The brute force examines every (start, end) pair, which is O(n²) windows. The window pattern collapses this by exploiting a monotonicity: as the right edge advances, the leftmost valid start never moves backwards. That means each index enters the window once and leaves at most once, so despite the nested-looking structure, the total work is O(n). Whenever you use this pattern, that non-backtracking property is the thing to justify.

def longest_unique(s):
    """Length of the longest substring with no repeated character."""
    last_seen = {}
    best = start = 0
    for i, c in enumerate(s):
        # Only shrink if the duplicate is INSIDE the current window.
        if c in last_seen and last_seen[c] >= start:
            start = last_seen[c] + 1
        last_seen[c] = i
        best = max(best, i - start + 1)
    return best

When the window size is fixed rather than variable, the pattern gets simpler — no shrink condition, just add the entering element and subtract the leaving one:

def max_sum_k(a, k):
    """Largest sum of any k consecutive elements."""
    if len(a) < k:
        return None
    window = sum(a[:k])
    best = window
    for i in range(k, len(a)):
        window += a[i] - a[i - k]   # add entering, remove leaving: O(1) per step
        best = max(best, window)
    return best

22.7 Hash map and frequency

The signal: "have I seen this before", counting occurrences, grouping by a derived key, or looking up a complement. Whenever a nested loop exists only to search for a matching element, a hash map removes the inner loop.

Why it works. It trades space for time in the most direct way available: O(n) memory buys O(1) lookup, converting a scan into a question. The insight to articulate is the reframing — instead of asking "is there a pair summing to target", ask, for each element, "have I already seen target - v". The second question is answerable in constant time; the first is not.

def two_sum(a, target):
    """Unsorted input. One pass: remember what we have seen."""
    seen = {}                       # value -> index
    for i, v in enumerate(a):
        if target - v in seen:      # the partner arrived earlier
            return (seen[target - v], i)
        seen[v] = i
    return None

22.8 Intervals

The signal: anything with start and end times — overlaps, merges, room or resource allocation, scheduling.

Why it works. Almost every interval problem becomes easy after sorting, and the entire skill is knowing what to sort by. Sort by start time to merge overlapping intervals; sort by end time for greedy "maximum non-overlapping" selection. The meeting rooms problem below uses a third option that is worth understanding properly, because it is the one candidates rarely find unprompted.

def min_meeting_rooms(intervals):
    """Fewest rooms so that no two overlapping meetings share one."""
    if not intervals:
        return 0
    starts = sorted(s for s, _ in intervals)
    ends   = sorted(e for _, e in intervals)
    i = j = in_use = best = 0
    while i < len(starts):
        if starts[i] < ends[j]:     # a meeting begins before the next one ends
            in_use += 1
            best = max(best, in_use)
            i += 1
        else:                       # a room frees up first
            in_use -= 1
            j += 1
    return best

The trick is that starts and ends are sorted separately, decoupling them. The algorithm then sweeps a virtual clock: every start before the next end means a new concurrent meeting, every end means a room is released. The maximum concurrency observed is exactly the number of rooms needed, because at that instant that many meetings are genuinely running at once.

22.9 Binary search on the answer

The signal: "minimise the maximum", "maximise the minimum", "the smallest capacity such that…", or any problem where checking a candidate answer is easy but constructing the best one directly is hard.

Why it works. This is the pattern most candidates fail to recognise, and the one that most impresses when found. The realisation is that you are not searching an array — you are searching the space of possible answers. It applies whenever feasibility is monotone: if a capacity of 18 works, then 19, 20, and everything above also work. That monotone boundary is exactly what binary search locates, and saying the word "monotone" out loud is what signals you know why this is valid rather than having pattern-matched.

def split_array_min_largest(nums, k):
    """Split nums into k contiguous parts, minimising the largest part sum."""

    def can_do_with_cap(cap):
        """Greedy: how few parts can we get if no part may exceed cap?"""
        parts, current = 1, 0
        for n in nums:
            if current + n > cap:
                parts += 1
                current = n
                if parts > k:
                    return False
            else:
                current += n
        return True

    lo, hi = max(nums), sum(nums)   # cap must fit one element; sum always works
    while lo < hi:
        mid = (lo + hi) // 2
        if can_do_with_cap(mid):
            hi = mid                # feasible: try to do better
        else:
            lo = mid + 1            # infeasible: need a bigger cap
    return lo

Note the structure: an inner greedy function that answers a yes/no question, wrapped in a binary search over the answer range. The greedy check is easy to write and easy to verify. Directly computing the optimal split is not. That asymmetry — hard to construct, easy to verify — is the real signal for this pattern.

22.10 Heaps and top-K

The signal: "the k largest", "the k-th smallest", "the k closest", or a running median over a stream. Also any time you need repeated access to the current extreme of a changing collection.

Why it works. A heap gives O(log n) insertion and O(1) access to the extreme, without paying for a full ordering you do not need. The key insight for interviews is the complexity argument: maintaining a heap of size k costs O(n log k), which beats sorting's O(n log n) whenever k is much smaller than n. If k is 10 and n is ten million, that difference is enormous, and being able to state it is the point of the question.

import heapq

def k_closest_to_origin(points, k):
    """The k points nearest (0,0). Compare squared distance: no sqrt needed."""
    return heapq.nsmallest(k, points, key=lambda p: p[0]*p[0] + p[1]*p[1])

def kth_smallest(a, k):
    """k-th smallest value. O(n log k) with a bounded heap, not O(n log n)."""
    return heapq.nlargest(k, a)[-1] if k > len(a)//2 else heapq.nsmallest(k, a)[-1]

For the k-closest-points variant, there is a second observation worth voicing: comparing squared distances avoids computing square roots entirely. Since squaring is monotone on non-negative values, the ordering is identical, and you have removed n transcendental operations for free.

22.11 Sorting as preprocessing

The signal: the problem is much easier when the data is in order, and nothing in the problem depends on the original positions.

Sorting is rarely the answer by itself; it is the step that makes the actual answer simple. The judgement being tested is whether you notice that O(n log n) is free in context — if the rest of your algorithm already costs that much, or if the alternative is an O(n²) scan, then sorting costs nothing you were not already paying.

22.12 BFS: fewest steps

The signal: "shortest path", "fewest moves", "minimum number of steps", or anything that proceeds level by level — on a grid, a graph, or an implicit state space where the edges are moves rather than stored links.

Why it works. BFS visits nodes in non-decreasing order of distance from the source, so the first time it reaches a node, it has arrived by a shortest path. That guarantee holds only when every edge costs the same; with varying weights you need Dijkstra instead. Being explicit about this precondition — "the edges are all unit cost, so BFS gives the shortest path and I do not need Dijkstra" — is a distinguishing remark.

from collections import deque

INF = 2**31 - 1     # an empty room

def walls_and_gates(grid):
    """Fill each empty room with its distance to the nearest gate (0). -1 is a wall.

    Multi-source BFS: seed the queue with EVERY gate at once, so the first
    time a room is reached it is reached by the nearest gate automatically.
    """
    if not grid or not grid[0]:
        return grid
    rows, cols = len(grid), len(grid[0])
    q = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 0)
    while q:
        r, c = q.popleft()
        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] == INF:
                grid[nr][nc] = grid[r][c] + 1
                q.append((nr, nc))
    return grid

22.13 DFS, recursion, backtracking

The signal: explore every path, enumerate all combinations or permutations, find connected components, or any tree traversal. If the problem says "all possible", it is almost always backtracking.

Why it works. DFS commits to one branch fully before trying the next, which makes it the natural fit for exhaustive exploration and for anything defined recursively (a tree, a component, a partial solution). The distinction from BFS is worth stating crisply: DFS answers "is there a path / what are all the paths", BFS answers "what is the shortest path".

def num_islands(grid):
    """Count connected components of '1' in a grid. Sinks each island as it goes."""
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
            return
        grid[r][c] = '0'          # mark visited by mutating: no separate set needed
        sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1        # a cell still standing starts a new island
                sink(r, c)
    return count

Mutating the grid to mark visits is a deliberate space optimisation over a separate visited set, and it is the kind of trade worth flagging out loud — along with the caveat that it destroys the caller's input, which you should confirm is acceptable.

Backtracking is DFS over a space of partial solutions, and every backtracking problem has the same three-line skeleton:

def subsets(nums):
    """Every subset. The shape of all backtracking: choose, recurse, un-choose."""
    out, path = [], []

    def explore(start):
        out.append(path[:])            # copy: path keeps mutating underneath us
        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            explore(i + 1)             # recurse on what remains
            path.pop()                 # un-choose, restoring state for the next branch
    explore(0)
    return out

22.14 Topological sort

The signal: dependencies, prerequisites, build order, "A must come before B", or recovering an unknown ordering from pairwise constraints.

Why it works. Kahn's algorithm repeatedly emits any node with no unmet dependencies, then removes it and its outgoing edges, which may free others. It doubles as cycle detection for free: if the algorithm stalls with nodes remaining, those nodes form a cycle, because every one of them is waiting on another. That two-for-one property is why it is preferred over the DFS-based variant in interviews.

from collections import deque, defaultdict

def alien_order(words):
    """Recover the letter order of an alien alphabet from sorted words.

    Each adjacent pair of words yields at most ONE constraint: the first
    position where they differ. Everything after that tells you nothing.
    """
    successors = defaultdict(set)
    indegree = {c: 0 for w in words for c in w}

    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if y not in successors[x]:
                    successors[x].add(y)
                    indegree[y] += 1
                break
        else:
            # No difference found in the overlap. "abc" before "ab" is
            # impossible in any ordering, so the input is contradictory.
            if len(first) > len(second):
                return ""

    ready = deque(sorted(c for c in indegree if indegree[c] == 0))
    order = []
    while ready:
        c = ready.popleft()
        order.append(c)
        for nxt in sorted(successors[c]):
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                ready.append(nxt)

    # Fewer letters emitted than exist means a cycle swallowed the rest.
    return "".join(order) if len(order) == len(indegree) else ""

22.15 Recognising a DP problem

The signal: "count the number of ways", "the minimum/maximum cost to", or a recursive brute force that recomputes the same subproblem repeatedly. Also: the word subsequence, which almost never means sliding window and almost always means DP.

DP is the pattern candidates most often fail to start, usually because they try to find the table first. That is backwards. The reliable route is to write the recursion, notice it repeats work, and then cache it. The table is an optimisation of a recursion you have already written, never the starting point.

22.16 One-dimensional DP

One-dimensional DP covers problems where the state is a single index or a single quantity. The classic is Kadane's algorithm, which is worth studying because it is DP compressed to two variables — the table is there, but only the last cell is ever needed.

def max_subarray(a):
    """Largest sum of any non-empty contiguous subarray (Kadane)."""
    best = current = a[0]
    for v in a[1:]:
        # Either v starts a fresh subarray, or it extends the previous one.
        current = max(v, current + v)
        best = max(best, current)
    return best

The recurrence hiding in that one line is best_ending_here[i] = max(a[i], best_ending_here[i-1] + a[i]): either the previous run is worth extending, or it is not and you start fresh. Since only the previous value is ever read, the array collapses to a scalar — the space optimisation described in step 5 above, applied.

Coin change is the other archetype: a state per amount, and a loop over choices at each.

def coin_change(coins, amount):
    """Fewest coins summing to amount, or -1. Classic 1-D DP over subproblems."""
    INF = float("inf")
    best = [0] + [INF] * amount        # best[x] = fewest coins to make x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and best[x - c] + 1 < best[x]:
                best[x] = best[x - c] + 1
    return -1 if best[amount] == INF else best[amount]

22.17 Two-dimensional DP

When the recursion takes two arguments — usually a position in each of two sequences, or a range with two endpoints — the table becomes a grid. The canonical example is longest common subsequence, and the shape of its recurrence recurs across edit distance, string matching, and most sequence-alignment problems.

def lcs_length(a, b):
    """Length of the longest common subsequence (not substring)."""
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1      # match: extend the diagonal
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])   # drop one character
    return dp[-1][-1]

Read the recurrence as a decision at the last character of each string. If they match, that character is in the subsequence and you move diagonally, having consumed both. If they do not, one of them cannot be in the answer, so you try dropping each and keep the better outcome. The +1 row and column of zeros encodes the base case — an empty string shares nothing with anything — without special-casing it in the loop.

22.18 What a strong answer sounds like

Getting the optimal solution is not what separates candidates, because plenty of people get there. What separates them is whether the interviewer could follow the reasoning, and whether the reasoning looked like engineering rather than recall.

This matters more at some companies than others. Google in particular is explicitly process-oriented rather than results-oriented — multiple Google interviewers describe reaching the optimal solution as insufficient on its own, and arriving at a strong approach with clear reasoning but incomplete code as frequently sufficient. The corollary is uncomfortable but actionable: silent correct coding scores worse than narrated partial progress.

22.19 A full worked transcript

Below is one problem worked end to end in the voice of a strong candidate. The problem is deliberately one whose optimal solution is not obvious: given an unsorted array, find the length of the longest run of consecutive integers it contains. For [100, 4, 200, 1, 3, 2] the answer is 4, from the run 1–2–3–4.

def longest_consecutive(nums):
    """Length of the longest run of consecutive integers. O(n) time."""
    pool = set(nums)                  # dedupes and gives O(1) membership
    best = 0
    for x in pool:
        if x - 1 in pool:
            continue                  # x is mid-run; its run gets walked from its start
        length = 1                    # x begins a run
        while x + length in pool:
            length += 1
        best = max(best, length)
    return best

22.20 Disguised questions and red herrings

Some interviewers deliberately design questions to look like a well-known problem that they are not. This is reported specifically and repeatedly about Google — a question shaped to look like Three Sum, where Three Sum is precisely the wrong approach.

The defence is not to recognise more problems. It is to verify that the problem in front of you actually satisfies the preconditions of the pattern you are about to apply. Every pattern in this chapter has a stated precondition for exactly this reason.

22.21 When you are stuck

Being stuck is normal and is not, by itself, disqualifying. Being stuck silently is, because it gives the interviewer nothing to evaluate and nothing to help with.

22.22 What Big-O actually measures

Every pattern in this chapter has come with a complexity attached — O(n), O(log n), O(n log n). This section is the one thing that was assumed rather than explained: what that notation actually means, and why it is built the way it is.

Big-O describes how the cost of an algorithm grows as the input grows, in the limit of large inputs. It is deliberately not a measurement of speed on any one input, and it deliberately throws away information that would make it more precise but less useful. Both of those choices are worth understanding rather than accepting.

22.23 Combining complexities

Almost no real algorithm is a single loop. The skill this section teaches is reading a block of code — sequences of steps, nested loops, recursive calls — and deriving its complexity mechanically, rather than guessing.

Bubble sort is the clearest possible illustration of the nested-loop rule, because the quadratic cost is visible directly in the shape of the work rather than needing to be taken on faith.

22.24 Tricky worked examples: time complexity

The rules in 22.23 are simple to state and easy to misapply. Every example below is a case where the obvious first guess is wrong, verified by actually counting the operations rather than trusting intuition.

def count_pairs_triangular(n):
    # Looks smaller than a full n x n nest because j starts at i, not 0.
    # It is still O(n^2): the comparisons made form a triangular number.
    comparisons = 0
    for i in range(n):
        for j in range(i, n):
            comparisons += 1
    return comparisons

The comparison counts form exactly the triangular sequence from 22.23: n + (n-1) + … + 1 = n(n+1)/2. Halving a quadratic quantity is still quadratic — confirmed above by checking that doubling n quadruples the count, the defining test for O(n²). The lesson: a nested loop is O(n²) whenever the inner loop's range scales with n, regardless of where that range starts.

def naive_fib_calls(n, calls=None):
    # Returns the TOTAL number of function calls made, not the Fibonacci value,
    # so the exponential blow-up is directly countable rather than inferred.
    if calls is None:
        calls = [0]
    calls[0] += 1
    if n <= 1:
        return calls[0]
    naive_fib_calls(n - 1, calls)
    naive_fib_calls(n - 2, calls)
    return calls[0]

def memo_fib_calls(n, memo=None, calls=None):
    if memo is None:
        memo, calls = {}, [0]
    calls[0] += 1
    if n in memo:
        return calls[0]
    if n <= 1:
        memo[n] = n
        return calls[0]
    memo_fib_calls(n - 1, memo, calls)
    memo_fib_calls(n - 2, memo, calls)
    memo[n] = memo[n - 1] + memo[n - 2]
    return calls[0]

def concat_cost(n):
    # Every += on a Python str creates a brand-new string and copies the old
    # content into it, because strings are immutable. Track total characters
    # copied rather than wall-clock time, for a deterministic assertion.
    s = ""
    copied = 0
    for i in range(n):
        piece = "x"
        copied += len(s) + len(piece)   # cost of building the new string
        s = s + piece
    return copied

def join_cost(n):
    # str.join builds the result once, from a list, in a single pass.
    parts = []
    copied = 0
    for i in range(n):
        parts.append("x")
        copied += 1                     # appending to a list is O(1) amortised
    copied += sum(len(p) for p in parts)  # the one final join pass
    return copied

Copying grows with the string built so far, so the total work across the loop is 1 + 2 + … + n — the same triangular shape as bubble sort and Example 1, giving O(n²). Building a list with append (O(1) amortised per call, 22.23) and joining once at the end does the copying exactly once, in a single O(n) pass. The check above confirms it directly: doubling n roughly quadruples the concatenation cost but only doubles the append-and-join cost.

def halving_steps(n):
    # A loop, not a recursive call -- and still O(log n), because what matters
    # for complexity is how the WORK shrinks, not whether it is spelled with
    # a loop or a recursion.
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

This is a loop, not a recursive call, and yet it is O(log n): the check confirms n = 1,000,000 takes only 19 iterations, and that doubling n from 1024 to 2048 adds exactly one more step. Complexity is a property of how the work shrinks, never of which syntax (loop or recursion) was used to express it — a fact worth stating explicitly if an interviewer tries to anchor you to "loops are O(n)".

22.25 Tricky worked examples: space complexity

Space complexity is asked about less often than time, which makes it easier to get wrong in the moment. The most common trap is conflating the two: assuming a slow algorithm must also use a lot of memory, or a fast one must use little.

def naive_fib_depth(n):
    # O(2^n) TIME (branches out), but the call STACK at any instant only
    # holds one path from root to leaf -- so space is O(n), not O(2^n).
    def go(n, depth, max_depth):
        max_depth[0] = max(max_depth[0], depth)
        if n <= 1:
            return
        go(n - 1, depth + 1, max_depth)
        go(n - 2, depth + 1, max_depth)
    max_depth = [0]
    go(n, 0, max_depth)
    return max_depth[0]

def iterative_fib(n):
    # O(n) time, O(1) space: only ever holds the last two values.
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def merge_sort_counting_space(a):
    # Counts the total auxiliary array cells allocated across the whole sort,
    # to make the O(n) auxiliary space claim concrete rather than asserted.
    allocated = [0]

    def sort(a):
        if len(a) <= 1:
            return a
        mid = len(a) // 2
        left = sort(a[:mid])
        right = sort(a[mid:])
        allocated[0] += len(left) + len(right)   # the merge buffer for this call
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged

    result = sort(a)
    return result, allocated[0]

Summed across one full level of the recursion, the merge buffers at that level together hold all n elements exactly once; there are O(log n) levels, but each level's buffers are released before the next level needs its own, so the peak memory in use at any instant is O(n), not O(n log n). The O(log n) recursion stack is real but small by comparison — it is the merge buffers, not the recursion itself, that define this algorithm's O(n) auxiliary space. This is also the standard argument for preferring quicksort when memory is tight: a well-implemented in-place partition needs no separate merge buffer at all, at the cost of losing the stability and worst-case guarantees that merge sort provides.

def subsets_space_accounting(nums):
    # Distinguishes OUTPUT space (the unavoidable answer itself) from
    # AUXILIARY space (the extra bookkeeping the algorithm needs beyond
    # producing that answer).
    out, path = [], []
    max_path_len = [0]

    def explore(start):
        max_path_len[0] = max(max_path_len[0], len(path))
        out.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            explore(i + 1)
            path.pop()

    explore(0)
    output_cells = sum(len(s) for s in out)   # every element, in every subset
    auxiliary_cells = max_path_len[0]          # the deepest the path list ever got
    return out, output_cells, auxiliary_cells

22.26 Key takeaways

22.27 Interview drills

These test pattern recognition and the reasoning around it, which is what actually fails in interviews — implementation is rarely the bottleneck. Answer out loud before expanding.

Expand all

Where this leaves you

Eleven patterns, each with the signal that identifies it, the invariant that makes it correct, and working code. That covers the coding rounds, which at Google are weighted more heavily than system design — the only FAANG company where that is true.

The next chapter covers the other kind of coding question that appears in these loops: probability and simulation problems, where the answer is a number you estimate rather than an algorithm you implement.