3. The Five-Step Problem Method
The idea
An interview is not a memory test. Nobody expects you to have seen the exact problem before. What they are watching is what you do in the first thirty seconds after reading a problem you have not seen — and for most people, that thirty seconds is a blank.
This page removes the blank. Every problem in this course, and every problem you will meet in a real round, is attacked with the same five moves, in the same order. You will do them so many times that they become automatic, and "I have no idea" turns into "okay, Move 1".
Here they are. Then we will run them on a real problem.
Move 1 — Say it back. Repeat the problem in your own words. Make a tiny example by hand, five to eight items. Name the weird inputs: empty, one item, all the same, already sorted, negative numbers. This is where you find out you misread the question — and everybody misreads the question sometimes.
Move 2 — Solve it the dumb way. The most obvious method that is definitely correct, however slow. Say how many steps it takes. You are not going to code this (usually). You are doing it because the dumb way shows you exactly where the waste is.
Move 3 — Find the waste. Look at the dumb way and ask: where am I doing the same work twice? Then look at the problem and ask: which word is the trigger? Certain words point at certain patterns, and the table at the bottom of this page lists them.
Move 4 — Swap in the pattern. Walk your tiny example through the new method by hand first. Only when it works on paper do you write code.
Move 5 — Prove it. Trace the code on the tiny example. Then the weird inputs. Then say the time and space cost in one sentence.
Let's solve one
The most famous interview problem of all:
Two Sum. You are given a list of numbers and a target. Find two numbers in the list that add up to the target, and hand back their box numbers.
Move 1 — Say it back. "I have a row of numbers. I need to pick two different boxes whose numbers add to the target, and say which boxes." Tiny example: [3, 8, 11, 2, 7], target 9. By hand: 2 + 7 = 9, and they sit in boxes 3 and 4. Weird inputs: a list with fewer than two numbers (no answer possible); a list where nothing adds up (what do we hand back?); two equal numbers like [4, 4] with target 8 (two different boxes, same value — allowed); negative numbers (fine, nothing changes).
Move 2 — Solve it the dumb way. Pick a box. Compare it with every box after it. If the two add to the target, done. Otherwise pick the next box and repeat. For every box, we look at every other box: that is every pair, O(N²). With five numbers that is ten pairs — no problem. With a hundred thousand numbers it is five billion pairs, and the interviewer's eyebrows go up.
Move 3 — Find the waste. Stand on box 3, which holds 2. You already know exactly what you are looking for: 9 − 2 = 7. Yet the dumb way scans the whole row to see whether a 7 exists. That scan is the waste. If only you had a notebook where you could ask "have I seen a 7, and in which box?" and get the answer instantly.
That notebook exists. It is called a hash map (Module 1 is all about it). For now, all you need to know: you can write "value → box number" into it, and later look up any value in one step. The trigger word here was "have I seen this before?" — whenever you catch yourself asking that, the answer is a hash map.
Move 4 — Swap in the pattern. New plan: walk the row once. At each box, ask the notebook "have you got target − this number?" If yes, done — the notebook tells you the other box. If no, write this number and its box into the notebook and move on.
Walk the example by hand:
One walk. Five boxes, five steps. Now the code:
Move 5 — Prove it. Trace [3, 8, 11, 2, 7], target 9, through the code: it does exactly what the picture did and hands back [3, 4]. Now the weird inputs. Empty list: the loop never runs, we hand back []. One item: same. [4, 4], target 8: at box 0 we need 4, the notebook is empty, we write 4 → 0; at box 1 we need 4, the notebook has it, answer [0, 1]. Correct — and notice we asked the notebook before writing, so a number never pairs with itself. Negatives: nothing special happens.
Cost: "O(N) time, because one walk; O(N) space, because the notebook can grow to one entry per item." We traded a bit of space for a lot of time. That trade is the most common move in all of interviewing.
The trigger words
Move 3 gets easier with a table. You will build this up module by module; here is the short version.
| When the problem says… | Think… | Module |
|---|---|---|
| "have I seen this?", "count how many", "group by" | hash map — the notebook | 1 |
| "sorted", "pair that adds to", "in place" | two pointers — two fingers on one row | 2 |
| "longest / shortest run of boxes next to each other" | sliding window | 3 |
| "sorted" + "find" or "smallest value that works" | binary search — the phone book | 4 |
| "most recent", "undo", "matching brackets", "next bigger" | stack — a pile of plates | 5 |
| "k largest", "top k", "keep the best few" | heap | 9 |
| "all combinations", "all arrangements" | backtracking | 10 |
| "connected", "shortest path", "grid of cells" | graph search | 11–12 |
| "best answer built from smaller answers", "number of ways" | dynamic programming | 14 |
When you are stuck
Being stuck is normal and expected. Do not go quiet. Say what you have ruled out. Then try one of these: go back a move (usually you skipped Move 2); make the example smaller; ask "what if the list were sorted?"; ask "what if I walked it backwards?". If nothing comes in a minute or two, ask for a hint — a hint costs a little, silence costs the round.
Practice
Solve Two Sum on the sheet for real, against hidden tests: 2 Sum in an Array. Do it with the Five Moves written down on paper next to you. Then do it again without the paper.
In the room
Interviewers can tell within a minute whether you have a method or are hoping for inspiration. The Five Moves are the method, and they are meant to be spoken: "Let me say the problem back… the obvious way is every pair, which is O(N²)… the waste is the rescan, so a hash map… let me walk my example… let me test the empty case." Say those sentences and you have already answered the question they care about most: can this person think in front of me?