Capstone: Which Pattern Is This?
You now own a small toolbox: seen-sets, complement lookups, counting, canonical keys, prefix sums, two pointers, binary search on lists and on answers, fixed and variable windows, and backtracking. In an interview nobody tells you which tool the problem wants. This final lesson is the habit that picks one in the first minute, before any code exists.
The rule
Name the pattern before you write a single line of code.
The first lesson of this course gave three questions. With everything since, they grow into a recognition ladder. Climb it from the top and stop at the first rung that fits:
| Rung | Signal | Reach for |
|---|---|---|
| 1 | "list every", "all ways", tiny limits | backtracking: subsets, orderings or pruned combinations |
| 2 | "contiguous", "stretch", "substring" | sliding window, or prefix sums if values can be negative or ranges are asked many times |
| 3 | sorted data, pairs or triples, "both ends" | two pointers, or binary search to locate a value or a boundary |
| 4 | "the smallest (or largest) x that still works" | binary search on the answer, with a yes-no checker |
| 5 | "seen before", "partner", "how many of each", "group" | set, dictionary, counts or canonical keys |
Then check the fit against the limits, as in the very first lesson. A pattern that is too slow for the largest input, or that needs sorted data you are not allowed to sort, is the wrong rung: climb on.
Two habits make the ladder reliable. Say why the tempting rung fails, not just why the chosen one fits: "not a window, because values can be negative" is exactly the reasoning interviewers hope to hear. And remember that patterns combine: a window that keeps a dictionary of counts, prefix sums that lean on a complement lookup, binary search whose checker is a greedy pass.
The shortcut
Read the problem once for its story and once, slowly, for its signal words and limits. Underline them. The rung usually announces itself.
The problem
A game logs each round's score change in order, and penalties make some changes negative. Up to 100,000 rounds. How many stretches of consecutive rounds add up to exactly 50?
Drills
Answer fast — trust the rule.
"A sorted list of house numbers: find two that add up to 1,000, using no extra memory." Which pattern?
"Find the smallest battery size that lets a drone finish its route with at most 5 recharges. A helper says yes or no for any size." Which pattern?
"The longest stretch of a gene string that contains at most 2 different letters." Which pattern?
"List every order in which 5 guests can be seated in a row." Which pattern?
"An unsorted list of 100,000 usernames: find two that are the same apart from capital letters." Which pattern?
Remember
- Name the pattern before you write a single line of code.
- Shortcut: climb the ladder (every, contiguous, sorted, smallest that works, seen), then check the limits.
- Trap: stopping at a tempting rung without saying why the others fail.