The coding round: going deeper

Lesson 6 keeps the selector table, eight solved problems and the drills. This appendix holds the longer explanations and the other solved problems, in case a pattern in the selector is new to you or you want more practice. Problem statements are the author's own; every example is invented. Solutions to the ten transfer problems and to the drill set are in the next appendix lesson.

Pattern 1: two pointers

Context. The baseline checks every pair: n(n-1)/2 sums, which is quadratic. Sortedness gives information the baseline throws away.

Invariant. Every pair not yet ruled out lies inside [lo, hi].

Run the template on the sorted list 1, 3, 4, 6, 8, 11 with target 10. Each of the five steps discards one end for good: once 1 + 11 = 12 is too big, 11 can pair with nothing. The code returns 1-based positions, so the answer is (3, 4); an empty or one-element array returns null.

class SortedPair {
  /** 1-based (i, j) with nums[i-1] + nums[j-1] == target; nums sorted. */
  static int[] find(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
      int s = nums[lo] + nums[hi];
      if (s == target) return new int[] {lo + 1, hi + 1};
      if (s < target) lo++;
      else hi--;
    }
    return null;
  }
}

Cost. O(n) time because every step moves an index and the two indices travel at most n steps between them; O(1) extra space. Where it breaks. If the array is not sorted, sorting costs O(n log n), and then you may prefer a hash set (O(n), O(n) space). Say that trade-off aloud; it is the kind of decision the interviewer is listening for.

Hack sheet: two pointers

Worked: 3Sum, every triple that sums to zero

Problem. Return every distinct triple of values from an int array that sums to 0, each triple once. Cue. "Triplet", "three numbers that sum to", "no duplicate triples". Idea. Sort once. Fix the first value a[i] and run the pair template on the rest with target -a[i]. Skip a first value equal to the one before it; after each hit, move both pointers and skip second values equal to the one just used. Equal third values then fall away on their own, because the sum is fixed.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class ThreeSum {
  /** Every distinct triple that sums to 0, each in ascending order. */
  static List<List<Integer>> threeSum(int[] input) {
    int[] a = input.clone();
    Arrays.sort(a);                              // O(n log n), once
    List<List<Integer>> out = new ArrayList<>();
    for (int i = 0; i + 2 < a.length; i++) {
      if (i > 0 && a[i] == a[i - 1]) continue;   // same first value
      int lo = i + 1, hi = a.length - 1;
      while (lo < hi) {
        long sum = (long) a[i] + a[lo] + a[hi];  // no int overflow
        if (sum < 0) lo++;
        else if (sum > 0) hi--;
        else {
          out.add(List.of(a[i], a[lo], a[hi]));
          lo++;
          hi--;
          while (lo < hi && a[lo] == a[lo - 1]) lo++;  // same second
        }
      }
    }
    return out;
  }
}

Cost. O(n squared) time: n first values, each with a linear pair walk; the sort adds O(n log n). O(1) extra space beyond the sorted copy and the output. Trap. Duplicates: without the skip after a hit, [-2, 0, 0, 2, 2] returns (-2, 0, 2) twice (a mutant of the listing, run on 2 Nov 2026). A second trap: three ints can overflow, and {MAX_VALUE, MAX_VALUE, 2} sums to 0 in int arithmetic, so the listing adds in a long. Fallback that still scores: the triple loop, O(n cubed), with each triple sorted into a set to drop repeats, said as such. If stuck: "I can find pairs with two pointers on a sorted array; fixing one value turns this into n pair problems." The harness compared the listing with an O(n cubed) brute force on 20,000 random arrays and checked that the input is left unchanged.

Next stop: Pattern 2: sliding window, 2 min

Pattern 2: sliding window

Context. The baseline tries every start and every end and checks each stretch: cubic if you recheck from scratch, quadratic if you are careful. But a stretch that has no repeats keeps having no repeats when you shrink it.

Invariant. The window [left, right] is valid after each step, and left never decreases.

Figure A6.1 follows "pwwkew". The version below stores the last index of every character, so a repeat moves left in one jump instead of one step at a time.

import java.util.HashMap;
import java.util.Map;

class Window {
  static int longest(String s) {
    Map<Character, Integer> last = new HashMap<>(); // char -> last index
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
      char ch = s.charAt(right);
      Integer p = last.get(ch);
      if (p != null && p >= left) left = p + 1;
      last.put(ch, right);
      best = Math.max(best, right - left + 1);
    }
    return best;
  }
}

Cost. O(n) time (each index enters and leaves the window once), O(min(n, alphabet size)) space. Where it breaks. A window works when the rule is monotone: shrinking never turns a bad window good. "Subarray with sum exactly k" over numbers that can be negative is not monotone, which is why that problem belongs to the next pattern. The other common window keeps counts and shrinks while it is valid (minimum window substring) or while it is broken (at most k distinct); both are worked in another section of this appendix.

Hack sheet: sliding window

Next stop: Pattern 3: prefix sums, 2 min

Pattern 3: prefix sums

Context. Define the prefix sum P[i] as the total of the first i elements, with P[0] = 0. The sum of the elements from position i up to j - 1 is then P[j] - P[i].

Invariant. The map holds every prefix total before the current element, with how many times each occurred.

Figure A6.2 draws the prefixes of [1, 2, 3] and the two arcs where the difference is 3.

import java.util.HashMap;
import java.util.Map;

class Prefix {
  static int countEqualK(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>(); // prefix sum -> times
    seen.put(0, 1);
    int total = 0, count = 0;
    for (int x : nums) {
      total += x;
      count += seen.getOrDefault(total - k, 0);
      seen.merge(total, 1, Integer::sum);
    }
    return count;
  }
}

Cost. O(n) time, O(n) space for the map. A brute force that sums every subarray is O(n squared). The "count subarrays with sum k" problem is not in either public list the author could open; it is included because it is the standard prefix-sum case.

Hack sheet: prefix sums

Next stop: Pattern 4: intervals, 2 min

Pattern 4: intervals

Context. If you compare every range with every other you do quadratic work and still have to handle chains (A overlaps B, B overlaps C). Sorting by start removes the chains: after the sort, a range can only overlap the one just before it in the output, because everything earlier ends before the current start or has already been absorbed.

Invariant. The output so far is sorted, non-overlapping, and covers exactly what the input seen so far covers.

Figure A6.3 draws the four input ranges on a line and the three merged ranges under them.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Merge {
  static int[][] merge(int[][] intervals) {
    int[][] a = intervals.clone(); // sort a copy of the row references
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] iv : a) {
      int[] last = out.isEmpty() ? null : out.get(out.size() - 1);
      if (last != null && iv[0] <= last[1]) {
        last[1] = Math.max(last[1], iv[1]);
      } else {
        out.add(new int[] {iv[0], iv[1]});
      }
    }
    return out.toArray(new int[0][]);
  }
}

Cost. O(n log n) for the sort, O(n) for the output. The merge pass itself is O(n). The output lists are new ones, so the caller's input is left intact. "Minimum number of arrows to burst balloons" uses the same sort-then-sweep idea.

Hack sheet: intervals

Next stop: Pattern 5: monotonic stack, 2 min

Pattern 5: monotonic stack

Context. The baseline scans forward from every day until it meets a warmer one: quadratic when temperatures only fall. The waste is that days still waiting for a warmer day are being rescanned by every day that follows them.

Invariant. The stack holds exactly the indices still waiting for an answer, with the coldest on top.

Figure A6.4 freezes the moment day 5 (72 degrees) arrives: it pops days 4 and 3, which were colder, and then sits on top of day 2 (75).

import java.util.ArrayDeque;
import java.util.Deque;

class Temps {
  static int[] daily(int[] temps) {
    int[] ans = new int[temps.length];
    Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting
    for (int i = 0; i < temps.length; i++) {
      while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
        int j = stack.pop();
        ans[j] = i - j;
      }
      stack.push(i);
    }
    return ans;
  }
}

Cost. O(n) time even though there is a loop inside a loop: each index is pushed once and popped at most once, so the inner loop does at most n pops in total across the whole run. That sentence ("amortised, each element enters and leaves once") is the one to say aloud. O(n) space for the stack in the worst case.

Hack sheet: monotonic stack

Next stop: Pattern 6: BFS and DFS on a grid, a graph or a tree, 3 min

Pattern 6: BFS and DFS on a grid, a graph or a tree

Context. A grid is a graph in disguise: each cell is a node, and its four neighbours are its edges. Both searches visit every reachable node once.

Invariant. Every node in the queue or already popped is marked seen; every node still unmarked has not been reached.

The three depth-first orders differ only in when the node is handled: preorder handles the node first (copying a tree), inorder between the subtrees (sorted order on a search tree), postorder last (a height or a sum from the children's answers).

Figure A6.5 shows breadth-first search by levels, with the queue written beneath. All nodes at distance d are taken before any at distance d + 1, so the first time BFS reaches a node is by a shortest path in steps; on a grid, "level" is "number of moves". The code below counts islands: each unseen land cell starts a new island, and a BFS from it marks the whole island.

import java.util.ArrayDeque;
import java.util.Deque;

class Islands {
  static int count(char[][] grid) {
    if (grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length, count = 0;
    boolean[][] seen = new boolean[rows][cols];
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int r = 0; r < rows; r++) {
      for (int c = 0; c < cols; c++) {
        if (grid[r][c] != '1' || seen[r][c]) continue;
        count++;
        seen[r][c] = true;
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[] {r, c});
        while (!q.isEmpty()) {
          int[] cur = q.poll();
          for (int[] d : dirs) {
            int ny = cur[0] + d[0], nx = cur[1] + d[1];
            if (ny >= 0 && ny < rows && nx >= 0 && nx < cols
                && grid[ny][nx] == '1' && !seen[ny][nx]) {
              seen[ny][nx] = true;
              q.add(new int[] {ny, nx});
            }
          }
        }
      }
    }
    return count;
  }
}

Cost. O(R x C) time and space for R rows and C columns: every cell is looked at a bounded number of times, and the seen table and queue are at most that size. The usual alternative is recursive DFS with the same count; its drawback is the call stack on a large grid (see the trap below), so the iterative form is safer. The same toolkit covers "maximum depth of a binary tree", "lowest common ancestor" and "right side view" (the last node of each BFS level); the public lists place those under this pattern.

Hack sheet: BFS and DFS

The stack-depth trap. A recursive DFS goes one call deeper per cell on a snake-shaped region. The author ran a recursive DFS over an all-land 400 by 400 grid (160,000 cells) and it threw StackOverflowError on OpenJDK 25 with the default thread stack; the limit is a JVM setting, so it differs by platform and by frame size. In an online assessment, or on a skewed tree, use an explicit ArrayDeque as a stack (or the queue above) and a loop. The island count above already does that. Python: the default recursion limit is about 1,000 frames (3.9.6).

Next stop: Pattern 7: topological sort, 5 min

Pattern 7: topological sort

Context. Think of the pairs as arrows in a directed graph. You can finish everything exactly when the graph has no cycle, because a cycle is a set of tasks each waiting on another.

Invariant. Everything popped had all its prerequisites popped before it.

Figure A6.6 draws four tasks with in-degrees 0, 1, 1 and 2, and the Kahn run beneath. The code returns the order the nodes were popped in, or null when a cycle blocks some of them.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Courses {
  /** Each pair is {course, prerequisite}. Returns an order, or null. */
  static int[] order(int n, int[][] prereqs) {
    int[] indeg = new int[n];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] p : prereqs) {
      adj.get(p[1]).add(p[0]);
      indeg[p[0]]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    int[] order = new int[n];
    int done = 0;
    while (!q.isEmpty()) {
      int v = q.poll();
      order[done++] = v;
      for (int w : adj.get(v)) if (--indeg[w] == 0) q.add(w);
    }
    return done == n ? order : null; // null means a cycle
  }
}

Cost. O(V + E) time and space, where V is the number of nodes and E the number of arrows: each node is queued once and each arrow is looked at once.

Hack sheet: topological sort

Worked: the alien dictionary, an order from sorted words

Problem. Words in an unknown alphabet arrive in that alphabet's sorted order. Return one order of the letters that agrees with the list, or "" if none can. Cue. "Sorted in an unknown order", "derive the alphabet". Idea. Two adjacent words give at most one rule: at their first differing position, the upper word's letter comes first. Each rule is an arrow, and a topological order of the letters that appear is an answer. Two cases have none. A word followed by its own proper prefix ("abc" before "ab") breaks every order. A cycle among the rules leaves letters never popped: the template's done != n test.

import java.util.ArrayDeque;
import java.util.Deque;

class Alien {
  /** A letter order under which the words are sorted, or "" if none.
   *  Words use 'a' to 'z'; every letter that appears is in the answer. */
  static String order(String[] words) {
    boolean[] used = new boolean[26];
    boolean[][] before = new boolean[26][26];    // before[u][v]: u < v
    int[] indeg = new int[26];
    for (String w : words)
      for (char c : w.toCharArray()) used[c - 'a'] = true;
    for (int i = 0; i + 1 < words.length; i++) {
      String a = words[i], b = words[i + 1];
      int k = 0, m = Math.min(a.length(), b.length());
      while (k < m && a.charAt(k) == b.charAt(k)) k++;
      if (k == m) {
        if (a.length() > b.length()) return "";  // "abc" before "ab"
        continue;                                // a prefix: no rule
      }
      int u = a.charAt(k) - 'a', v = b.charAt(k) - 'a';
      if (!before[u][v]) {                       // count an edge once
        before[u][v] = true;
        indeg[v]++;
      }
    }
    Deque<Integer> ready = new ArrayDeque<>();
    int letters = 0;
    for (int c = 0; c < 26; c++) {
      if (!used[c]) continue;
      letters++;
      if (indeg[c] == 0) ready.add(c);
    }
    StringBuilder out = new StringBuilder();
    while (!ready.isEmpty()) {
      int u = ready.poll();
      out.append((char) ('a' + u));
      for (int v = 0; v < 26; v++)
        if (before[u][v] && --indeg[v] == 0) ready.add(v);
    }
    return out.length() == letters ? out.toString() : "";  // a cycle
  }
}

Cost. O(C) to compare adjacent words, for C characters in all, plus O(26 x 26) for the arrow table, which is also the space. Trap. Only the first difference is a rule; later letters say nothing. Without the prefix check, ["abc", "ab"] returns "abc". With a table of arrows, count each arrow once: on ["ca", "cb", "da", "db"] the rule a before b appears twice, and counting it twice leaves b's in-degree stuck at 1, so the answer comes back "" instead of "acbd" (both mutants run on 2 Nov 2026). Letters in no rule still belong in the answer. Fallback that still scores: the three-colour DFS from the hack sheet, with the post-order reversed. If stuck: "Two adjacent sorted words tell me one thing, the first letter where they differ. That is an arrow, so this is a topological sort." The harness checked 5,000 random word lists, half sorted under a random hidden order, against every permutation of their letters: "" exactly when no order exists, and otherwise an order that sorts the list.

Next stop: Pattern 8: union-find (disjoint set), 4 min

Pattern 8: union-find (disjoint set)

Context. You could do a BFS from each unseen city, as in pattern 6. Union-find is the better tool when edges arrive one at a time, or when the question is "are these two already in the same group".

Invariant. Two cities are in the same group exactly when find gives them the same root; the group count equals the number of roots.

Union by size keeps trees flat, so three cities never form a chain: the smaller tree always hangs under the larger root. Four cities do give a two-step path. Figure A6.7 runs union(0, 1), union(2, 3), then union(0, 2): roots 1 and 3 both hold two cities, so the code keeps rb = 3 and sets parent[1] = 3, leaving 0 two steps from the root, parent = [1, 3, 3, 3]. One find(0) with path halving sets parent[0] = parent[1] = 3, giving [3, 3, 3, 3].

class DisjointSet {
  private final int[] parent, size;
  DisjointSet(int n) {
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
  }
  int find(int x) {
    while (parent[x] != x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  }
  /** Returns false if a and b were already in one group. */
  boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;
    if (size[ra] > size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[ra] = rb;           // smaller tree hangs under the larger
    size[rb] += size[ra];
    return true;
  }
}

class Provinces {
  static int count(int[][] isConnected) {
    int n = isConnected.length, comps = n;
    DisjointSet ds = new DisjointSet(n);
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
        if (isConnected[i][j] == 1 && ds.union(i, j)) comps--;
    return comps;
  }
}

Cost. With an edge list, O(E x alpha(n)) time, where alpha is the inverse Ackermann function, below 5 for any n you will ever meet, so treat it as constant. With the full matrix as here, scanning all pairs is itself O(n squared), so the total is O(n squared x alpha(n)); say that rather than "linear". O(n) space for parent.

Hack sheet: union-find

Next stop: Pattern 9: binary search on the answer, 2 min

Pattern 9: binary search on the answer

Context. The answer is a number in a known range (a speed from 1 up to the largest pile). Checking one candidate is easy: at speed s a pile of p takes ceil(p / s) hours, so add them up.

Invariant. The true answer is always within [lo, hi].

Figure A6.8 runs it for piles 3, 6, 7, 11 and 8 hours: four checks narrow the range from 1 to 11 down to a single speed, 4.

import java.util.function.IntPredicate;

class Speed {
  /** Smallest value in [lo, hi] with ok(value) true; ok is monotone. */
  static int minFeasible(int lo, int hi, IntPredicate ok) {
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (ok.test(mid)) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  }

  static int minSpeed(int[] piles, int h) {
    int max = 0;
    for (int p : piles) max = Math.max(max, p);
    return minFeasible(1, max, s -> {
      long hours = 0;
      for (int p : piles) hours += (p + s - 1) / s; // ceiling division
      return hours <= h;
    });
  }
}

Cost. Each check is O(n); there are about log2(M) checks for the largest pile M, so O(n log M) time and O(1) space. A linear scan of every speed would be O(n x M). "Find peak element" also uses a binary search, steered by comparing a value with its neighbour.

Hack sheet: binary search on the answer

Next stop: Pattern 10: heaps and k-way merge, 4 min

Pattern 10: heaps and k-way merge

Context. Sorting costs O(n log n) and gives you far more than you asked for. A heap is a tree stored in an array in which every parent is no larger (a min-heap) than its children, so the smallest item is always at the root, and inserting or removing costs O(log size).

Invariant. The heap holds the k largest items seen so far.

Figure A6.9 shows the heap after each item of the stream 3, 2, 1, 5, 6, 4 with k = 2. Java's PriorityQueue is a min-heap by default.

import java.util.PriorityQueue;

class KthLargest {
  static int find(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(); // k largest so far
    for (int x : nums) {
      heap.add(x);
      if (heap.size() > k) heap.poll();
    }
    return heap.peek();
  }
}

Cost. O(n log k) time and O(k) space, against O(n log n) for a full sort. When k is close to n there is no gain; when n is huge and k is 10 the heap is a clear win.

Hack sheet: heaps and k-way merge

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class MergeK {
  /** Merge sorted lists: heap entries are {value, list, position}. */
  static List<Integer> merge(List<List<Integer>> lists) {
    PriorityQueue<int[]> heap =
        new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    for (int i = 0; i < lists.size(); i++)
      if (!lists.get(i).isEmpty())
        heap.add(new int[] {lists.get(i).get(0), i, 0});
    List<Integer> out = new ArrayList<>();
    while (!heap.isEmpty()) {
      int[] top = heap.poll();
      out.add(top[0]);
      List<Integer> src = lists.get(top[1]);
      if (top[2] + 1 < src.size())
        heap.add(new int[] {src.get(top[2] + 1), top[1], top[2] + 1});
    }
    return out;
  }
}

On [[1, 4, 7], [2, 5], [3, 6]] it returns [1, 2, 3, 4, 5, 6, 7], and the Java run compares it with sorting the concatenation on seeded random inputs. Cost O(N log k) for N items in k lists.

Median of a stream: two heaps. A heap hands over only its extreme, so the median needs two: a max-heap low for the smaller half and a min-heap high for the larger half, kept within one item in size. The median is then the top of low (odd count) or the mean of the two tops (even count). Each add sends the new item through low to high and moves one back if high grew larger; that routing keeps every item of low at most every item of high.

import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
  private final PriorityQueue<Integer> low =
      new PriorityQueue<>(Collections.reverseOrder()); // smaller half
  private final PriorityQueue<Integer> high = new PriorityQueue<>();

  void add(int x) {
    low.add(x);
    high.add(low.poll());           // the top of the low half moves up
    if (high.size() > low.size()) low.add(high.poll());
  }

  double median() {
    return low.size() > high.size() ? low.peek()
        : (low.peek() + high.peek()) / 2.0;
  }
}

Stream 5, 2, 9: after 5, low holds [5] and the median is 5; 2 goes to low, 5 moves up, so low [2] and high [5] give 3.5; 9 goes to low, then to high, which now has two items to one, so 5 moves back and the median is 5 again. Cost O(log n) per add, O(1) per median, O(n) space. A sliding-window median needs deletions too; the usual route is lazy deletion in the same two heaps (named, not coded).

Next stop: Pattern 11: backtracking, 2 min

Pattern 11: backtracking

Context. When the answer is "all the ways to", there is no shortcut around producing them, but there is a disciplined way to do it. Build one candidate step by step.

Invariant. On entry to go() the path and the used marks describe the same partial candidate; on exit they are restored.

Figure A6.10 draws the tree for [1, 2, 3], with the branch under 1 expanded. The two leaves are the permutations [1, 2, 3] and [1, 3, 2]; the other two branches have the same shape.

import java.util.ArrayList;
import java.util.List;

class Perms {
  static List<List<Integer>> all(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    go(nums, new ArrayList<>(), new boolean[nums.length], out);
    return out;
  }

  private static void go(int[] nums, List<Integer> path, boolean[] used,
                         List<List<Integer>> out) {
    if (path.size() == nums.length) {
      out.add(new ArrayList<>(path)); // a copy, not the live path
      return;
    }
    for (int i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.add(nums[i]);
      go(nums, path, used, out);
      path.remove(path.size() - 1);
      used[i] = false;
    }
  }
}

Cost. n! results each of length n, so O(n x n!) time. For n = 3 that is 6 results and 18 numbers written; for n = 10 it is 3,628,800 results. That growth is why you ask about the input size before choosing this pattern. Space is O(n) for the recursion depth, plus the output.

Hack sheet: backtracking

import java.util.ArrayList;
import java.util.List;

class Subsets {
  static List<List<Integer>> all(int[] a) {
    List<List<Integer>> out = new ArrayList<>();
    pick(a, 0, new ArrayList<>(), out);
    return out;
  }

  private static void pick(int[] a, int i, List<Integer> path,
                           List<List<Integer>> out) {
    if (i == a.length) {
      out.add(new ArrayList<>(path));
      return;
    }
    pick(a, i + 1, path, out);           // skip a[i]
    path.add(a[i]);                      // take a[i]
    pick(a, i + 1, path, out);
    path.remove(path.size() - 1);        // undo
  }
}

The Java run checks that it returns 2^n distinct subsets for every n from 0 to 6.

Next stop: Pattern 12: dynamic programming, one-dimensional and two-dimensional, 5 min

Pattern 12: dynamic programming, one-dimensional and two-dimensional

Context. A dynamic-programming problem has two properties. The best answer for a big input is made from best answers for smaller inputs, and the same smaller inputs come up again and again in a naive recursion.

One-dimensional.

Invariant. When dp[x] is computed, every dp it reads is final.

import java.util.Arrays;

class Coins {
  static int change(int[] coins, int amount) {
    int inf = amount + 1;               // larger than any real answer
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, inf);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
      for (int c : coins)
        if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
    return dp[amount] == inf ? -1 : dp[amount];
  }
}

One-dimensional cost: O(amount x number of coins) time, O(amount) space. Coin change is a standard problem in the public study plans; "house robber" has the same shape with a different choice at each step.

Two-dimensional.

Invariant. Row i is filled from row i - 1 and from earlier cells of row i only.

For the strings "abcde" and "ace" the table has six rows and four columns (the extra row and column are the empty prefix), 24 cells in all, and three cells where a letter matches; the drawn table is in another section of this appendix.

import java.util.Arrays;

class Lcs {
  static int table(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
      for (int j = 1; j <= n; j++)
        dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
            ? dp[i - 1][j - 1] + 1
            : Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
  }

  /** The same table rolled into one row of b.length() + 1 cells. */
  static int rolled(String a, String b) {
    int[] row = new int[b.length() + 1];   // row[j] is dp[i][j]
    for (int i = 1; i <= a.length(); i++) {
      int diag = 0;                        // dp[i - 1][j - 1]
      for (int j = 1; j <= b.length(); j++) {
        int up = row[j];                   // dp[i - 1][j], about to go
        row[j] = a.charAt(i - 1) == b.charAt(j - 1)
            ? diag + 1
            : Math.max(up, row[j - 1]);    // row[j - 1] is dp[i][j - 1]
        diag = up;
      }
    }
    return row[b.length()];
  }

  /** The same answer top-down: plain recursion plus a memo table. */
  static int memo(String a, String b) {
    int[][] memo = new int[a.length() + 1][b.length() + 1];
    for (int[] row : memo) Arrays.fill(row, -1);
    return best(a, b, 0, 0, memo);
  }

  private static int best(String a, String b, int i, int j, int[][] memo) {
    if (i == a.length() || j == b.length()) return 0;
    if (memo[i][j] >= 0) return memo[i][j];
    int r = a.charAt(i) == b.charAt(j)
        ? 1 + best(a, b, i + 1, j + 1, memo)
        : Math.max(best(a, b, i + 1, j, memo), best(a, b, i, j + 1, memo));
    return memo[i][j] = r;
  }
}

Two-dimensional cost: O(m x n) time and space for strings of lengths m and n (here 5 x 3 = 15 cells of work); rolled keeps one row of the table plus the old diagonal cell in a variable, so passing the shorter string as b cuts the space to O(min(m, n)) with the same O(m x n) time. The trap in rolling is overwriting dp[i - 1][j - 1] before it is read, which is why diag is saved from up after each cell. The harness ran all three methods against each other on 5,000 random pairs of strings over a, b and c up to eight letters, and checked abcde and ace (3) and the empty string (0), on 2 Nov 2026.

Hack sheet: dynamic programming

The memoised-recursion shortcut. The Lcs class above also carries the top-down form: the plain recursion over (i, j) plus an int[][] memo filled with -1, so the recursion becomes the table without writing the table; it agrees with the table version in the Java run. Python: @functools.cache does the same in one line.

More families. The longest increasing subsequence, the 0/1 knapsack, edit distance and buy-sell-with-cooldown, each with the answer rebuilt and checked against a brute force, are worked in another section of this appendix. The hack sheet above covers all four: name the state in one sentence, write the recursion, then the table, then rebuild the items by walking the table back.

Next stop: Pattern 13: tries (prefix trees), 2 min

Pattern 13: tries (prefix trees)

Context. A list of words answers a prefix question by scanning every word. A trie spends memory to make each prefix a place: one node per distinct prefix, each node holding its children keyed by the next letter.

Invariant. The path from the root to a node spells exactly one prefix; the marker is on exactly the nodes that spell stored words.

Figure A6.11 stores "apple", "app" and "bat". The nodes for "app" and "apple" are on one path, so the ring on the second p says "app" is a stored word while the continuing path says it is also a prefix.

class Trie {
  private final Trie[] next = new Trie[26];
  private boolean isWord;

  void insert(String word) {
    Trie node = this;
    for (char ch : word.toCharArray()) {
      if (node.next[ch - 'a'] == null) node.next[ch - 'a'] = new Trie();
      node = node.next[ch - 'a'];
    }
    node.isWord = true;                  // end-of-word marker
  }

  private Trie walk(String s) {
    Trie node = this;
    for (char ch : s.toCharArray()) {
      node = node.next[ch - 'a'];
      if (node == null) return null;
    }
    return node;
  }

  boolean search(String word) {
    Trie node = walk(word);
    return node != null && node.isWord;
  }

  boolean startsWith(String prefix) {
    return walk(prefix) != null;
  }
}

Cost. O(L) per insert, search or prefix query for a word of length L, independent of how many words are stored; O(total characters) space in the worst case, less when prefixes are shared.

Hack sheet: tries

Next stop: Pattern 14: bit tricks, 2 min

Pattern 14: bit tricks

Context. The hash-map baseline counts every number: O(n) time and O(n) space. Bits give a shortcut.

Invariant. After each step x is the XOR of everything read so far.

class Bits {
  static int single(int[] nums) {
    int x = 0;
    for (int n : nums) x ^= n;           // equal pairs cancel
    return x;
  }

  static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;  // parentheses: == binds tighter
  }
}

Cost. O(n) time, O(1) space.

Hack sheet: bit tricks

Next stop: Pattern 15: shortest paths with weights (Dijkstra, 0-1 BFS, k stops), 5 min

Pattern 15: shortest paths with weights (Dijkstra, 0-1 BFS, k stops)

Context. Breadth-first search finds the fewest edges, which is the cheapest path only when every edge costs the same. Once edges carry costs (minutes, rupees, effort), the fewest-edge path can be the dearest. Dijkstra's idea is to settle nodes in order of their best known distance: the closest unsettled node cannot be improved, because every other route to it starts from a node that is at least as far. That argument fails as soon as an edge cost is negative.

Invariant. When a node comes off the heap with an up-to-date distance, that distance is final.

Figure A6.12 runs it from node 0: node 2 is reached at 1 and improves node 1 from 4 to 3; node 1 then improves node 3 from 6 to 4. The stale heap entries (node 1 at 4, node 3 at 6) are skipped when they come up, because their distance is larger than the stored one. Final distances: 0, 3, 1, 4. The code has three methods: Dijkstra with a lazy-deletion heap, 0-1 BFS, and the fewest-stops variant.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.PriorityQueue;

class Paths {
  /** Edges are {from, to, weight}, weights >= 0. MAX_VALUE = unreachable. */
  static long[] dijkstra(int n, int[][] edges, int src) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]});
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.add(new long[] {0, src});               // {distance, node}
    while (!pq.isEmpty()) {
      long[] top = pq.poll();
      int u = (int) top[1];
      if (top[0] > dist[u]) continue;          // stale entry: skip
      for (int[] e : adj.get(u)) {
        long nd = top[0] + e[1];
        if (nd < dist[e[0]]) {
          dist[e[0]] = nd;
          pq.add(new long[] {nd, e[0]});
        }
      }
    }
    return dist;
  }

  /** Weights are only 0 or 1: a deque replaces the heap, O(V + E). */
  static int[] zeroOne(int n, int[][] edges, int src) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]});
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    Deque<Integer> dq = new ArrayDeque<>();
    dq.add(src);
    while (!dq.isEmpty()) {
      int u = dq.pollFirst();
      for (int[] e : adj.get(u)) {
        if (dist[u] + e[1] < dist[e[0]]) {
          dist[e[0]] = dist[u] + e[1];
          if (e[1] == 0) dq.addFirst(e[0]);    // free: front
          else dq.addLast(e[0]);
        }
      }
    }
    return dist;
  }

  /** Cheapest price from src to dst with at most k stops (k + 1 edges). */
  static int cheapest(int n, int[][] edges, int src, int dst, int k) {
    long inf = Long.MAX_VALUE / 2;
    long[] dist = new long[n];
    Arrays.fill(dist, inf);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {
      long[] next = dist.clone();              // read old, write new
      for (int[] e : edges)
        if (dist[e[0]] + e[2] < next[e[1]]) next[e[1]] = dist[e[0]] + e[2];
      dist = next;
    }
    return dist[dst] >= inf ? -1 : (int) dist[dst];
  }
}

0-1 BFS. When every edge costs 0 or 1, a deque replaces the heap: a free edge puts the neighbour at the front of the line, a costly one at the back, so the deque is always ordered by distance and the whole run is O(V + E). On edges 0 to 1 (cost 1), 0 to 2 (cost 0), 2 to 1 (cost 0) and 1 to 3 (cost 1), node 1 is reached free through node 2, and node 3 costs 1.

At most k stops. Plain Dijkstra is wrong here: the cheapest route to a node may have used up its stops, and keeping only that route throws away a dearer one that still has stops left. Instead, run k + 1 rounds; in each round every edge is relaxed against the distances from the round before, which is why the code relaxes into a copy. Without the copy, one round could chain several edges and the stop count would be wrong. With flights 0 to 1 (100), 1 to 2 (100) and 0 to 2 (500), the cheapest route from 0 to 2 costs 500 with no stops and 200 with one.

Cost. Dijkstra is O((V + E) log V) time and O(V + E) space: each edge pushes at most once. 0-1 BFS is O(V + E). The k-stop rounds cost O(k x E) time and O(V) space. Sums can pass an int, so distances are long in the Dijkstra method.

Hack sheet: shortest paths

Next stop: Pattern 16: sweep line, 4 min

Pattern 16: sweep line

Context. "How many meetings are on at once" or "the busiest hour" asks about overlap, not about merging. Comparing every pair is quadratic. The shift is to stop treating an interval as one object: it is two events, a start that adds one and an end that subtracts one. Sort the events, walk them once, and the running count is the number of intervals covering the current point.

Invariant. The running count equals the number of intervals that have started and not yet ended.

The first method sorts the starts and the ends separately, which gives the same sweep without building event objects. At each start, every meeting that has already ended is released first, so a meeting that ends at 10 and another that starts at 10 share a room (the <=). Ask the interviewer whether touching meetings overlap; the answer flips that one character. The second class is the online form: bookings arrive one at a time, and a TreeMap of deltas keeps them in time order.

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

class Sweep {
  /** Most meetings running at once: sort starts and ends separately. */
  static int minRooms(int[][] meetings) {
    int n = meetings.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) {
      starts[i] = meetings[i][0];
      ends[i] = meetings[i][1];
    }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int rooms = 0, best = 0, e = 0;
    for (int s = 0; s < n; s++) {
      while (e < n && ends[e] <= starts[s]) { // free by this start
        e++;
        rooms--;
      }
      rooms++;
      best = Math.max(best, rooms);
    }
    return best;
  }
}

/** Online: bookings arrive one at a time; +1 at a start, -1 at an end. */
class Calendar {
  private final TreeMap<Integer, Integer> delta = new TreeMap<>();

  /** End is exclusive; returns the largest overlap so far. */
  int book(int start, int end) {
    delta.merge(start, 1, Integer::sum);
    delta.merge(end, -1, Integer::sum);
    int running = 0, best = 0;
    for (Map.Entry<Integer, Integer> e : delta.entrySet()) {
      running += e.getValue();
      best = Math.max(best, running);
    }
    return best;
  }
}

A zero-length meeting such as [5, 5] occupies no room, so it adds nothing to the count (without the e < n test the loop would walk off the end of ends). With several zero-length meetings at one time, rooms can dip below zero, because each one's end is consumed before its own start is counted. The maximum is still right: within a run of equal starts the count only rises, and after the last of them it equals the meetings running at that moment (checked against a brute force on 20,000 random sets, zero-length meetings included). For meetings [[0, 30], [5, 10], [15, 20]] the starts are 0, 5, 15 and the ends 10, 20, 30: the count rises to 2 at 5, falls to 1 at 10, and is 2 again at 15, so two rooms. For [[7, 10], [2, 4]] it never passes 1. In Calendar, booking [10, 20), then [15, 25), then [20, 30) returns 1, 2, 2.

Cost. The two sorts are O(n log n); the sweep is O(n); space is O(n). Calendar.book rewalks the whole map, so it is O(n) per booking and O(n squared) over n bookings; a segment tree with lazy updates (named, not coded) makes each booking O(log n). If the online question is only yes or no (accept a booking when it overlaps nothing already booked), Booker in lesson 6 answers each one in O(log n) with floorEntry and ceilingEntry (Figure A6.16); a count of overlaps still needs the segment tree.

Hack sheet: sweep line

Next stop: Pattern 17: Fenwick tree and segment tree, 2 min

Pattern 17: Fenwick tree and segment tree

Context. Prefix sums (pattern 3) answer "sum of a range" in O(1) from a table built once. Change one number and the table is wrong from that position to the end, so a rebuild costs O(n). When updates and queries are mixed, both need to be O(log n). A Fenwick tree does that for sums with very little code. A segment tree does it for any associative combine (minimum, maximum, greatest common divisor) at a little more code.

Invariant. Fenwick: tree[i] holds the sum of the i & -i elements that end at position i (counting from 1). Segment tree: each node holds the combine of its two children, and the leaves are the array.

The two listings (Fenwick and MinSegTree), the segment-tree figure and a worked run are in another section of this appendix. This pattern is recognise and explain only, and the hack sheet below carries both templates.

Cost. Each update or query is O(log n). Building the segment tree is O(n); building the Fenwick tree with n calls to add, as the appendix listing does, is O(n log n). Space is O(n). A change that touches a whole range (add 5 to positions 3 to 9) needs lazy propagation (named, not coded).

Hack sheet: Fenwick and segment trees

Next stop: Pattern 18: quickselect, 3 min

Pattern 18: quickselect

Context. Pattern 10 finds the k-th largest in O(n log k) with a heap. If you only need the one value, you can do better on average, by borrowing the partition step of quicksort: choose a pivot, move the smaller values to its left, and see where the pivot lands. If it lands at position k, you are done; if it lands left of k, the answer is in the right part; otherwise in the left. Only one side is ever searched, so the work halves each time on average: n + n/2 + n/4 and so on, about 2n.

Invariant. The target position always lies inside [lo, hi], and everything left of lo is no larger than everything inside.

The code returns the k-th smallest, counting k from 1 (the k-th largest is the (n - k + 1)-th smallest). It works on a copy, because partitioning reorders the array, and it picks a random pivot so that no fixed input is the worst case.

import java.util.Random;

class Select {
  private static final java.util.Random RNG = new java.util.Random();

  /** k-th smallest (k from 1), average O(n); works on a copy. */
  static int kthSmallest(int[] nums, int k) {
    int[] a = nums.clone();
    int lo = 0, hi = a.length - 1, target = k - 1;
    while (lo < hi) {
      int p = partition(a, lo, hi);
      if (p == target) return a[p];
      if (p < target) lo = p + 1;
      else hi = p - 1;
    }
    return a[lo];
  }

  private static int partition(int[] a, int lo, int hi) {
    swap(a, lo + RNG.nextInt(hi - lo + 1), hi); // random pivot to the end
    int pivot = a[hi], store = lo;
    for (int i = lo; i < hi; i++)
      if (a[i] < pivot) swap(a, i, store++);
    swap(a, store, hi);
    return store;
  }

  private static void swap(int[] a, int i, int j) {
    int t = a[i]; a[i] = a[j]; a[j] = t;
  }
}

On [3, 2, 1, 5, 6, 4], k = 2 returns 2 and k = 5 returns 5 (the second largest). The Java run compares it with sorting on seeded random arrays.

Cost. O(n) on average, O(n squared) in the worst case, and O(n) extra space for the copy. The simple partition used here slows on many equal values: with 60,000 equal values and k = 30,000 it took about 327 ms on the author's laptop against about 1 ms on random data. The cure is a three-way partition (less than, equal to, greater than the pivot), named here and not coded. A worst-case O(n) exists (median of medians) and is rarely worth writing in a round.

Hack sheet: quickselect

Next stop: Complexity at a glance, 1 min

Complexity at a glance

Context. Time and space here are derived by the author from the code above (the standard analysis, not a measurement on a machine). Costs of the lesson's methods:

Worked arithmetic. For n = 100,000 a quadratic method does 10,000,000,000 basic steps; an n log n method does about 1,660,964 (log2 of 100,000 is about 16.61), roughly 6,000 times fewer; a linear method does 100,000. The author's reading, not a measurement, is that a machine does tens to hundreds of millions of simple operations a second, fewer in an interpreted language: 10 billion steps is out of reach, under two million is comfortable. Factorial growth is a harder cliff: n = 10 gives 3,628,800 permutations, and n = 20 is hopeless. When you state a complexity, derive it loop by loop: the stack and the window both have an inner loop that looks quadratic and is not, because the inner pointer never goes backward.

Next stop: Choosing between neighbours, 2 min

Choosing between neighbours

Context. Several patterns answer questions with similar wording. The deciding facts are usually one property of the input or one property of the answer, and you can ask the interviewer about either. The table lists the commonest confusions with the question that separates them. It is the author's own guide, built from the cues above.

Next stop: Closing the gaps: greedy scheduling and a count-min sketch, 4 min

Closing the gaps: greedy scheduling and a count-min sketch

Greedy: interval scheduling and the exchange argument

A greedy answer is only as good as its proof, and an interviewer will ask. The question: the most meetings one room can host. Sort by end time and take each meeting that starts at or after the last taken end.

import java.util.Arrays;

class Greedy {
  /** Most meetings one room can host; touching ends are fine. */
  static int maxMeetings(int[][] iv) {
    int[][] s = iv.clone();
    Arrays.sort(s, (p, q) -> p[1] != q[1]       // earliest end first,
        ? Integer.compare(p[1], q[1])        // then earliest start
        : Integer.compare(p[0], q[0]));
    int count = 0, lastEnd = Integer.MIN_VALUE;
    for (int[] m : s) {
      if (m[0] >= lastEnd) {
        count++;
        lastEnd = m[1];
      }
    }
    return count;
  }
}

Why it is correct (exchange argument). Take any best schedule. Its first meeting ends no earlier than the meeting that ends first overall. Swap that first meeting for the earliest-ending one: it still fits before the second meeting, because it ends no later. The schedule is no worse. Repeat on what remains. So some best schedule begins with the greedy choice. Sorting by start time or by shortest length fails: one long meeting can block many short ones, and a short one can sit in the middle of two others that would both fit. The harness checks the rule against a brute force over every subset of up to eight meetings, 3,000 times. Sorting makes it O(n log n). One consistency note with the sweep in Pattern 16: there a zero-length meeting such as [5, 5] needs no room, so it never raises the room count; here it counts as one meeting you can attend, because it starts at or after the last end and sets the new end to the same time. The two are different questions (rooms needed against meetings attended), and both are right; ask whether a zero-length meeting is a meeting. The tie-break on start matters only for zero-length meetings: with [3, 5] and [5, 5] ending together, taking [5, 5] first would block [3, 5]; start order takes both. The harness checks the rule on touching and zero-length cases too, 5,000 random cases against every subset.

Other greedy questions follow the same two steps: pick the sort key, then give the swap argument in three sentences. Task scheduler and jump game are both of this kind; if you cannot produce the swap, you may have a heuristic, not a greedy.

Count-min sketch: top-k on a stream you cannot store

For top-k words on a 50 GB stream, Pattern 10's hack sheet keeps a heap per shard and merges the shard heaps, which still needs each shard's table of counts. When even that table will not fit, a count-min sketch keeps a small grid of counters: depth rows, width columns, one hash per row. Adding a key bumps one counter in each row; the estimate is the smallest of its counters. Collisions only add, so the estimate is never below the true count. The sizing rule, from the author's memory of Cormode and Muthukrishnan (2005), which was not re-read: width about e divided by epsilon and depth about ln of 1 divided by delta give an overcount of at most epsilon times the stream length N with probability at least 1 minus delta. Treat that as secondary: Wikipedia's count-min article gives the same width and depth (read 1 Nov 2026), but the paper itself could not be opened.

class CMS {
  private final int[][] t;
  private final int w;
  private final long[] seed;

  CMS(int depth, int width) {
    t = new int[depth][width];
    w = width;
    seed = new long[depth];
    for (int i = 0; i < depth; i++) seed[i] = 0x9E3779B97F4A7C15L * (i + 1);
  }

  private int slot(String key, int row) {
    long h = key.hashCode() * 0xFF51AFD7ED558CCDL + seed[row];
    h ^= h >>> 33; h *= 0xC4CEB9FE1A85EC53L; h ^= h >>> 33;
    return (int) Math.floorMod(h, (long) w);
  }

  void add(String key) {
    for (int i = 0; i < t.length; i++) t[i][slot(key, i)]++;
  }

  int estimate(String key) {            // never below the true count
    int m = Integer.MAX_VALUE;
    for (int i = 0; i < t.length; i++) m = Math.min(m, t[i][slot(key, i)]);
    return m;
  }
}

The harness builds a skewed 20,000-item stream with 1,157 distinct keys at depth 4 and width 272 (about epsilon 0.01), asserts that no key is ever undercounted, and that fewer than one key in twenty is over by more than 0.01 times N. It printed keys 1157 over eps*N 0. For top-k keep a small heap of k candidates beside the sketch and compare each new estimate with the heap's smallest. Say what it cannot do: it cannot list the keys, delete, or give exact counts.

Next stop: Tests, naming, and changing code under a follow-up, 1 min

Tests, naming, and changing code under a follow-up

Four habits show in every answer that reads as senior, and each costs under a minute. First, name tests as sentences before writing them: "single task", "cycle", "ties". Second, write the check as a small function that throws, as the harnesses in this lesson do, so you can run it again after each change. Third, when a requirement changes, edit the smallest part and say which invariant still holds; the transcript above did this with the worker cap and the changed duration. Fourth, rename a variable the moment you misread it; from reads better than p and costs five seconds. Interviewers cannot see a plan that was not said, so say it. Figure A6.15 puts the two time budgets of lesson 6 side by side: one problem, and two problems in the same 45 minutes.

Next stop: Two follow-ups the earlier parts only named, 3 min

Two follow-ups the earlier parts only named

Islands II: land arrives one cell at a time

Counting islands with a flood fill after each added cell costs the whole grid every time. A new cell is either on already-land (no change), or it starts one island and merges with up to four neighbours. Union-find gives the count directly: add one for the new cell, subtract one for every union that joins two different islands. Pattern 8's union-find, with path halving, is reused.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Islands2 {
  private static int find(int[] p, int x) {
    while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; }   // path halving
    return x;
  }

  /** Island count after each land cell is added; repeats are harmless. */
  static List<Integer> counts(int h, int w, int[][] adds) {
    int[] p = new int[h * w];
    Arrays.fill(p, -1);                       // -1 means still water
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int islands = 0;
    List<Integer> out = new ArrayList<>();
    for (int[] a : adds) {
      if (a[0] < 0 || a[0] >= h || a[1] < 0 || a[1] >= w)
        throw new IllegalArgumentException("cell off the grid");
      int id = a[0] * w + a[1];
      if (p[id] == -1) {
        p[id] = id;
        islands++;                            // new island, then merge
        for (int[] d : dirs) {
          int r = a[0] + d[0], c = a[1] + d[1];
          if (r < 0 || c < 0 || r >= h || c >= w || p[r * w + c] == -1)
            continue;
          int x = find(p, id), y = find(p, r * w + c);
          if (x != y) { p[x] = y; islands--; }
        }
      }
      out.add(islands);
    }
    return out;
  }
}

The harness replays 2,000 random sequences (with repeated cells) against a fresh flood fill after every step, and checks the sample: on a 3 by 3 grid, adding (0,0), (0,1), (1,2), (2,1), (1,1) gives 1, 1, 2, 3, 1. Cost: m additions in O(m log n) at worst with path halving alone (the bound Pattern 8 states), which is near linear in practice. The follow-up "a cell can turn back into water" breaks the structure, since union-find cannot split a set. The honest answers: if all the operations are known in advance, process them backwards so removals become additions (offline); online, either rebuild from the grid for each removal, or use union-find with rollback when removals undo the latest additions in order. Name these; do not code them unless asked.

Online booking: a sorted map with floor and ceiling

Pattern 16 counted overlaps, and its Calendar.book rewalks the whole map, O(n) per booking. A different question: accept a booking only if it overlaps nothing already accepted, and answer each one as it arrives. Keep the accepted bookings in a sorted map keyed by start. A new booking [s, e) can only clash with the booking that starts at or before s (does it run past s?) or the booking that starts at or after s (does it start before e?). Those two neighbours come from floorEntry and ceilingEntry, each O(log n) in the Java documentation's words for TreeMap, so a booking is O(log n) where a list scan is O(n). Figure A6.16 draws the two checks.

import java.util.TreeMap;

class Booker {
  private final TreeMap<Integer, Integer> byStart = new TreeMap<>();

  /** Half-open [s, e). True and stored if it overlaps nothing booked. */
  boolean book(int s, int e) {
    if (s >= e) return false;                    // empty or backwards
    var before = byStart.floorEntry(s);          // last start <= s
    if (before != null && before.getValue() > s) return false;
    var after = byStart.ceilingEntry(s);         // first start >= s
    if (after != null && after.getKey() < e) return false;
    byStart.put(s, e);
    return true;
  }
}

The harness compares 3,000 random sequences of twelve bookings with a linear scan, and checks the touching case (10 to 20, then 20 to 30 is accepted; the one in between is not) and the empty booking. The rule on empty and backwards bookings (rejected here) is a question for the interviewer, as the zero-length note under Greedy says. Do not confuse this with the sweep: the sweep tells you how many rooms a known list needs; this decides yes or no online.

Next stop: A vague prompt and parsing, 5 min

A vague prompt and parsing

When the prompt is vague: five numbers and the assumptions you state

Parsing prompts arrive short. The senior move is to convert the sentence into limits before any code, and to say the assumptions aloud so a wrong one can be corrected in ten seconds rather than twenty minutes.

Asked to "write a calculator", ask five things in one breath: which operators, brackets and nesting, whole numbers or decimals and how big, what bad input should do, and how long the input is. Then state your assumptions before any code (here: division truncates toward zero; overflow and division by zero are errors; spaces allowed) and the design they lead to: a tokenizer, then one parsing function per precedence level. Asking takes about a minute; a wrong guess costs a rewrite. An invented dialogue of this exchange is in another section of this appendix.

Tokenizer and recursive-descent calculator

Brute force here is not a loop; it is the wrong shape. Scanning for the lowest-precedence operator and splitting works but rescans the string at every level, O(n squared) on deep nesting, and handles unary minus badly. The shape that works is a grammar with one function per level: expr calls term, term calls unary, and unary calls expr again inside brackets. Each function reads the level below it and loops on its own operators, which gives left-to-right grouping: 10-4-3 is 3, not 9.

The tokens carry their position, so an error can say where. Every arithmetic step uses the Exact methods, which throw ArithmeticException on overflow instead of wrapping (Oracle, Java SE 21 API, opened 2 Nov 2026). The one trap in the lexer is a number such as 99999999999999999999, which overflows while it is being read, so the digit loop uses them too. Division needs its own: v / r does not throw on Long.MIN_VALUE divided by -1, it returns Long.MIN_VALUE, and the Math page says so in those words, so plain v / r would break the overflow rule; Math.divideExact, which the page marks "Since: 18", throws instead. The lexer also tests digits with a plain '0' to '9' range: Character.isDigit accepts digits from other scripts, and for the Arabic-Indic one c - '0' is 1585, so a lexer using it reads that character as the number 1585 instead of rejecting it as a bad character (checked in the run on 2 Nov 2026).

import java.util.ArrayList;
import java.util.List;

class Calc {
  enum Kind { NUM, PLUS, MINUS, STAR, SLASH, LP, RP }
  record Tok(Kind kind, long value, int pos) {}

  static boolean digit(char c) { return c >= '0' && c <= '9'; } // ASCII

  static List<Tok> lex(String s) {
    List<Tok> out = new ArrayList<>();
    int i = 0;
    while (i < s.length()) {
      char c = s.charAt(i);
      if (c == ' ') { i++; continue; }
      if (digit(c)) {
        int start = i;
        long v = 0;
        while (i < s.length() && digit(s.charAt(i))) {
          v = Math.addExact(Math.multiplyExact(v, 10L), s.charAt(i++) - '0');
        }
        out.add(new Tok(Kind.NUM, v, start));
        continue;
      }
      Kind k = switch (c) {
        case '+' -> Kind.PLUS;
        case '-' -> Kind.MINUS;
        case '*' -> Kind.STAR;
        case '/' -> Kind.SLASH;
        case '(' -> Kind.LP;
        case ')' -> Kind.RP;
        default -> throw new IllegalArgumentException("bad char at " + i);
      };
      out.add(new Tok(k, 0, i++));
    }
    return out;
  }

  // expr = term (('+'|'-') term)*   term = unary (('*'|'/') unary)*
  // unary = '-' unary | '(' expr ')' | NUM
  private final List<Tok> t;
  private int p = 0;
  private Calc(List<Tok> t) { this.t = t; }

  static long eval(String s) {
    Calc c = new Calc(lex(s));
    long v = c.expr();
    if (c.p != c.t.size())
      throw new IllegalArgumentException("junk at token " + c.p);
    return v;
  }

  private boolean at(Kind k) { return p < t.size() && t.get(p).kind() == k; }

  private long expr() {
    long v = term();
    while (at(Kind.PLUS) || at(Kind.MINUS)) {
      boolean plus = t.get(p++).kind() == Kind.PLUS;
      long r = term();
      v = plus ? Math.addExact(v, r) : Math.subtractExact(v, r);
    }
    return v;
  }

  private long term() {
    long v = unary();
    while (at(Kind.STAR) || at(Kind.SLASH)) {
      boolean mul = t.get(p++).kind() == Kind.STAR;
      long r = unary();
      if (!mul && r == 0) throw new ArithmeticException("divide by zero");
      // divideExact (Java 18+) throws on Long.MIN_VALUE / -1; v / r wraps
      v = mul ? Math.multiplyExact(v, r) : Math.divideExact(v, r);
    }
    return v;
  }

  private long unary() {
    if (at(Kind.MINUS)) { p++; return Math.negateExact(unary()); }
    if (at(Kind.LP)) {
      p++;
      long v = expr();
      if (!at(Kind.RP)) throw new IllegalArgumentException("missing )");
      p++;
      return v;
    }
    if (at(Kind.NUM)) return t.get(p++).value();
    throw new IllegalArgumentException("expected a number at token " + p);
  }
  // main and the test helpers are in the file that was run
}

Results from the file that was run: 1+2*3 is 7; (1+2)*3 is 9; -(2+3)*-4 is 20; 10-4-3 is 3; 100/7/2 is 7; --5 is 5; 7/-2 is -3. Eleven malformed inputs are rejected: nine ordinary ones (empty, 1+, (1, 1), 2 3, 1/0, a letter, a leading star, and the 20-digit number), plus (0-9223372036854775807-1)/-1, which is Long.MIN_VALUE divided by -1, and an Arabic-Indic digit one followed by +1. The bracket (0-9223372036854775807-1) on its own still evaluates to Long.MIN_VALUE. A further 20,000 random expressions were checked against a BigInteger evaluator (details in this appendix).

Cost. Lexing and parsing are one pass each, O(n) time. Space is O(n) for the token list, plus recursion depth equal to the bracket nesting; a line of 100,000 open brackets would overflow the stack, which is one sentence to say aloud and a reason to ask "short lines". An explicit-stack version (shunting-yard) removes that limit.

A dry run with no execution

Some rounds score a dry run: trace the code by hand without executing it. The habit is cheap. Drill: write your list reverse (drill 1) on paper, trace it on 1, 2, 3 with a column of three values per step (prev, head, next) and say the final list before you type. Do the same for your window maximum (drill 9) on [1, 3, -1, -3, 5] with k = 3: the deque of indexes after each step is [0], [1], [1, 2], [1, 2, 3], [4], and the output is 3, 3, 5. If your trace and your code disagree, the code is wrong about half the time and the trace the rest, which is why you do it twice.

Next stop: A question bank: common types the patterns did not solve, 6 min

A question bank: common types the patterns did not solve

Eleven common question types were named earlier in this lesson, or asked often enough to need one, but not solved by a pattern section. Two are worked here: grid paths, and reservoir sampling after it. The other nine are worked in full in another section of this appendix, each with a listing compiled and run with java --source 21 on 2 Nov 2026 against a brute force on random inputs; the table keeps the idea and the trap of each. An LRU cache is in the next section (and with threads in lesson 7), and partition into equal subsets is Pattern 12's knapsack asking whether half the total is reachable.

Grid paths: minimum sum and counting

Cue. A grid, moves only right or down, and "minimum path sum", "number of paths" or "with obstacles". Idea. A cell's best cost is its own cost plus the better of the cell above and the cell to its left. Row i needs only row i - 1 and the cell just filled to its left, so one row of the table is enough, as in Lcs.rolled.

class GridPath {
  /** Cheapest top-left to bottom-right path, moving right or down.
   *  One row of the table is kept; grid is non-empty. */
  static long minPathSum(int[][] g) {
    int n = g[0].length;
    long[] row = new long[n];             // row[j]: best cost into (i, j)
    for (int i = 0; i < g.length; i++) {
      for (int j = 0; j < n; j++) {
        long best;
        if (i == 0 && j == 0) best = 0;
        else if (i == 0) best = row[j - 1];        // only from the left
        else if (j == 0) best = row[j];            // only from above
        else best = Math.min(row[j], row[j - 1]);  // above or left
        row[j] = best + g[i][j];
      }
    }
    return row[n - 1];
  }

  /** Paths through an m by n grid, right or down; exact to 34 x 34. */
  static long uniquePaths(int m, int n) {
    long[] row = new long[n];
    java.util.Arrays.fill(row, 1);       // the first row: one way each
    for (int i = 1; i < m; i++)
      for (int j = 1; j < n; j++)
        row[j] = Math.addExact(row[j], row[j - 1]);  // throws, no wrap
    return row[n - 1];
  }
}

Cost. O(R x C) time, O(C) space. The harness compared both methods with plain recursion on 3,000 random grids up to 4 by 4, and checked uniquePaths(34, 34) as 7,219,428,434,016,265,740, which still fits in a long. From 35 by 35 the count passes Long.MAX_VALUE, and Math.addExact throws ArithmeticException instead of wrapping to a wrong number, the lesson's overflow rule; the harness checks that 35 by 35 is the first square that throws. Fallback: the full table, or the memoised recursion of Pattern 12. Trap: the first row and first column have one neighbour each; with obstacles, a blocked cell sets row[j] = 0 when counting; and an int count overflows from 18 by 18 on (2,333,606,220 paths, in the same run).

Gave up / revisit when / signal (grid paths). Gave up: moves in all four directions, where cycles remove any fill order and the problem becomes Dijkstra (Pattern 15). Revisit when: diagonal or four-way moves, or negative cells. Signal: the candidate named the fill order and why one row is enough.

Reservoir sampling: k items from a stream of unknown length

Cue. "Pick k at random", "uniformly", and a stream or a list too long to store or count first. Idea. Keep the first k items. For item i (counting from 1) with i > k, draw j uniformly from 0 to i - 1; if j < k, item i replaces slot j. Why it is uniform, in two lines. Item i enters with chance k/i, and a later step j evicts it only by landing on its slot, chance (k/j)(1/k) = 1/j. So it ends in the sample with chance (k/i) x (i/(i + 1)) x ... x ((n - 1)/n) = k/n; the first k items enter with chance 1 and the product from k + 1 gives k/n too.

import java.util.Iterator;
import java.util.Random;

class Reservoir {
  /** k items, uniform over a stream of unknown length n >= k. */
  static int[] sample(Iterator<Integer> stream, int k, Random rnd) {
    int[] keep = new int[k];
    int seen = 0;
    while (stream.hasNext()) {
      int x = stream.next();
      seen++;
      if (seen <= k) {
        keep[seen - 1] = x;                // the first k go in
      } else {
        int j = rnd.nextInt(seen);         // 0 to seen - 1
        if (j < k) keep[j] = x;            // in with chance k / seen
      }
    }
    if (seen < k) throw new IllegalArgumentException("fewer than k");
    return keep;
  }
}

Cost. O(n) time, one random draw per item after the first k; O(k) space. Trap. Drawing one short, from 0 to i - 2 (nextInt(seen - 1)): in the same 200,000 seeded runs the first three values were picked about 44,000 to 44,600 times each instead of 60,000 (a mutant, run on 2 Nov 2026). Fallback that still scores: give each item a random key and keep the k smallest keys in a heap of size k (Pattern 10): O(n log k), also uniform. If stuck: do k = 1 aloud on three items: keep item i with chance 1/i, so the first survives 1 x 1/2 x 2/3 = 1/3, the second 1/2 x 2/3 = 1/3, and the third 1/3.

Next stop: Small classes: an LRU cache, a time-keyed store and an iterator, 9 min

Small classes: an LRU cache, a time-keyed store and an iterator

Context. Lesson 7 builds caches and queues with threads. Inside a DSA round the same objects arrive as plain coding problems, "design a class whose methods each run in O(1)", often followed by "now make it thread-safe" (author's reading of the lesson 6 and lesson 7; no company publishes how often). They test something the pattern problems do not: whether you choose an invariant before typing and keep it true in every method. The LRU cache and the time-keyed store were compiled and run in one file with java --source 21 on OpenJDK 25 on 2 Nov 2026, each checked against a plain list model on 3,000 random runs of 30 to 40 operations and against the invented traces here; a hand-rolled LRU cache and a min stack from the same file are in another section of this appendix. The iterator was run on its own.

LRU cache, with the library

Cue. "Least recently used", "capacity", "get and put in O(1)". Idea. A hash map gives O(1) lookup but no order; a doubly linked list gives O(1) move-to-front and drop-from-the-back but no lookup. Keep both, pointing at the same nodes. Java's library already joins them: in Oracle's words, a LinkedHashMap built in access order is "well-suited to building LRU caches", and its removeEldestEntry hook "may be overridden to impose a policy for removing stale mappings automatically when new mappings are added" (Java SE 21 API, opened 2 Nov 2026). Say the library version first, in two lines, then offer to write the list yourself; the hand-rolled one is the version an interviewer usually asks to see (author's reading), and it is in another section of this appendix.

import java.util.LinkedHashMap;
import java.util.Map;

/** Library version: access order plus an eviction hook. */
class LruMap<K, V> extends LinkedHashMap<K, V> {
  private final int cap;

  LruMap(int cap) {
    super(16, 0.75f, true);   // true: access order, not insertion
    this.cap = cap;
  }

  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > cap;      // asked after every insert
  }
}

Cost. O(1) average per get and put, from the hash map; O(capacity) space. Trap. The two-argument constructor keeps insertion order, so a get is not a use and the wrong entry is evicted; access order needs the third argument, true (checked in a run on 2 Nov 2026). A put to a key already present is a use too. By hand, the node must store its key: eviction starts from the list end and must also remove the map entry. Fallback that still scores: this version, with the two lines that matter said aloud (access order true; evict when size() > cap).

The follow-up: make it thread-safe. Which lock: one lock around the whole cache, either a synchronized wrapper or Collections.synchronizedMap, which Oracle names because the class "is not synchronized". A read-write lock does not help here, and saying why is the senior signal: every get reorders the list. Oracle puts it plainly: "In access-ordered linked hash maps, merely querying the map with get is a structural modification." So a get needs the write lock too, and a read-write lock becomes a slower mutex. To scale, split the keys into stripes, each a smaller cache with its own lock, chosen by the key's hash. The price is that eviction happens per stripe, so the cache is no longer exactly least recently used across all keys. Lesson 7 tests locked caches under real threads.

What contention costs was measured crudely on 2 Nov 2026 on an Apple M2 with 8 cores and OpenJDK 25: the hand-rolled cache (this appendix), capacity 10,000, keys drawn from 0 to 19,999, 80% gets, 4 million operations in all, three runs after a warm-up, timed with System.nanoTime rather than a benchmark harness such as JMH. The table gives total throughput across all threads, in million operations a second:

On this machine, four threads sharing one lock did less work in total than one thread alone: each operation is so short that passing the lock between cores costs more than the work. Striping won back part of the loss but did not beat one thread. The spread between runs is wide (8.4 to 14.2 for the same set-up), so read the order, not the numbers; they say nothing about other hardware. The sentence for the round: "One lock is correct. Under contention it serialises everything, and for work this cheap the handoff dominates, so I would measure before striping, and I would say that striping gives up exact LRU."

Gave up / revisit when / signal (LRU). Gave up: LFU (least frequently used, a map from frequency to list), expiry by time (the TTL cache in lesson 7's this appendix) and lock-free designs. Revisit when: the prompt says "frequency" or "expires". Signal: the map-plus-list invariant stated before typing, and the reason a read-write lock fails.

A time-keyed store

Cue. "set(key, value, time)", "get(key, time) returns the value set at the latest time at or before it", "a snapshot". Idea. Per key, a sorted map from time to value; get is a floor lookup. Oracle's TreeMap gives "worst-case log(n) time cost for the containsKey, get, put and remove operations", and its floorEntry "Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key" (Java SE 21 API, opened 2 Nov 2026).

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/** set(k, v, t); get(k, t) is the value set at the latest t' <= t. */
class TimeMap {
  private final Map<String, TreeMap<Integer, String>> m = new HashMap<>();

  void set(String key, String value, int t) {
    m.computeIfAbsent(key, k -> new TreeMap<>()).put(t, value);
  }

  /** Returns "" when nothing was set for key at or before t. */
  String get(String key, int t) {
    TreeMap<Integer, String> h = m.get(key);
    if (h == null) return "";
    Map.Entry<Integer, String> e = h.floorEntry(t);
    return e == null ? "" : e.getValue();
  }
}

Cost. O(log n) per set and get, for n entries under the key; space for every entry ever set. If the prompt says times arrive in increasing order for each key, an array list with a binary search gives O(1) amortised set, the same O(log n) get and less memory per entry; ask before choosing. Trap. Two questions decide the code, so ask them: what get returns when nothing is set (here "", not null), and whether a second set at the same time replaces the first (here it does). Thread safety: a ConcurrentHashMap of ConcurrentSkipListMap. Oracle documents that on ConcurrentHashMap the "entire method invocation is performed atomically" for computeIfAbsent, so two threads cannot create two histories for one key, and that the skip list has "expected average log(n) time cost for the containsKey, get, put and remove operations", runs them "safely" across threads, and keeps floorEntry (Java SE 21 API, opened 2 Nov 2026). That version was not run under threads in this lesson. Fallback that still scores: a list of (time, value) pairs per key and a linear scan on get, O(n), stated as such.

Gave up / revisit when / signal (time-keyed store). Gave up: the snapshot array, which is the same idea with snapshot ids for times (per index, a sorted map from snapshot id to value), and trimming old history. Revisit when: values must expire or memory is capped. Signal: the floor lookup named as the reason for the sorted map, before any code.

An iterator: flatten a nested list, and the hasNext contract

Cue. "Design an iterator", "implement next and hasNext", "flatten", "peek". The contract. Oracle's Java SE 21 Iterator page says hasNext "Returns true if the iteration has more elements. (In other words, returns true if next() would return an element rather than throwing an exception.)", and that next throws NoSuchElementException "if the iteration has no more elements" (opened 2 Nov 2026). So hasNext may be called any number of times without losing an element, and next must work when hasNext was never called. Idea. A stack of iterators, one per open list. hasNext does the searching: it steps into lists and pops finished ones until it holds the next integer, then caches it. next hands the cached integer over once.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

/** The integers of a nested list, in order. Elements are Integer or
 *  List; hasNext finds the next integer and may be called repeatedly. */
class Flatten implements Iterator<Integer> {
  private final Deque<Iterator<?>> stack = new ArrayDeque<>();
  private Integer next;                    // found, not yet returned

  Flatten(List<?> root) {
    stack.push(root.iterator());
  }

  @Override
  public boolean hasNext() {
    while (next == null && !stack.isEmpty()) {
      Iterator<?> top = stack.peek();
      if (!top.hasNext()) {
        stack.pop();                       // this list is used up
        continue;
      }
      Object o = top.next();
      if (o instanceof Integer v) next = v;
      else stack.push(((List<?>) o).iterator());  // one level down
    }
    return next != null;
  }

  @Override
  public Integer next() {
    if (!hasNext()) throw new NoSuchElementException();
    Integer v = next;
    next = null;                           // hand it over once
    return v;
  }
}

Cost. O(1) amortised per call, since over the whole walk each list is pushed and popped once and each element read once; O(d) space for nesting depth d. Trap. A hasNext that only asks "is the stack non-empty?" says true for [[]], and next then has nothing to give. Another is a hasNext that moves past an element on every call, so asking twice skips one; the harness calls hasNext zero, one or two times before each next, on 5,000 random nested lists against a recursive walk, and checks that hasNext stays false after the end and that next then throws. The peeking variant (named, not coded) is the same cache: peek fills it if empty and returns it without clearing; next returns and clears it. Fallback that still scores: flatten everything into an ArrayList in the constructor and walk an index: O(n) memory instead of O(d), and say so. If stuck: "I will make hasNext do all the searching and cache what it finds; then next is three lines."

Next stop: Two hard ones, in outline: an interval DP and the median of two sorted arrays, 4 min

Two hard ones, in outline: an interval DP and the median of two sorted arrays

Context. Senior rounds reach a hard problem often enough that the partial-credit path needs rehearsing as well as the full answer (author's reading). Each item below gives the problem in the author's words, the idea, the cost, the trap and the sentence to say if the clock runs out before the code works. The listings, figures and traces are in another section of this appendix, where both classes were compiled and run in one file with java --source 21 on 2 Nov 2026.

Burst balloons: interval DP, choosing the last move

Problem. Balloons in a row carry numbers. Bursting balloon i earns left × i × right, using its neighbours at that moment, with a 1 beyond either end. Burst them all, in the order that earns the most. Limits (invented): up to 300 balloons, values 0 to 100. Cue. The order of removals matters, and each removal's value depends on what is next to it at the time. Idea. Choosing which balloon to burst first splits nothing, because its neighbours then become neighbours of each other. Choose instead the balloon k that bursts last inside an open interval (l, r): at that moment its neighbours are exactly l and r, and the balloons on each side were burst independently inside (l, k) and (k, r). Pad a 1 at each end; then dp[l][r] is the maximum over k of dp[l][k] + a[l]·a[k]·a[r] + dp[k][r], filled by growing the interval's length.

Cost. O(n³) time and O(n²) space. At n = 300 the inner step runs 4,545,100 times (arithmetic, counted by script). An int is safe: the total is at most n × 100³ = 3 × 10⁸, under 2³¹ (arithmetic). Trap. Thinking about the first balloon to burst: the two sides are not independent, because they become neighbours. A second trap: the loop must grow by length, so that dp[l][k] and dp[k][r] are filled before dp[l][r] reads them.

What I would say if I could not finish. "I would memoise on the set of balloons still standing, as a bitmask: for each standing balloon, burst it now, find its nearest standing neighbours and recurse. With the neighbour scan that is O(2ⁿ · n²), fine up to about n = 15 and hopeless at 300. The fix is to think about the last balloon instead of the first, because that makes the two sides independent intervals." The run file holds that fallback and checks the DP against it.

Gave up / revisit when / signal (interval DP). Gave up: palindrome partitioning with fewest cuts and matrix-chain order, which fill the same (l, r) table. Revisit when: a prompt merges or splits a sequence and the cost depends on both ends. Signal: the word "last" said before any code.

Median of two sorted arrays: binary search on the cut

Problem. Two sorted int arrays of sizes m and n, not both empty; return the median of all m + n values in O(log(min(m, n))) time. Cue. "Two sorted arrays", "median" or "k-th smallest", and a limit that rules out a linear merge. Idea. The median splits the merged values into a left half of (m + n + 1) / 2 values and the rest. Take i values from a and j = half − i from b. The cut is right when every left value is at most every right value, and because each array is sorted, two cross checks are enough: a[i−1] ≤ b[j] and b[j−1] ≤ a[i]. Binary search on i over the shorter array, with sentinels standing in for a missing side.

Cost. O(log(min(m, n))) time, O(1) space. Traps. Searching the longer array lets j go negative. hi starts at m, not m − 1, because the cut can fall after a's last value. The sum of the two middle values can overflow an int, so the average is taken in a long: the harness checks MAX_VALUE with MAX_VALUE, and MIN_VALUE with MAX_VALUE, which gives −0.5.

What I would say if I could not finish. "A merge walk gets the answer: two pointers advance (m + n) / 2 + 1 steps, keeping the last two values, O(m + n) time and O(1) space. The log version does better by searching where the cut falls in the shorter array instead of walking to it." Say it, and code the walk if the binary search does not work by minute 25 of the round.

Gave up / revisit when / signal (median). Gave up: the k-th smallest of two arrays by discarding k/2 values a step, and the median of k sorted arrays. Revisit when: the prompt asks for the k-th value, not the median. Signal: the two cross checks stated before any code.