Coding interview strategy: how to think
Most candidates fail not because they don't know algorithms, but because they don't have a repeatable process. This lesson is the "how to think"; files 01–18 are the "what to code".
Why this matters
Candidates read the prompt, freeze, and either blurt the first idea or sit silent. The interviewer is grading a signal you can fully control: "can this person take an ambiguous problem and drive it to a working, analyzed solution while thinking out loud?" That signal is a process, and a process can be rehearsed until it's automatic. This lesson is the navigation hub of the series: a framework, a way to read target complexity off the constraints, a pattern map pointing at every other lesson, then communication, common mistakes, edge cases, and a study plan.
(1) The framework — UMPIRE
A named sequence so you never freeze. Say each step out loud.
- U — Understand. Restate the problem in your own words. Ask clarifying questions: input types/ranges? sorted? duplicates allowed? negative values? empty input? in-place or new output? one answer or all? what to return on ties / no-answer? Never start coding until you can state the contract precisely.
- M — Match. What category is this? (See the pattern map below.) "Sorted + pair" smells like two pointers; "contiguous subarray" smells like sliding window; "all combinations" smells like backtracking. Matching narrows the search space of techniques.
- P — Plan. Walk a concrete example by hand. State a brute-force approach first (it proves you understand the problem and gives a correctness baseline), then its complexity, then propose the optimization. Get the interviewer to nod before you type.
- I — Implement. Code the planned approach cleanly. Narrate as you go. Use good names. Don't prematurely optimize syntax; correctness first.
- R — Review. Re-read your code as if it were someone else's. Trace the example through it line by line. Check the edge cases you surfaced in step U.
- E — Evaluate. State final time and space complexity. Mention trade-offs and what you'd change with different constraints (e.g. "if n were 1e9 I'd...").
(2) Reading complexity off the constraints
The input size n (often given in the constraints) tells you the target complexity, which in turn tells you the family of techniques. ~1e8 simple operations per second is the rough mental budget.
| Constraint on n | Target | What it unlocks |
|---|---|---|
| n ≤ 12 | O(n!) | permutations / brute force over orderings |
| n ≤ 20 | O(2ⁿ) | subsets, bitmask DP, backtracking |
| n ≤ 100 | O(n³) | 3 nested loops, Floyd-Warshall, interval DP |
| n ≤ 500 | O(n³) | cubic still fine |
| n ≤ 5000 | O(n²) | 2 nested loops, simple DP, pair scans |
| n ≤ 1e5 | O(n log n) | sort, heap, binary-search-the-answer |
| n ≤ 1e6 | O(n) / O(n log n) | single pass / linearithmic |
| n ≤ 1e7 | O(n) | hashing, two pointers, sliding window |
| n ≥ 1e9 | O(log n) / O(1) | binary search on answer, math/closed form |
And the special case: tiny n, huge values — the value range (not n) may drive complexity (binary search on a value range, or O(value) DP).
Use it backwards: if the brute force is O(n²) but n ≤ 1e5, you need to find an O(n log n) or O(n). The constraint is a hint, not just a limit.
(3) Pattern recognition — signal → technique → lesson
This is the heart of "matching". Each signal points to the lesson in this folder where the technique lives.
| Signal | Technique | Lesson |
|---|---|---|
| sorted array / find a pair | two pointers / binary search | 05, 06 |
| contiguous subarray / substring | sliding window / prefix sum | 05, 07 |
| top k / kth largest / k closest | heap (or quickselect) | 11, 18 |
| shortest path, unweighted | BFS | 12 |
| shortest path, weighted ≥ 0 | Dijkstra (heap) | 12 |
| explore all paths / flood fill | DFS | 12 |
| all combinations / permutations | backtracking | 13 |
| count ways / optimal substructure | dynamic programming | 14 |
| next greater / smaller element | monotonic stack | 08 |
| connected groups / merge sets | union-find / DFS | 12, 17 |
| prefix queries / autocomplete | trie | 17 |
| task ordering with dependencies | topological sort | 12 |
| merge / overlapping intervals | sort + sweep line | 15 |
| fast lookup / dedupe / count | hashmap / hashset | 02, 07 |
| balanced brackets / nesting / undo | stack | 08 |
(4) Communication, common mistakes, edge cases
Communication
- Think out loud constantly. Silence reads as "stuck".
- State assumptions before coding; confirm them.
- When stuck, narrate the obstacle ("the issue is duplicates double-count") — the interviewer often nudges you.
- Propose brute force, then optimize. Don't jump to the clever trick silently.
- Announce complexity unprompted at the end.
Common mistakes
- Coding before fully understanding the contract.
- Ignoring the constraints (writing O(n²) when n = 1e6).
- Off-by-one in loops/binary search (use half-open
[lo, hi)). - Mutating a collection while iterating it.
- Forgetting to return / returning the wrong variable.
- Not testing edge cases before declaring "done".
Edge cases to always check
- Empty input (
[],"",None). - Single element / single character.
- All-equal / duplicates (do dupes change the count or the answer?).
- Negative numbers and zero.
- Already-sorted / reverse-sorted input.
- Very large input (does the algorithm scale to the stated
n?). - Integer overflow: not a concern in Python (arbitrary-precision ints) — but mention it anyway; in Java/C++ you'd use 64-bit or guard the sum.
(5) A short study plan
- Week 1 — Fundamentals: arrays/strings, hashing, two pointers, sliding window, stacks/queues, binary search (lessons 01–08-ish).
- Week 2 — Trees & graphs: BFS/DFS, recursion, topological sort, heaps (11, 12).
- Week 3 — Dynamic programming: 1D, 2D, knapsack, intervals; backtracking (13, 14).
- Week 4 — Advanced + review: union-find, tries, sorting internals (17, 18), and timed mock interviews. Always rehearse UMPIRE out loud.