31 of 32 · 6 min
What to do when you have never seen it
Every page so far taught a tool. The interview does not hand you a labelled problem. This page is the method for the moment when nothing is obviously the answer.
Do not start coding
The most common failure is writing code within thirty seconds and discovering at minute twenty that the approach cannot work. Time spent understanding is not time lost.
The sequence
1. Restate it. Say the problem back in your own words. Misunderstandings surface here and cost nothing.
2. Ask about the input. How large? Sorted? Duplicates? Negative? Empty? These are not stalling, they are the specification, and the size in particular decides the approach:
| Input size | Suggests |
|---|---|
| up to 20 | exponential is fine: subsets, permutations, bitmask |
| up to 5,000 | O(n squared) |
| up to 100,000 | O(n log n): sorting, heap, binary search |
| up to 10 million | O(n) or O(log n) only |
3. Work an example by hand. A small one, on paper. Then a tricky one. What you do by hand is usually the algorithm, and noticing what you repeat is where the optimisation is.
4. Say the brute force out loud. "I could check every pair, that is O(n squared)." This is not a weak answer. It establishes a baseline, proves you understand the problem, and gives you something to improve. An interviewer would rather have a working brute force than an elegant silence.
5. Find the waste. Nearly every optimisation is one of:
recomputing something -> store it (hash map, prefix sums, DP) scanning to find -> keep it ordered (heap, sorted array, BST) trying every pair -> two indices (two pointers, sliding window) exploring the same state repeatedly -> memoise (dynamic programming)
6. Then code it, saying what you are doing as you go.
7. Test it on paper. The empty input, one element, all equal, the largest case. Finding your own bug before being told is worth a great deal.
The signals, collected
| The problem says | Consider |
|---|---|
| "sorted array" | binary search, two pointers |
| "contiguous subarray" | sliding window, prefix sums |
| "k largest" or "k closest" | heap of size k |
| "how many ways" or "best possible" | dynamic programming |
| "shortest path", "fewest steps" | BFS, or Dijkstra with weights |
| "prerequisites", "ordering" | topological sort |
| "all permutations", "all valid" | backtracking |
| "prefix" or "autocomplete" | trie |
| "are these connected" | union find |
If you get stuck
Say so, and say where. "I can do this in O(n squared), I think there is a way to avoid the inner loop, I am trying to work out what to store." That is a thinking engineer, and interviewers hire those. Silence gives them nothing to work with and nothing to credit.