The pattern-recognition checklist
You now own ten patterns. Interview problems rarely announce which one they want, and they leak it through trigger phrases.
This table is the course in one screen. Read the cue, name the pattern, then recall the lesson that built it.
| The problem says | Reach for | Built in |
|---|---|---|
| sorted input, or O(log n) required | binary search | 2-2 |
| smallest or largest X that passes a monotonic test | binary search on the answer | 2-3 |
| pairs or order in an array, no better idea yet | sort-then-solve | 3-3 |
| pair in sorted data, palindrome, converging ends | two pointers | 4-1 |
| best contiguous run, substring, or subarray | sliding window | 4-2 |
| repeated range totals, count subarrays summing to k | prefix sums | 4-3 |
| all subsets, permutations, or boards | backtracking | 6-1, 6-2 |
| fewest steps, all steps equal cost | BFS | 7-2 |
| explore or count regions, connectivity | DFS | 7-1, 7-2 |
| fastest route with weights ≥ 0 | Dijkstra | 10-2 |
| prerequisites, must-come-before | topological sort | 10-3 |
| max, min, or count over choices that interact | DP | 9-1 to 10-1 |
| "seen before?", counting, complements | hash set or dict | 1-1 |
Greedy from unit 8 is the special case, since it has no trigger phrase of its own. Propose it, hunt for a counterexample, and only trust it with an exchange argument.
The table is a starting point rather than a decision procedure. Patterns compose, and the harder problems are two rows at once, such as a binary search whose feasibility test is a greedy pass.
BFS, because it is fewest steps with equal step costs.
Minimum number of moves plus every move costing the same is the BFS trigger from lesson 7-2, and a maze is a grid graph where each open cell connects to its open neighbors.
The other three candidates all fail for different reasons, and being able to say why is the complete answer.
DFS explores the whole maze but returns whatever route it wandered down first, which has no relationship to the shortest one.
Dijkstra would give the right answer and is overkill without weights, paying a log factor for a priority queue that a plain deque handles.
Backtracking enumerates every route, which is exponential, when the question asks for one optimal distance rather than all the paths.
Binary search on the answer, since capacity is numeric and the feasibility question is monotonic.
The shape is the smallest value that passes a test, which is lesson 2-3's pattern and the same structure as the min_speed problem there.
Monotonicity is the property that makes it work. A bigger capacity never delivers fewer packages, so once some capacity succeeds every larger one does too, and the yes/no answers form a run of no followed by a run of yes.
The search range is also easy to pin down. The lowest possible capacity is the heaviest single package, since it must fit on some day, and the highest is the sum of all packages, which finishes in one day.
The feasibility check inside is a simple greedy pass. Load packages in order until the next one would exceed the capacity, then start a new day, and compare the day count with d.
That composition is the lesson. Binary search on the answer plus a greedy check is one of the most common two-pattern combinations in interviews.
merge_intervals
An interview staple that composes sort-then-solve with neighbor merging.
def merge_intervals(intervals): intervals.sort() merged = [intervals[0]] for start, end in intervals[1:]: if start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end]) return merged print(merge_intervals([[1, 3], [8, 10], [2, 6], [15, 18]])) print(merge_intervals([[1, 4], [4, 5]]))
Output
[[1, 6], [8, 10], [15, 18]] [[1, 5]]
intervals.sort() sorts by start time, since tuples and lists compare position by position and the start is first. That is the whole setup step.
After sorting, an interval can only overlap the last merged one, which is lesson 3-3's locality argument. Every earlier merged interval ends before this one begins.
The max() matters more than it looks. [1, 10] followed by [2, 3] must stay [1, 10] rather than shrinking to [1, 3], because a fully contained interval adds nothing.
merged[-1][1] = ... mutates the last merged interval in place, which is why the seed is intervals[0] as a list rather than a tuple.
Touching counts as overlapping here, so [1, 4] and [4, 5] merge into [1, 5]. Changing <= to < would keep them separate, and which one the problem wants is worth asking.
The cost is O(n log n) for the sort plus O(n) for the pass, and the sort dominates, which is the usual shape of a sort-then-solve answer.
Backtracking from unit 6, enumerating all combinations with the choose, explore, undo loop.
The ask is every possibility rather than the best one, and "all", "every", and "generate" are the giveaway words. Nothing here is being maximized or counted.
The prune is straightforward. Once a path holds 3 people it is complete, so it gets recorded and the branch stops rather than continuing to add.
A second prune keeps the tree small. Only consider people after the last one picked, which stops the same team appearing in six different orders and turns permutations into combinations.
The size is comfortable. C(10, 3) = 120 leaves, well inside the range where enumeration is the intended answer.
The size estimate is part of the answer too. If the ask were teams of 3 from 10,000 people, C(10000, 3) is about 1.7 × 10¹¹, and the problem would have to be asking for a count rather than a listing.