The Pattern-Recognition Playbook
A cheat sheet from problem cues to the right technique, so you spend your minutes solving instead of flailing.
Most coding interviews are not testing whether you have memorized a thousand problems. They are testing whether you can hear a prompt, recognize its shape, and choose a tool quickly enough to spend the remaining minutes reasoning. This playbook is the cheat sheet for that first decision.
The move is not “jump to a memorized solution.” The move is: extract the cues, name the likely pattern, confirm the assumptions with the interviewer, then solve from first principles. Pattern recognition buys time; it does not replace thinking.
The mental model
Treat every prompt as a routing problem. Before coding, ask three questions:
- What structure is hidden in the input? Sorted order, contiguity, graph edges, a tree, intervals, dependencies, frequencies.
- What operation is expensive in the brute force? Searching, re-counting, recomputing overlapping work, scanning every pair, exploring repeated states.
- What invariant would make that operation cheap? A hash lookup, a monotonic stack, a sliding window condition, a priority queue, a DP state.
A good pattern choice sounds like this:
| Step | What you say out loud | What it proves |
|---|---|---|
| Cue | “The array is sorted and we need a pair.” | You noticed structure. |
| Pattern | “I’ll try two pointers before hashing.” | You know the tool. |
| Invariant | “Moving the left pointer only increases the sum.” | You can justify it. |
| Trade-off | “This keeps O(1) extra space.” | You understand cost. |
Pattern recognition
| If the prompt says… | Reach for… | Why |
|---|---|---|
| Sorted array; find pair/triplet; remove duplicates in-place | Two pointers | Order lets one pointer’s movement predictably increase or decrease the target condition. |
| Sorted array; find boundary; minimum feasible value; “first true” | Binary search | A monotonic predicate lets you discard half the search space. |
| Contiguous subarray or substring; longest/shortest window | Sliding window | The answer is a range that can grow and shrink while maintaining an invariant. |
| Running range sums; many range queries; subarray sum equals k | Prefix sums | Convert repeated range summation into subtraction of two precomputed totals. |
| “Seen before”; duplicates; counts; anagrams; complement to target | Hash map or set | Replace repeated searches with O(1) membership, counts, or lookup by key. |
| Group by equivalence: same letters, same slope, same signature | Hash map keyed by canonical form | Turn “are these equivalent?” into “do these produce the same key?” |
| Top-k; kth largest; merge k streams; schedule by next priority | Heap or priority queue | You repeatedly need the current min/max without sorting everything each time. |
| Running median or balance two halves | Two heaps | One heap owns the lower half, one owns the upper half; rebalance around the median. |
| Prefix lookup; autocomplete; dictionary of words; wildcard word search | Trie | Shared prefixes avoid re-scanning strings and make prefix queries natural. |
| Connectivity; islands; groups; components; “can reach” | BFS/DFS or union-find | Model relationships as graph edges, then traverse or merge connected components. |
| Dynamic connectivity under many union/find queries | Union-find | Near-constant merges and same-set checks beat repeated graph traversals. |
| Shortest path in unweighted graph or grid | BFS | Layer-by-layer traversal finds the fewest edges first. |
| Shortest path with non-negative weights | Dijkstra | A priority queue expands the currently cheapest frontier safely. |
| Dependencies; prerequisites; ordering; “can finish all” | Topological sort | Directed acyclic order reveals whether prerequisites can be satisfied. |
| “Number of ways”; “minimum cost”; “maximum profit” with choices | Dynamic programming | Overlapping subproblems can be cached once you define state and transition. |
| Choose or skip each item; combinations; subsets; permutations | Backtracking | The solution space is a decision tree, often with pruning constraints. |
| Intervals; meetings; calendars; overlapping ranges | Sort + sweep line | Sorting endpoints makes conflicts and active counts visible in one pass. |
| Next greater/smaller; stock span; remove dominated previous elements | Monotonic stack | Keep only candidates that have not been dominated by a better later value. |
| Sliding-window maximum/minimum | Monotonic deque | Maintain best candidates in window order while dropping expired and dominated values. |
| Parentheses; undo; nested parsing; last-opened must close first | Stack | LIFO order matches nested structure. |
| LRU cache; O(1) remove from middle; in-place list surgery | Linked list plus hash map | The map finds nodes; the linked list updates recency or ordering in O(1). |
| Cycle in linked list; middle node; palindromic list | Fast/slow pointers | Two speeds reveal cycles, midpoints, and second-half boundaries. |
| Tree traversal; validate BST; lowest common ancestor | DFS recursion | Tree problems usually decompose into left answer, right answer, combine. |
| Level order; nearest node by edge count | BFS queue | FIFO order preserves distance layers. |
| Matrix with four-direction movement | Graph traversal | Cells are nodes; neighbor rules are edges. |
| Greedy scheduling; maximize count; earliest finish; merge by endpoint | Sort by the decisive key | The sorted key creates a local choice that can be justified by exchange. |
| Bit masks; subsets of small n; parity/toggle; XOR uniqueness | Bit manipulation | Bits represent compact state, membership, or parity. |
| Randomized set with O(1) insert/delete/getRandom | Array plus hash map | The array gives random indexing; the map gives O(1) location for swap-delete. |
| Stream of events; rate limits; time-window counts | Queue/deque plus counters | Expire old events while maintaining current window state. |
| Need lexicographically smallest valid sequence | Greedy plus stack or heap | Maintain feasibility while choosing the smallest next candidate. |
| “At most k” distinct/chosen/errors | Sliding window with counts | Counts tell you when a window violates the budget and how to shrink it. |
| “Exactly k” | Transform from at-most counts or use prefix counts | Exactly is often atMost(k) - atMost(k - 1) or a prefix-frequency lookup. |
| “Return all paths” or “all valid boards” | Backtracking | You must enumerate, not just optimize. |
| Repeated state in recursion; exponential brute force | Memoization | Cache by the smallest state that determines the future. |
Variations
Worked problems
These are not about finishing an implementation. They are reps for the first two minutes: hear the prompt, identify the pattern, and justify it.
Ambiguous prompt: longest stable segment
You are given an array of sensor readings and an integer k. Return the length of the longest contiguous segment that contains at most k distinct readings.
Approach. The words “longest,” “contiguous,” and “at most k distinct” are the cues. Contiguity rules out sorting. “At most” suggests a window that can become invalid and shrink until valid again. Counts tell you when a distinct value enters or leaves the window.
Show solution
The pattern is sliding window with a frequency map.
Identification:
| Cue | Meaning |
|---|---|
| “Contiguous segment” | The answer is a window, not a subsequence. |
| “Longest” | Expand greedily and remember the best valid length. |
“At most k distinct” |
Maintain counts and shrink while the invariant is violated. |
The invariant is: the current window has no more than k distinct readings. Move right one step at a time, increment that reading’s count, and while the map has more than k keys, move left and decrement counts. After the shrink, the window is valid, so update the best length.
A common wrong turn is sorting the readings. Sorting destroys contiguity, which is the whole constraint.
Ambiguous prompt: cheapest upgrade path
A service can run in many configurations. Each possible upgrade from one configuration to another has a non-negative cost. Given a start and target configuration, find the cheapest sequence of upgrades.
Approach. The object names are a distraction. Configurations are nodes; upgrades are weighted directed edges. “Cheapest sequence” is a shortest-path question. Because costs are non-negative, Dijkstra is the default candidate.
Show solution
The pattern is Dijkstra’s shortest path.
Identification:
| Cue | Meaning |
|---|---|
| “Configurations” and “upgrades” | Hidden graph: states and transitions. |
| “Cost” on each upgrade | Weighted edges, not plain reachability. |
| “Cheapest sequence” | Minimize total path weight. |
| “Non-negative” | Dijkstra is valid; negative weights would require a different algorithm. |
You would say: “I’ll model each configuration as a node and each upgrade as an edge with cost. Since all costs are non-negative, I’ll use a priority queue to always expand the cheapest known configuration next. The first time I pop the target from the queue, I have the cheapest total cost.”
If the interviewer instead asked for the fewest number of upgrades, with no costs, that would become BFS.
Ambiguous prompt: release order
You have a list of packages. Some packages depend on others being released first. Return a valid release order, or report that no valid order exists.
Approach. “Depends on” and “order” are the cues. This is not sorting by name or date; it is ordering a directed graph under prerequisite constraints. If a cycle exists, no release order can satisfy every dependency.
Show solution
The pattern is topological sort with cycle detection.
Identification:
| Cue | Meaning |
|---|---|
| “A depends on B” | Directed edge B → A. |
| “Valid order” | Need every edge to point forward in the output. |
| “No valid order” | A directed cycle blocks completion. |
A strong plan: build an adjacency list and indegree count. Push all zero-indegree packages into a queue, repeatedly emit one, and decrement its dependents. If you emit all packages, the order is valid. If some remain, they are trapped in a cycle.
This is the same shape as course schedule, build systems, migrations, and task pipelines. The nouns change; the dependency graph does not.
Confirm before you commit
Pattern recognition should sound provisional for the first minute: “This looks like a sliding-window problem because the answer is contiguous and bounded by a budget. Let me test that with a small example.” That sentence does three things: it names the cue, names the tool, and invites correction before you spend twenty minutes implementing the wrong idea.