The coding round

A coding problem is almost never new. Under the story about trains, tickets or text sits one of a small set of shapes: two pointers, a window, a running total, ranges, a graph, a number you can search for, a table of smaller answers, a linked list. The round is where a stranger watches you recognise the shape, type it without fuss and say what it costs.

How the round is judged

Meta's careers page says its interviewers look at how you approach the problem, whether you write the solution correctly and in time, and whether you find and fix your own bugs; Amazon's page stresses well-tested, robust code; Google's re:Work guide describes a method of vetted questions, notes and standard rubrics, not a coding form. From those the author builds a four-box check. It is not any company's form.

A senior interviewer marks down, in this order: code before a stated plan, silence, no trace, a cost claimed without derivation, and a bluff when the algorithm runs out.

Next stop: Costs to know by heart, 1 min

Costs to know by heart

For: Intern; SDE-1 if Big-O is new.

Big-O says how work grows with the input size n: O(n) doubles when n doubles; O(log n) adds one step. The costs are those the OpenJDK class comments state.

Three rules. Count the loops: nested loops are O(n squared) unless the inner pointer never moves back (a window takes 2n steps in all: O(n)). Amortised means averaged: an ArrayList sometimes copies its array to grow, yet n adds cost O(n). Recursion costs calls times work per call: two branches n deep is O(2^n) (subsets); halving gives log n levels, and a full pass per level O(n log n) (merge sort). Stack depth counts as space.

Next stop: The moves, minute by minute, 4 min

The moves, minute by minute

The marks below are the author's estimate (not measured); move them after your first two mocks.

Two problems in 45 minutes. Hard stop on the first problem at minute 16 (18 at the latest), whatever its state; say "I will park this with the brute force and move on". Rehearse it with solutions 3 then 1 (author's marks, not measured): clarify 0 to 2, plan to 4, code to 11, trace to 14, cost to 16; then clarify 16 to 19, plan to 21, code to 33, trace to 38, cost and follow-up to 45. One hard problem. By minute 12 have a faster idea or be typing the brute force. Meta's page splits its coding interview into 5 minutes of introductions, 35 of coding and 5 of questions, so you have about 35 minutes, not 45: start the clock when the problem is read, cut the follow-up first, never the trace.

Read the limits first

The printed size is a hint to the intended solution. This is the competitive-programming rule of thumb for about one second in a compiled language such as Java (a convention, not a quotation); an interpreted language should aim one row tighter.

Say it aloud: "n is 100,000, so quadratic is out." If no limit is given, ask: "How large can the input be, and what range do the values have?"

Clarifying questions that reveal the pattern

The mapping is the author's reading.

Next stop: When you are stuck, 2 min

When you are stuck

For: all levels.

Do these four in order, aloud, before you ask for anything.

1. State the brute force and what it wastes. On "count subarrays that sum to k": "Every start and end, O(n squared); the waste is re-adding the same prefix." A stated brute force scores partial credit by itself, and naming the repeated work points at the fix.
2. Shrink the input. On "is this a binary search tree": draw 10 with children 5 and 15, then add a 6 as the left child of the 15. Each parent check passes and the tree is wrong, because 6 sits in the right subtree of 10. The fact to carry down is a pair of bounds, not the parent.
3. Break your own idea. You think "slide a window, shrink when the sum is above k" works. Try [5, -3, 1] with k = 3: the whole array sums to 3, but the window drops the 5 at once. The failure tells you the method must not rely on sums rising.
4. Write the invariant you believe. When code is nearly right and answers are wrong, stop editing and write the sentence that should hold after every step ("the window has no repeats and left never decreases"). Test that sentence on four elements.

Asking for a hint. Talking through how you would improve the brute force invites a nudge and reads better than "can I have a hint?". A script: "I have the O(n squared) version. The cost is in re-scanning. Is there a structure you would expect me to keep between steps?" One light hint is usually fine if you recover fast; some interviewers count any hint (author's estimate, not measured). Partial credit. Ship the correct slow version before the fast one is half written: "I will code the quadratic version first so we have a baseline." If you cut a corner, say so in a comment.

Tests, in this order. The sample; empty and one element; all equal; sorted and reverse sorted; a zero or negative; the maximum size (reason about its time, do not run it); the case that breaks the trap in your pattern's row below. Walk the smallest case that could fail by hand instead of adding prints.

Next stop: The pattern selector, 6 min

The pattern selector

For: all levels, Staff and Principal included.

Read the trigger, type the template line, check the trap. The rows are the author's split: type every row from memory except 18, which is recognise-only. Row 1 is solved in "Two first problems", starred rows in "Eight problems solved to the end", the rest as templates.

When two rows fit, take the cheaper one that meets the limit. Subarray sum with negatives: row 5, not 4. A moving top k: row 13. A "connected?" that edges change over time: row 11, not a fresh BFS each time. Tasks with order: row 10; with costs on edges as well, row 16.

Eight common types the rows do not name. Each still reduces to a row.

Next stop: Two first problems: a hash map and two pointers, 2 min

Two first problems: a hash map and two pointers

For: Intern, SDE-1.

Two-sum, unsorted. Trigger: two values adding to a target, unsorted. Brute force tries every pair, O(n squared). Invariant: at j, the map holds every value to its left, so one lookup finds an earlier partner. Cost: O(n) time and space. Trap: inserting before the lookup pairs [3] with itself for target 6.

3Sum, row 1. Trigger: a sorted or sortable input, a pair or triple with a target sum. Sort, fix the first value, then run sorted two-sum on the rest. Invariant: no pair outside [lo, hi] can reach zero: a low sum means a[lo] fails even with the largest partner left. Cost: O(n log n) plus O(n squared); O(n) for the copy. Trap: without the outer skip, [-1, -1, 0, 1] gives [-1, 0, 1] twice; without the inner skip, [-2, 0, 0, 2, 2] gives [-2, 0, 2] twice.

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

class Pairs {
  static int[] twoSum(int[] a, int target) {    // unsorted: a hash map
    Map<Integer, Integer> at = new HashMap<>();  // value -> index
    for (int j = 0; j < a.length; j++) {
      Integer i = at.get(target - a[j]);        // partner seen earlier?
      if (i != null) return new int[] {i, j};
      at.put(a[j], j);                          // only after the lookup
    }
    return null;
  }

  static List<List<Integer>> threeSum(int[] nums) {   // triples summing to 0
    int[] a = nums.clone();
    Arrays.sort(a);
    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) {                              // sorted two-sum
        long s = (long) a[i] + a[lo] + a[hi];
        if (s < 0) lo++;
        else if (s > 0) hi--;
        else {
          out.add(List.of(a[i], a[lo], a[hi]));
          while (lo < hi && a[lo] == a[lo + 1]) lo++;  // skip repeats
          lo++;
          hi--;
        }
      }
    }
    return out;
  }
}

Both were checked against brute force on 5,000 random arrays. On sorted input, two-sum is row 1 in O(1) space.

Next stop: Eight problems solved to the end, 8 min

Eight problems solved to the end

For: all levels; Staff and Principal type five of these cold for lesson 5's gate B.

One per family, each with its baseline, invariant, cost, trap and an example to pass on the first run.

1. Sliding window: the longest stretch with no repeated character (row 4)

The baseline checks every start and end: quadratic at best. A stretch with no repeats keeps having none when you shrink it, so one pass suffices. Invariant: the window [left, right] has no repeats after each step, and left never decreases. Figure 6.2 follows "pwwkew".

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 once), O(min(n, alphabet)) space. Trap: on "abba" the map says index 0 for the last 'a', but left is already 2, so the guard p >= left keeps it; without it the code returns 3 instead of 2.

2. Prefix sums: count subarrays that sum to k, negatives allowed (row 5)

A subarray sum is the difference of two prefix sums, so at each position ask how many earlier prefixes equal total - k. A window fails here because with negatives the sum does not rise as the window grows. Invariant: the map holds every earlier prefix with its count.

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;
  }
}

Example: [1, -1, 1] with k = 1 gives 3: each 1 alone, and the whole array. Cost: O(n) time, O(n) space. Trap: forget the seed {0: 1} and every subarray that starts at index 0 is missed.

3. Intervals: merge overlapping ranges (row 6)

Sorted by start, a range either touches the last output range or starts a new one. Invariant: the output is sorted, disjoint and covers every input range seen so far.

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) after it. Trap: extend with Math.max, because [1,4] followed by [2,3] must stay [1,4]. For "how many meetings overlap", turn each range into +1 at the start and -1 at the end, sort the events and keep a running count.

4. Linked lists: reverse, middle, nth from the end, cycle start, merge (rows 2 and 3)

Fast and slow pointers find the middle (slow is there when fast runs out) and the cycle; a lead pointer n steps ahead finds the nth from the end; a dummy head makes merge uniform. In Floyd's cycle start, if the tail before the cycle is t nodes long, t steps from the meeting point also land on the cycle start, perhaps after whole laps (the distances agree modulo the cycle length). So restart one pointer at the head and step both once at a time: they meet at the start.

class Lists {
  static class Node { int val; Node next; Node(int v) { val = v; } }

  static Node reverse(Node head) {
    Node prev = null;
    while (head != null) {
      Node next = head.next;            // save before overwriting
      head.next = prev; prev = head; head = next;
    }
    return prev;
  }

  static Node middle(Node head) {   // second middle if the length is even
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next; fast = fast.next.next;
    }
    return slow;
  }

  static Node nthFromEnd(Node head, int n) {   // n = 1 is the last node
    Node lead = head;
    for (int i = 0; i < n; i++) {
      if (lead == null) return null;           // list shorter than n
      lead = lead.next;
    }
    Node trail = head;
    while (lead != null) { lead = lead.next; trail = trail.next; }
    return trail;
  }

  static Node cycleStart(Node head) {   // Floyd
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next; fast = fast.next.next;
      if (slow == fast) {
        slow = head;
        while (slow != fast) { slow = slow.next; fast = fast.next; }
        return slow;
      }
    }
    return null;
  }

  static Node merge(Node a, Node b) {   // dummy head: no first-node case
    Node dummy = new Node(0), tail = dummy;
    for (; a != null && b != null; tail = tail.next)
      if (b.val < a.val) { tail.next = b; b = b.next; }
      else { tail.next = a; a = a.next; }
    tail.next = a != null ? a : b;
    return dummy.next;
  }
}

Example: on 1 to 5, reverse gives 5 to 1, the middle is 3, nthFromEnd(head, 2) is 4, and with 5 linked back to 3 cycleStart is 3; merging 1, 4 with 2, 3 gives 1, 2, 3, 4. Cost: each method is one pass, O(n) time and O(1) space; no hash set needed. Traps: reverse loses the list if you overwrite next first; nth from the end needs the null check inside the lead loop; with an even length middle returns the second of the two middle nodes, so say which you want.

5. Grid BFS: count the islands (row 8)

The baseline is a flood fill from every land cell, which is fine if each cell is visited once. Invariant: every cell that is queued is already marked seen, so nothing enters the queue twice.

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;
  }
}

Example: rows 110, 001 and 011 give 2; the diagonal from row 0 to row 1 does not join. Cost: O(rows x cols) time and space. Trap: marking on pop rather than push lets one cell be queued many times. A queue also avoids a recursive fill's stack overflow on a large grid.

6. Binary search on the answer: the slowest eating speed that finishes in h hours (row 12)

If a speed works, a faster one works too, so the answer sits at the boundary of a monotone yes/no check. The reusable part is minFeasible; only the check changes between problems. Invariant: the answer stays inside [lo, hi].

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 += ((long) p + s - 1) / s; // ceiling
      return hours <= h;
    });
  }
}

Example: piles 4, 9, 6 with h = 6 give 4 (speed 3 needs 7 hours). Cost: O(n log max) time, O(1) space. Trap: a check that is not monotone makes the search meaningless, so state the monotonicity out loud; hours total in a long. Ask whether h is at least the number of piles: below that no speed works, and this code returns max without saying so.

7. Dynamic programming: the fewest coins for an amount (row 15)

Say the state first: dp[a] is the fewest coins that make amount a. Each amount tries the last coin, which gives dp[a - c] + 1. Greedy (largest coin first) is wrong for coins {1, 3, 4} and amount 6: it gives 4+1+1, three coins, while 3+3 uses two.

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];
  }
}

Cost: O(amount x coins) time, O(amount) space. Trap: an infinity of Integer.MAX_VALUE overflows on the + 1.

8. Topological order: the critical path, in the transcript below (row 10)

Next stop: Eight more families as templates, 5 min

Eight more families as templates

Rows 7, 9, 11, 13, 14, 16, 17 and 19, each in the shortest form worth typing from memory.

Monotonic stack (row 7). Use: the next larger (or smaller) element to the right. Trap: < or <= decides equal values, so ask; store indexes. Cost: O(n), each index pushed and popped once. Figure 6.3 traces [73, 74, 75, 71, 69, 72, 76, 73], which gives [1, 1, 4, 2, 1, 1, 0, 0].

  static int[] warmer(int[] temp) {          // days to wait, 0 if never
    int[] ans = new int[temp.length];
    Deque<Integer> st = new ArrayDeque<>();   // indexes, coldest on top
    for (int i = 0; i < temp.length; i++) {
      while (!st.isEmpty() && temp[st.peek()] < temp[i]) {
        int j = st.pop();                     // day i is j's warmer day
        ans[j] = i - j;
      }
      st.push(i);
    }
    return ans;
  }

Tree recursion (row 9). Use: a node's answer comes from its children's (height, diameter, path sums). Return one value up; keep the best path that bends at a node in a one-element array. Trap: returning the bent path instead of the height. Cost: O(n) time, O(h) stack. Level order is solution 5's queue with for (int k = q.size(); k > 0; k--) per level.

  record T(int val, T left, T right) {}

  static int diameter(T root) {              // longest path, in edges
    int[] best = {0};
    height(root, best);
    return best[0];
  }

  static int height(T n, int[] best) {       // post-order: kids first
    if (n == null) return 0;
    int l = height(n.left(), best), r = height(n.right(), best);
    best[0] = Math.max(best[0], l + r);      // the path that bends at n
    return 1 + Math.max(l, r);
  }

Union-find (row 11). Use: groups only merge, and you ask "same group?" in between (drill 11). Trap: compare roots; count a merge only when union returns true; it cannot split. Cost: near O(1) per call with path halving and union by size.

class Dsu {
  final int[] up, size;                      // up[x]: x's parent
  Dsu(int n) {
    up = new int[n]; size = new int[n];
    for (int i = 0; i < n; i++) { up[i] = i; size[i] = 1; }
  }
  int find(int x) {                          // path halving
    for (; up[x] != x; x = up[x]) up[x] = up[up[x]];
    return x;
  }
  boolean union(int a, int b) {              // false: already joined
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    up[rb] = ra; size[ra] += size[rb];       // smaller under larger
    return true;
  }
}

Heap, top k (row 13). Use: the k largest of many. A min-heap of size k keeps the smallest survivor on top, so a bigger arrival evicts it. Trap: iteration order is not sorted. Cost: O(n log k). Merging k sorted lists (drill 3's follow-up) is in the Solutions appendix.

  static List<Integer> topK(int[] a, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();  // min on top
    for (int x : a) {
      pq.add(x);
      if (pq.size() > k) pq.poll();               // evict the smallest
    }
    return new ArrayList<>(pq);                   // heap order, unsorted
  }

Backtracking (row 14). Use: every subset, arrangement or placement, n up to about 20. Choose, explore, undo. Trap: record a copy of the path; sort first so the duplicate skip works. Cost: O(2^n · n) for subsets.

  static void subsets(int[] a, int from, List<Integer> path,
      List<List<Integer>> out) {             // a sorted
    out.add(new ArrayList<>(path));          // a copy, not path
    for (int i = from; i < a.length; i++) {
      if (i > from && a[i] == a[i - 1]) continue;  // skip duplicates
      path.add(a[i]);                        // choose
      subsets(a, i + 1, path, out);          // explore
      path.remove(path.size() - 1);          // undo
    }
  }

Dijkstra (row 16). Use: the cheapest path from one source, no negative weights. PriorityQueue cannot lower a key, so push again and skip stale entries. Trap: int sums overflow; unreachable stays Long.MAX_VALUE. Cost: O(E log V).

  static long[] dijkstra(List<List<int[]>> adj, int src) {
    long[] dist = new long[adj.size()];      // adj.get(u): {v, weight}
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;
    var pq = new PriorityQueue<long[]>(Comparator.comparingLong(e -> e[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: skip
      for (int[] e : adj.get(u))
        if (dist[u] + e[1] < dist[e[0]]) {
          dist[e[0]] = dist[u] + e[1];
          pq.add(new long[] {dist[e[0]], e[0]});
        }
    }
    return dist;
  }

Trie (row 17). Use: many words, and repeated "is this a word?" or "any word with this prefix?". Trap: without the end flag a prefix passes as a word; c - 'a' assumes lowercase, so ask. Cost: O(length) per call; 26 slots per node.

class Trie {
  private final Trie[] next = new Trie[26];
  private boolean word;                      // a word ends here
  void add(String s) {
    Trie t = this;
    for (char c : s.toCharArray()) {
      if (t.next[c - 'a'] == null) t.next[c - 'a'] = new Trie();
      t = t.next[c - 'a'];
    }
    t.word = true;
  }
  boolean has(String s, boolean asPrefix) {
    Trie t = this;
    for (int i = 0; i < s.length() && t != null; i++)
      t = t.next[s.charAt(i) - 'a'];
    return t != null && (asPrefix || t.word);
  }
}

Greedy (row 19). Use: the fewest ranges to remove so the rest do not overlap. Keep the range that ends first: put in place of the first range of any best answer, it leaves that answer valid and the same size (the exchange argument; say it aloud). Trap: sorted by start, [1, 10] is kept and blocks [2, 3] and [4, 5]: 2 removals, not 1. Example: [1, 3], [2, 4], [3, 5], [1, 5] gives 2. Cost: O(n log n).

import java.util.Arrays;

class Greedy {
  static int removals(int[][] ranges) {   // touching ranges may both stay
    int[][] a = ranges.clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[1], y[1]));  // by end
    int kept = 0;
    long end = Long.MIN_VALUE;            // end of the last range kept
    for (int[] r : a)
      if (r[0] >= end) { kept++; end = r[1]; }
    return a.length - kept;
  }
}

Next stop: Dynamic programming families, 2 min

Dynamic programming families

Most DP problems in a round are one of these five (author's grouping; solution 7 is the first). Say the state, the transition, then an order that fills each cell after the cells it reads.

Interval DP (fill by length) and bitmask DP (n up to 20) are rarer (author's estimate, not measured). The two-strings row in full: the fewest inserts, deletes and replacements that turn s into t.

class Edit {
  static int distance(String s, String t) {  // fewest edits, s to t
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];      // dp[i][j]: s[0,i) to t[0,j)
    for (int i = 0; i <= m; i++) dp[i][0] = i;     // delete all
    for (int j = 0; j <= n; j++) dp[0][j] = j;     // insert all
    for (int i = 1; i <= m; i++)
      for (int j = 1; j <= n; j++)
        dp[i][j] = s.charAt(i - 1) == t.charAt(j - 1)
            ? dp[i - 1][j - 1]                     // last chars match
            : 1 + Math.min(dp[i - 1][j - 1],       // replace
                Math.min(dp[i - 1][j], dp[i][j - 1]));  // delete, insert
    return dp[m][n];
  }
}

Traced on "horse" to "ros" (invented): the bottom-right 3 is replace h with r, delete r, delete e.

      ""  r  o  s
  ""   0  1  2  3
  h    1  1  2  3
  o    2  2  1  2
  r    3  2  2  2
  s    4  3  3  2
  e    5  4  4  3

Cost: O(m × n) time and space; each row reads only the one above, so two rows give O(n) space.

Next stop: A senior answer, as a transcript, 4 min

A senior answer, as a transcript

For: SDE-2, SDE-3, Staff, Principal.

A plain question: the senior signals come before the code.

The bracketed notes are the signals; none needed a cleverer algorithm. The code:

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

class Crit {
  record Plan(int days, List<Integer> path) {}

  /** Each edge is {before, after}. Returns null when there is a cycle. */
  static Plan criticalPath(int[] dur, int[][] edges) {
    int n = dur.length;
    int[] indeg = new int[n];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
      adj.get(e[0]).add(e[1]);
      indeg[e[1]]++;
    }
    int[] finish = new int[n];   // earliest finish of each task
    int[] from = new int[n];     // predecessor that set that finish
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
      finish[i] = dur[i];
      from[i] = -1;
      if (indeg[i] == 0) q.add(i);
    }
    int done = 0;
    while (!q.isEmpty()) {
      int v = q.poll();
      done++;
      for (int w : adj.get(v)) {
        if (finish[v] + dur[w] > finish[w]) {
          finish[w] = finish[v] + dur[w];
          from[w] = v;
        }
        if (--indeg[w] == 0) q.add(w);
      }
    }
    if (done < n) return null;
    int last = 0;
    for (int i = 1; i < n; i++) if (finish[i] > finish[last]) last = i;
    List<Integer> path = new ArrayList<>();
    for (int v = last; v != -1; v = from[v]) path.add(0, v);
    return new Plan(finish[last], path);
  }
}

Example: the sample gives 8 days, path 0, 2, 3; a two-task cycle gives null. Hack sheet. Template: finish[w] = max(finish[w], finish[v] + dur[w]) when relaxing v to w, remembering the predecessor. Trap: duration on the node versus on the arrow; reading the answer from the last popped node instead of the maximum.

Next stop: Follow-ups after each solved problem, 2 min

Follow-ups after each solved problem

For: SDE-2, SDE-3, Staff, Principal.

The author's reading of the next question after each solution.

Next stop: Coding at Staff and Principal, 3 min

Coding at Staff and Principal

For: Staff, Principal.

Usually one medium problem or a screen; some Principal loops have none (lesson 12). The bar changes, not the problem (author's estimate, not measured): assumptions before code, a baseline before the clever version, code a colleague could merge (honest names, tests named as sentences, errors handled), what breaks at a hundred times the size, and where you stop optimising. A bluff costs more than a hint. A Principal screen may be code reading: rank the bug, the race and the missing test (one worked, one drill, below). Rehearse the transcript and its follow-ups aloud on a clock.

A worked code-reading screen

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/** At most limit calls per user in any windowMs. */
class Limiter {
  private final int limit;
  private final long windowMs;
  private final Map<String, Deque<Long>> hits = new HashMap<>();

  Limiter(int limit, long windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
  }

  /** Called from every request thread. */
  boolean allow(String user, long now) {
    Deque<Long> q = hits.get(user);
    if (q == null) {
      q = new ArrayDeque<>();
      hits.put(user, q);
    }
    while (!q.isEmpty() && q.peekFirst() <= now - windowMs) q.pollFirst();
    if (q.size() > limit) return false;
    q.addLast(now);
    return true;
  }
}
// The only test: limit 3, window 1000 ms; calls at 0, 1, 2 all allowed.

Run on OpenJDK 25: the shipped code passes its only test; under 8 threads it miscounted in every one of 120 stress runs (most of them threw); the fix was exact in all 120. More: lesson 9's "A worked 60-minute round, with a planted bug" and its practice loop.

A second screen, as a drill

Cover the answer below, set 10 minutes and rank aloud.

import java.util.HashMap;
import java.util.Map;
import java.util.function.Supplier;

/** Retries op with doubling waits. Used by payments and search. */
class Retry {
  static final Map<String, Integer> failures = new HashMap<>();

  static <T> T call(String name, Supplier<T> op, int maxTries)
      throws InterruptedException {
    long waitMs = 100;
    for (int i = 0; i <= maxTries; i++) {
      try {
        return op.get();
      } catch (RuntimeException e) {
        failures.merge(name, 1, Integer::sum);
        Thread.sleep(waitMs);
        waitMs *= 2;
      }
    }
    throw new IllegalStateException(name + " failed");
  }
}
// The only test: an op that fails once, then returns 7, gives 7.

Answer, by harm. 1. A timed-out payment may have gone through, so a retry can charge twice: retry only idempotent calls or send an idempotency key, and only on retryable errors. 2. The shared HashMap races: use ConcurrentHashMap, whose merge is atomic. 3. i <= maxTries makes maxTries + 1 calls, sleeps after the last failure and drops the cause; doubling waits also need jitter and a cap. 4. The missing test: an op that always fails. Pass: inside 10 minutes, 1 and 2 ranked above 3, each with a one-sentence fix and its test (author's bar, not measured). 3 and 4 alone is SDE-2.

Run on OpenJDK 25: maxTries 3 made 4 calls; under 8 threads the count fell short in 10 of 10 runs, 0 with ConcurrentHashMap.

For: Staff, Principal.

The Principal move. End either screen with the rule that stops this class of fault in every repository: one shared retry helper that refuses calls not marked idempotent, owned by the platform team, checked by a lint rule that flags hand-written retry loops and a test that a payment call without an idempotency key fails. Pass: rule, owner and check inside two minutes (author's bar, not measured).

Next stop: A design-a-class problem: the LRU cache, 3 min

A design-a-class problem: the LRU cache

Some prompts are not a pattern but a small class: "a cache of capacity n whose get and put each run in O(1), evicting the least recently used key". It tests whether you choose an invariant before typing and keep it true in every method (author's reading).

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, with the list running from most recent to least recent between two sentinel nodes, so no method needs a special case for an empty list or an end node. Say first that Java's library already joins the two: a LinkedHashMap built with super(16, 0.75f, true) (access order) and removeEldestEntry overridden to return size() > cap is an LRU cache in two lines; Oracle's API calls access order "well-suited to building LRU caches". Then offer the hand-rolled version (Figure 6.4), which interviewers usually want (author's reading).

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

/** Hand-rolled: a map to nodes plus a doubly linked list. */
class Lru {
  private static final class Node {
    final int key;
    int val;
    Node prev, next;
    Node(int key, int val) { this.key = key; this.val = val; }
  }

  private final int cap;
  private final Map<Integer, Node> map = new HashMap<>();
  private final Node head = new Node(0, 0);  // sentinel: most recent
  private final Node tail = new Node(0, 0);  // sentinel: least recent

  Lru(int cap) {
    if (cap < 1) throw new IllegalArgumentException("cap < 1");
    this.cap = cap;
    head.next = tail;
    tail.prev = head;
  }

  /** Returns -1 when absent; a hit becomes the most recent. */
  int get(int key) {
    Node n = map.get(key);
    if (n == null) return -1;
    unlink(n);
    addFront(n);
    return n.val;
  }

  void put(int key, int val) {
    Node n = map.get(key);
    if (n != null) {            // update counts as a use
      n.val = val;
      unlink(n);
      addFront(n);
      return;
    }
    if (map.size() == cap) {    // evict before inserting
      Node old = tail.prev;
      unlink(old);
      map.remove(old.key);      // why the node stores its key
    }
    n = new Node(key, val);
    map.put(key, n);
    addFront(n);
  }

  private void unlink(Node n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
  }

  private void addFront(Node n) {
    n.next = head.next;
    n.prev = head;
    head.next.prev = n;
    head.next = n;
  }
}

Cost. O(1) average per get and put, from the hash map; O(capacity) space. Traps. The node stores its key, because eviction starts from the list and must also remove the map entry. A put to a key already present is a use. In the library version, the two-argument constructor keeps insertion order, so a get is not a use and the wrong key is evicted.

The follow-up: make it thread-safe. One lock around get and put is correct. A read-write lock does not help, and saying why is the senior signal: every get moves a node, so a get is a write. Oracle's API says the same of access-ordered maps: "merely querying the map with get is a structural modification". To scale, stripe the keys by hash, each stripe a smaller cache with its own lock; eviction is then per stripe, so no longer exactly least recently used. Say you would measure before striping. Next questions. "Least frequently used": key to node, each count to its keys in recency order, and the minimum count, all O(1). "Entries expire": store an expiry time per entry; on get, treat an expired one as missing and remove it (lazy expiry).

Next stop: Java details that cost marks, 1 min

Java details that cost marks

For: anyone who codes in Java.

If you pick Java, these slips turn a right idea into a failed test.

• Comparators. (x, y) -> x[0] - y[0] overflows for large values; write Integer.compare(x[0], y[0]). PriorityQueue is a min-heap; for a max-heap pass Comparator.reverseOrder().
• Overflow and division. int sums pass 2.1 billion quickly; use long when n times the value could. mid = (lo + hi) / 2 can overflow; write lo + (hi - lo) / 2. Integer division truncates toward zero, so -7 / 2 is -3.
• Equality. Compare boxed Integer values with equals, not ==; == is only reliable for small cached values. Compare strings with equals.
• Mutating while iterating. Removing from a list inside a for-each usually throws ConcurrentModificationException; removing the second-to-last element instead skips the last one silently. Use removeIf or iterate backwards by index. A map's getOrDefault and merge remove most null checks.
• Recursion depth. Measured (OpenJDK 25, macOS, the height recursion above on a skewed tree): the default 2 MB thread stack held 10,000 levels and overflowed at 20,000; at -Xss1m, the Linux x64 default, 5,000 held and 8,000 overflowed. If the input can be deeper than 5,000, use a loop and say why.

Next stop: The drill set, 4 min

The drill set

Do each problem on a clock in an editor with no autocomplete, without looking at a listing. Six are sprints: under 25 minutes, no running until your hand trace is done, then one run that must pass. Targets are the author's estimate (not measured) for someone who knows the pattern. Problems 1, 2, 3 and 8 are solved in this lesson; the rest are in the Solutions appendix. Cover the hint table: read hint 1 after five stuck minutes, hint 2 after five more, hint 3 last, and count each as a lost point.

Score each out of 6: 3 for correct code your own hand trace confirms, 1 for the cost sentence in your words, 1 for naming the main edge case before running, 1 for the follow-up in two sentences; subtract one per hint. Under 40 of 72 means the speed is not there yet: repeat the six sprints a week later with the listings closed. The numbers are the author's estimate (not measured), a way to see progress and not a pass mark from any company. Lesson 5's readiness gate says how many of these to clear before you book loops.

Next stop: Online assessments, 3 min

Online assessments

Many Indian loops open with a timed online assessment. The vendors' own help pages (read 1 November 2026) say: Codility scores every task for correctness and, where possible, performance on large data, and its report includes a similarity check and a timeline marking pasted text; CodeSignal's general coding assessment allows 70 minutes unless the company sets another, keeps your highest-scoring submission per question, and proctors with photo ID, screen, camera and microphone; HackerRank's Proctor Mode flags tab switches, full-screen exits, webcam events, extra monitors and external AI assistants. Amazon's SDE II page describes 90 minutes for two coding questions, then 20 minutes of design scenarios and an 8-minute work-style survey. A flag is a report to the employer, not an automatic rejection, but assume a person reads it.

• The limits are the spec of the hidden tests. Submit early, find out whether the last or the best submission counts, and run the sample plus one edge test of your own.
• Language and input. Use the language you type fluently. Some tests give a function to fill; others give raw standard input. For the second kind, type this until it is automatic. It reads tokens across line breaks and prints through one buffered writer (run on two cases: input 2 / 3 / 1 2 / 3 / 2 / 5 -1 prints 6 and 4; the input format here is invented).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
  static BufferedReader in =
      new BufferedReader(new InputStreamReader(System.in));
  static StringTokenizer st = new StringTokenizer("");

  static String next() throws IOException {      // tokens across line breaks
    while (!st.hasMoreTokens()) st = new StringTokenizer(in.readLine());
    return st.nextToken();
  }

  public static void main(String[] args) throws IOException {
    PrintWriter out = new PrintWriter(System.out);   // one buffered writer
    int cases = Integer.parseInt(next());
    while (cases-- > 0) {
      int n = Integer.parseInt(next());
      long sum = 0;                        // long: sums overflow int
      for (int i = 0; i < n; i++) sum += Integer.parseInt(next());
      out.println(sum);
    }
    out.flush();                           // without this, no output
  }
}

• Honest preparation. Run the platform's demo test, close other applications and monitors, open no other tab, and tell the recruiter in writing if something interrupts you. Ask in writing whether any AI tool is allowed; lesson 9 covers rounds where it is.

Pacing two or three problems

For: Intern, SDE-1, SDE-2.

Campus tests often give 2 or 3 problems in 60 to 90 minutes. The author's rules (not measured): read every problem and its limits first; bank the easiest; on a hard one, submit a brute force for the small tests, then improve whichever is closest to full marks; stuck 15 minutes, submit and move on; no new code in the last 8 minutes. For 2 in 60: both read by 5, one banked by 25, a brute force on the other by 40.

0-6    read A, B, C and their limits
6-22   A: subarray count, prefix sums (row 5); 10 of 10
22-48  B: grid BFS (row 8); 11 of 12; a 1 x 1 grid; 12 of 12
48-58  C, n up to 200,000: brute force submitted, 6 of 15
58-82  C is "most meetings kept": greedy (row 19); 15 of 15
82-90  no new code; re-read C's output format; stop

Campus basics the selector skips, each run on OpenJDK 25:

Practice with an AI: the prompt kit in the appendix has 3 cards for this lesson.

Unseen problems: after the drill set, the Practice banks appendix has ten transfer problems, solved in the Solutions appendix.

Sources