2 The Interview Playbook

A strong interview is collaborative problem solving with observable judgment. Correct code matters, but the interviewer also needs evidence that you can clarify requirements, choose deliberately, validate your work, and respond to new constraints.

2.1 A reliable 45-minute flow

Minutes	Candidate action
0–5	Restate the problem; ask about input guarantees, duplicates, ordering, and desired failure behavior
5–10	Work a tiny example; name a brute-force baseline and its cost
10–15	Propose the better pattern; state its invariant and complexity
15–30	Implement in small compilable steps while narrating decisions
30–38	Trace a normal case and run boundary/adversarial tests
38–45	Fix issues; discuss trade-offs, alternatives, and follow-ups

Do not silently optimize in your head for ten minutes. Give the interviewer useful checkpoints: “A nested loop is \(O(n^2)\). I can avoid rescanning by storing earlier values in a hash map, giving expected \(O(n)\) time and \(O(n)\) space.”

2.2 Clarify before coding

Ask questions that can change the code:

Can input be empty or null?
Are values distinct? Can they be negative or overflow int arithmetic?
Is the input already sorted? May I mutate it?
Do I return indices, values, a count, or the objects themselves?
Does output order matter?
For graphs, are edges directed? Can nodes be disconnected?

Avoid spending time on hypothetical constraints after the contract is clear. State reasonable assumptions and proceed.

2.3 Explain the invariant

An invariant is a precise statement about the algorithm’s changing state that remains true at the same checkpoint—usually the start or end of every loop iteration. It explains what variables, pointers, a map, a queue, or a partially filled table mean right now. It is stronger than saying what the code does and more immediate than stating the final goal.

For example, “I use a hash map” describes a data structure. “Before processing index i, the map contains exactly the values already seen at indices smaller than i” is an invariant. That statement explains which entries may be in the map and why a match found there cannot reuse the current element.

An invariant gives a compact, three-part correctness argument:

Initialize: show that it is true before the first iteration.
Preserve: show that one iteration keeps it true for the next iteration.
Finish: combine the invariant with the stopping condition to explain why the result is correct.

State the invariant before coding when possible. It acts as a design constraint: it gives each piece of state a meaning, suggests the correct loop condition and update order, and reveals which data can be safely discarded. During a trace, check the invariant after every iteration. The first step where it becomes false usually identifies the bug. Saying it aloud also lets the interviewer evaluate the reasoning without reconstructing it from finished code.

A useful spoken form is: “At the start of each iteration, ___ represents ___, while ___ remains to be processed.” Be specific about the checkpoint and boundaries. “The window is valid” is vague; “At the start of each iteration, s[start..end-1] contains no duplicate characters, and start never moves backward” is testable.

Problem	Invariant	How it guides or repairs the code
Two Sum	Before processing `i`, the map contains only values from indices `< i`.	Check for the complement before inserting `nums[i]`; otherwise one element could match itself.
Binary search	If the target exists, it is in the inclusive candidate interval `[low, high]`.	Use `low <= high`, and after checking `mid`, set a boundary to `mid + 1` or `mid - 1`. Keeping `mid` would fail to make progress.
Longest substring without repeats	The current window contains no duplicates, and `start` never moves backward.	On `abba`, an old index for `a` must not move `start` back into invalid territory; update with `max(start, oldIndex + 1)`.
BFS level order	After `levelSize = queue.size()`, the first `levelSize` queued nodes are exactly the current level.	Remove exactly that many nodes. Rechecking the growing queue size would mix children into their parents’ level.
Coin change	Before computing amount `x`, the optimal answers for all smaller amounts are final.	Fill the table in increasing amount order, so every state read by the recurrence is ready.

The invariant does not need to be true at every line inside the loop body; an update may temporarily disrupt it. It must be restored at the chosen checkpoint before the next iteration. If you cannot say when the statement is true or what each boundary includes, refine it before relying on it.

2.4 Code for recovery

Prefer code you can debug under stress:

use descriptive state such as left, right, previous, and prerequisitesLeft;
keep the baseline solution in one method;
use early returns for empty inputs;
avoid clever stream pipelines in the core algorithm;
use Integer.compare(a, b) instead of a - b in comparators; and
separate graph construction from graph traversal.

If stuck, return to the example and state what information you repeatedly recompute. That information often reveals the needed data structure.

2.5 Test like an engineer

Start with one ordinary example, then target the algorithm’s seams:

empty and one-element input;
first/last position and even/odd lengths;
duplicates, all-equal values, negative values, and zeros;
already sorted, reverse-sorted, or fully overlapping input;
skewed trees, disconnected graphs, self-cycles, and unreachable states.

Predict the output before running a test. A green test is weak evidence if the expected value was improvised after execution.

2.6 If you find a bug

Say what failed, reduce it to a small case, and repair the invariant. This is better evidence than hurried random edits. For example: “On abba, I moved start backward when I saw the old a. start must be monotonic, so I need max.”

2.7 Best practices for interviewers

Interviewers can make the exercise more predictive and fair:

state the contract, evaluation criteria, time budget, and available APIs;
use a calibrated prompt with multiple valid approaches;
distinguish required behavior from optional follow-ups;
offer the same category of hint at the same stage to comparable candidates;
let candidates run code and tests in a realistic environment;
evaluate reasoning, correctness, testing, communication, and response to feedback—not recall of a trick;
avoid trivia, hidden assumptions, and unnecessary domain context;
leave five minutes for candidate questions; and
write evidence-based notes immediately, separating observed behavior from inference.

A useful rubric scores independent dimensions. A candidate who chooses a slightly less optimal but correct, well-tested solution may demonstrate stronger engineering judgment than one who recalls an optimal trick but cannot validate it.

2.8 A compact spoken template

“Let me restate the contract and check two assumptions. A direct solution would cost __ because . I can improve it with . The invariant is . I’ll implement that, trace this small case, then test the boundaries. The resulting complexity is .”