Interview strategy
The algorithm is half the score — the other half is everything you say before, during and after writing it.
What is actually being scored
At the advanced level the interviewer is not checking whether you can produce a correct program. They are estimating one thing: what is it like to hand this person an ambiguous problem and come back in three days? Every behaviour in this chapter is a proxy for that. Clarifying questions predict whether you will build the wrong thing. Stating a brute force before optimizing predicts whether you ship something or stall. Testing your own code predicts whether QA finds your bugs or you do. Naming a tradeoff unprompted predicts whether you will make a defensible technical decision alone.
Two candidates can both produce a working O(n log n) solution and receive "strong hire" and "no hire." The difference is almost never the code. It is that one of them narrated a decision process the interviewer could follow and trust, and the other silently emitted a memorized answer that could not be probed, extended, or debugged out loud.
The first five minutes: questions that change the answer
Silence here is the single strongest negative signal available, and it is the cheapest to fix. An engineer who starts coding from an under-specified problem statement is telling the interviewer exactly how they behave with an under-specified ticket. But not all questions are equal — "can I use a hashmap?" wastes the goodwill you are trying to build. Ask only questions whose answer would change your solution, and say why you are asking.
| Ask | Why it changes the solution |
|---|---|
| "How large can n get?" | The highest-value question in the interview. It fixes your target complexity before you have written anything — see the table below. |
| "Is the input sorted, or can I sort it?" | Sorted unlocks two pointers and binary search for free. If not sorted, an O(n log n) sort may be free anyway when the target is already O(n log n) — but it is not free if the target is O(n). |
| "Can there be duplicates?" | Changes whether you dedupe, whether a Set is safe, whether two-pointer needs a skip loop, and whether the expected output is unique. |
| "What's the range of the values? Negative? Zero? Floats?" | Negatives break sliding-window-on-sums and greedy arguments. Small bounded values unlock counting sort or a bitmask. Floats kill exact equality. |
| "What should I return for empty input / no valid answer?" | An explicit contract, decided up front, instead of an ad-hoc guess at minute 40. |
| "Can I mutate the input?" | In-place sorting or marking may be the whole space optimization; if the input is shared state, it isn't allowed. |
| "Is this called once, or repeatedly on the same data?" | Repeated queries change the answer entirely — preprocess into a prefix array, segment tree, or index map and amortize. |
| "Does the whole input fit in memory, or is it a stream?" | Streaming rules out sorting and random access; pushes toward heaps, reservoir sampling, count-min sketch. |
That last clause is the part that scores. You are not collecting facts, you are demonstrating that each fact eliminates a branch of your decision tree. Two or three questions asked this way beat ten asked mechanically.
A framework that works on a problem you have never seen
You will not recognize the problem. That is the point of an advanced interview. What you need is not recall but a procedure that visibly makes progress even from zero. Run these seven steps out loud, in order.
| # | Step | What you actually say |
|---|---|---|
| 1 | Restate in your own words | "So: given X, return Y, where the constraint is Z. Is that right?" |
| 2 | Work the given example by hand | Say the answer for the example before writing anything. Catches misreads instantly. |
| 3 | State a brute force, with its complexity | "The obvious thing is to check every pair — O(n²) time, O(1) space. That's my baseline; let me see if I can beat it." |
| 4 | Name the bottleneck | "The expensive part is that for each i, I re-scan everything before i. That inner scan is the thing to remove." |
| 5 | Read the constraints for the target | "n goes to 10⁵, so O(n²) is 10¹⁰ — far too slow. They're steering me to O(n log n) or O(n)." |
| 6 | Ask what structure removes the bottleneck | "What would make that inner scan O(1) or O(log n)? A hashmap of seen values, a heap, a monotonic stack, or precomputed prefix sums." |
| 7 | Confirm, then code | "So: one pass, hashmap from value to index, O(n) time and O(n) space. Shall I code that?" |
Step 3 is non-negotiable and candidates skip it constantly, believing a brute force looks weak. The opposite is true: it guarantees you have a solution on the board within five minutes, it proves you understand the problem, and it gives you a concrete complexity to improve on. An interviewer will almost always let you skip implementing it. What they will not forgive is twenty minutes of silence hunting for the clever answer.
Constraints → intended complexity: the highest-leverage table here
Interviewers and problem setters choose n deliberately. The
bound is a hint about the intended solution, and reading it correctly can
collapse a twenty-minute search into thirty seconds. Calibrate against the
rough industry rule that ~10⁸ simple operations is about one second.
| Constraint on n | Intended complexity | Pattern family it points at |
|---|---|---|
| n ≤ 10-12 | O(n!) · O(n! · n) | Full permutation search, brute-force TSP, "try every ordering" |
| n ≤ 20-25 | O(2ⁿ) · O(2ⁿ · n) | Bitmask — subset enumeration, bitmask DP, meet-in-the-middle (2^(n/2)) if n ≈ 40 |
| n ≤ 100 | O(n³) · O(n⁴) | Floyd-Warshall, interval/matrix-chain DP, triple nested loops are fine |
| n ≤ 1,000-5,000 | O(n²) | 2D DP over pairs — edit distance, LCS, palindromic substrings; all-pairs comparison |
| n ≤ 10⁵ | O(n log n) | Sort-then-scan, heap, binary search on the answer, balanced BST / ordered set, divide and conquer, segment tree |
| n ≤ 10⁶-10⁷ | O(n) · O(n log log n) | Single pass, two pointers, sliding window, hashmap, counting sort, prefix sums, sieve, Kadane |
| n ≤ 10⁹-10¹⁸ | O(log n) · O(√n) · O(1) | Math/closed form, binary search over the answer space, matrix exponentiation, digit DP — you cannot even read the input |
Read the second half of the constraints too. "Sum of all string lengths ≤ 10⁵" over many strings means linear in the total, which points at a Trie or Aho-Corasick rather than per-string work. A value range like "values ≤ 100" alongside a huge n points at counting/bucketing. A memory limit matters as much as time: n = 10⁵ with an O(n²) DP table is 10¹⁰ cells — impossible regardless of the time limit, which tells you the DP must be rolled down to one or two rows.
n first, derive the complexity the setter intends, and use that
as a filter on which patterns are even eligible. "n ≤ 20" is not
trivia — it is the interviewer telling you the answer involves subsets. Very
few candidates do this, and it is visible in seconds when someone does.
How to talk while you code
The goal is a continuous, low-effort narration that lets the interviewer follow your reasoning without interrupting. Not a play-by-play of syntax — nobody needs "now I'll write a for loop." Narrate decisions, and name your patterns, because naming is what proves the choice was deliberate rather than lucky.
| Instead of | Say |
|---|---|
| silence | "I'll use a monotonic decreasing stack here, because I need the next greater element for every index and a stack lets each element be pushed and popped once — amortized O(n)." |
| "now a map" | "Map from value to index rather than a Set, because I need to return indices, not just detect membership." |
| "hmm, hold on" | "I'm deciding between sorting first and using a heap. Sorting is simpler but O(n log n) up front; the heap gets me the top k in O(n log k). Since k is small I'll take the heap." |
| "…" while fixing a bug | "That should be <=, not < — otherwise the last window never gets evaluated. Let me re-check the boundary." |
| "I'll handle that later" | "I'm deliberately deferring the empty-input case; noting it here as a TODO and I'll come back before I call this done." |
Two mechanical habits pay for themselves. First, write the function signature and the return type before the body — it forces the contract to be explicit. Second, when you defer something, say so and leave a visible marker; an acknowledged gap is a plan, an unacknowledged one is a bug.
Being stuck, handled well
You will get stuck. It is expected and it is not disqualifying — freezing is. What is being measured is whether you have a procedure for it. Work this ladder out loud, in order, and say which rung you are on.
| Rung | Do this | Why it works |
|---|---|---|
| 1 | Re-read the constraints and the exact wording of the ask | Most stuckness is a misread — "subsequence" vs "subarray," "any" vs "all," "at most" vs "exactly." The constraint bound also re-states the target complexity you may have drifted from. |
| 2 | Work a tiny example by hand — n = 1, n = 2, n = 3 | You are looking for the rule your hand is following. Solving n = 3 manually and asking "what did I just do?" recovers the recurrence more often than staring at the general case. |
| 3 | Ask "what shape is this?" | Not "have I seen this problem" but: is it a graph? intervals? a tree of choices? a search over a monotonic answer space? Shape recall is far more reliable than problem recall. |
| 4 | Ask whether it is two known patterns composed | Advanced problems usually are. Sort + two pointers. Trie + backtracking. Binary search on the answer + a greedy feasibility check. Heap + hashmap. Topological order + DP. Say the two names out loud. |
| 5 | Relax the problem, solve the easier version | Drop a constraint (assume sorted, assume no duplicates, assume k = 1, assume the array is positive). Solve that, then re-introduce the constraint and see what breaks. Partial credit is real credit. |
| 6 | State where you are stuck, precisely, and take the hint | "I have an O(n²) solution and I know the bottleneck is re-scanning the prefix; what I can't see is a structure that gives me the max of a shrinking window in O(1)." That is a targeted request, and it lets the interviewer give a small hint rather than a large one. |
Note what that phrasing does: it converts "stuck" into "executing a deliberate step." Interviewers are instructed to give hints; taking one gracefully costs far less than most candidates fear, and refusing to ask while burning ten minutes costs far more.
Test before you say "done"
Declaring completion and letting the interviewer find the bug is the most avoidable score loss in the entire interview. Finding it yourself, out loud, converts the same bug into a positive signal. Trace the given example first — line by line, tracking real variable values, not vibes — then run a deliberately chosen edge case.
| Edge case | What it catches |
|---|---|
Empty input [] / "" | arr[0] on an empty array, Math.max() of nothing returning -Infinity, a while loop that assumed one element |
| Single element | Two-pointer and sliding-window loops whose body never executes; left < right vs left <= right |
All duplicates [5,5,5,5] | Dedupe logic, Set-vs-Map choices, two-pointer skip loops, "distinct" requirements |
| Already sorted / reverse sorted | Worst-case quicksort partitioning, degenerate BSTs, and off-by-one at the array ends |
| Two elements | The smallest case where a comparison or swap can be backwards |
| Negatives and zero | Greedy and sliding-window sum arguments that silently assume positivity; division and modulo by zero |
| All elements identical to the target / none matching | The "not found" return contract you agreed on in minute two |
| Maximum n from the constraints | Recursion depth (JS blows up around 10⁴-10⁵ frames), integer overflow past 2⁵³, O(n²) memory |
while (left <
right) never executes, so I fall through to the not-found return —
correct. And an empty array: nums.length - 1 is -1, the loop
still doesn't execute, still correct. I'm happy with this."
Discussing tradeoffs at a senior level
The clearest seniority marker in the last ten minutes is raising a tradeoff before you are asked, and framing it against a use case rather than in the abstract. Intermediate candidates report complexity. Advanced candidates report complexity, name the alternative they rejected, and say what would change their mind.
| Axis | The sentence to have ready |
|---|---|
| Time vs space | "This is O(n) time with an O(n) hashmap. If memory were the binding constraint I'd sort in place and use two pointers — O(1) extra space, O(n log n) time. Which matters more here?" |
| Preprocess vs per-query | "If this is called once, the linear scan is right. If it's called a million times on the same array, I'd build prefix sums up front — O(n) once, then O(1) per query." |
| Worst case vs average case | "Quickselect is O(n) expected but O(n²) adversarially. If this is on a user-facing path where input could be hostile, I'd take the heap's guaranteed O(n log k) instead." |
| Simplicity vs constant factor | "The bitmask version is maybe 5× faster per node but noticeably harder to read. For n ≤ 12 I'd ship the readable one and leave a comment about the optimization." |
| Amortized vs bounded latency | "The dynamic array is amortized O(1) but a single resize is O(n). If this were in a real-time path I'd pre-size it." |
| Exact vs approximate | "For exact distinct counts I need O(n) memory. If an error of a percent or two is acceptable at this scale, HyperLogLog does it in kilobytes." |
| Mutating vs pure | "I'm sorting the input in place, which is faster but destroys the caller's array. If it's shared, I'd copy first and pay the O(n)." |
Every one of those ends in a question or a condition. That is deliberate — it turns a monologue into a design conversation and invites the interviewer to supply real-world context, which is the exact interaction they are trying to score. It is also honest: which side of a tradeoff is correct genuinely depends on information you do not have.
Two more things to have ready without being asked. How would this scale past one machine? — even a sentence ("if the array doesn't fit in memory, I'd external-sort by chunk, or shard by hash of the key and merge") shows the thinking extends past the whiteboard. And what would you test? — naming three unit tests and one property ("the output should always be a permutation of the input") signals engineering maturity that pure DSA never reaches.
Signals that separate an advanced performance from an intermediate one
- Constraints are read as a hint, not as trivia. "n ≤ 20, so they intend an exponential-in-n solution — that means bitmask" is said in the first two minutes, not discovered at minute thirty.
- A brute force is stated with its complexity before any optimizing starts. There is always something on the board, and the improvement is measured against a named baseline rather than asserted.
- Patterns are named out loud as they are chosen. "Monotonic stack, because I need the next greater element and each index is pushed and popped once" — not just correct code that happens to be a monotonic stack.
- The bottleneck is identified explicitly ("the expensive part is re-scanning the prefix") and the optimization is presented as buying that specific work back with a specific structure.
- Getting stuck produces a described procedure, not silence. Re-read constraints → hand-trace a tiny case → identify the shape → check for two composed patterns → relax a constraint → ask a precise question.
- The candidate tests their own code before declaring done — a real trace with real values, plus a deliberately chosen edge case, and finds their own off-by-one.
- Tradeoffs are raised unprompted and tied to a use case, with a stated condition that would flip the decision, rather than a memorized complexity table recited on request.
- Corrections are absorbed without defensiveness. A hint is taken, integrated, and credited — "good catch, that breaks when the values are negative; let me fix the invariant" — because the interviewer is simulating what code review with you feels like.
- Uncertainty is stated honestly and bounded. "I'm fairly sure this is O(n log n) amortized but I'd want to double-check the resize cost" beats a confident wrong claim every time, and it is the difference between an engineer you can trust and one you have to verify.
Opens in the editor — write it, run it, and check it against real tests.