Stage 1 · Code
Interview Synthesis
Turn Constraints Into a Pattern
Translate bounds, ordering, mutation rules, and output shape into candidate families—and reject patterns whose invariants do not fit.
Treat Constraints as Evidence
A pattern name should be the result of analysis, not a reflex triggered by one keyword. Start by extracting evidence from the prompt: input size, value range, ordering, whether values are positive, whether mutation is allowed, whether the output is one answer or every answer, and whether the operation happens once or repeatedly. Those facts tell you which complexity is affordable and which invariants are even possible.
| Constraint signal | Candidate families | Question that validates the fit |
|---|---|---|
| n is around 10⁵ or larger | Linear scan, hashing, pointers, windows, stacks, heaps, graph traversal | Can each item enter and leave the maintained state only O(1) times? |
| Input or answer space is ordered | Two pointers, binary search, interval sweep, k-way frontier | What ordering rule lets one decision safely discard alternatives? |
| All values are non-negative or strictly positive | Sliding window, greedy accumulation | Does moving a boundary change the measured quantity monotonically? |
| Values lie in 1..n and mutation is allowed | Index placement or cyclic-sort reasoning | Can value v be placed at a deterministic index without losing information? |
| Need repeated minimum, maximum, median, or top k | Monotonic deque, one heap, two heaps, bounded heap | Which candidates can be discarded permanently, and which must remain queryable? |
| Need all combinations, paths, or assignments | Backtracking, sometimes dynamic programming for counting | Is the output itself exponential, or can equivalent states be merged? |
| Same state is reached through many choices | Memoization or tabulation | Can the subproblem be named with a small, complete state key? |
| Relationships, prerequisites, grids, or transitions | BFS, DFS, topological sort, union-find, shortest path | What are the nodes and edges, and does order, connectivity, or distance matter? |
The strongest classification statement includes a rejection: “A dynamic window is plausible because values are positive and the sum changes monotonically; it would be invalid if negative values were allowed.” That is evidence-based reasoning, not template matching.
Build and Rank a Shortlist
In an interview, do not silently search your memory for the one correct label. Name two or three candidates, then rank them by the invariant they would maintain. The best candidate is the simplest one whose invariant proves both correctness and the required complexity.
- Translate the largest input bound into a target complexity. For n = 200, exponential search may still be impossible while O(n²) may be acceptable; for n = 200,000, start near O(n) or O(n log n).
- Identify structure: sortedness, contiguous ranges, tree hierarchy, graph edges, bounded values, repeated queries, or stream updates.
- Name candidate state. Examples: earliest prefix index, counts inside a window, unresolved indices on a stack, best cost for state (i, budget), or the smallest item on each sorted frontier.
- Test monotonicity and information loss. Ask whether advancing a pointer, popping a stack item, or discarding a heap element can ever remove a future optimum.
- Choose the candidate with the shortest proof, then state why the runner-up is weaker or invalid.
| Prompt | Shortlist | Ranking decision |
|---|---|---|
| Find a pair sum in a sorted array | Hash map; opposite pointers; binary search per item | Opposite pointers use the ordering directly, need O(1) extra space, and eliminate one endpoint after each comparison. |
| Maintain the median of a stream | Repeated sorting; ordered tree; two heaps | Two heaps expose both sides of the partition and rebalance in O(log n) per insertion. |
| Count paths through a grid with blocked cells | Backtracking; 2-D DP | If only the count is needed, DP merges paths that reach the same cell; enumerating every path repeats equivalent work. |
| Return k most frequent values | Sort all frequencies; bounded min-heap; buckets | Choose from value bounds and k: buckets can be linear with bounded frequencies, while a heap gives O(u log k) for u unique values. |
Reject the Tempting Decoy
Consider: “Given an integer array that may contain negative values, find the longest contiguous subarray whose sum is at most k.” The words longest, contiguous, and at most make a dynamic sliding window tempting. That choice is wrong because negative values destroy the monotonic rule required to move the left boundary.
For a positive-only array, once a window sum exceeds k, extending the right side cannot repair it; shrinking from the left is safe. With negatives, an invalid window may become valid after adding a negative value. Removing a negative value from the left can even increase the sum. The usual window invariant no longer proves that a discarded left endpoint can never participate in the optimum.
| Candidate | Why it is tempting | Acceptance test | Verdict |
|---|---|---|---|
| Dynamic sliding window | The answer is a longest contiguous range | Window validity must change monotonically as either boundary moves | Reject when arbitrary negatives are allowed |
| Prefix sums plus an ordered structure | Every subarray sum is a difference of two prefixes | Need to query an earlier prefix satisfying an inequality while preserving the best index | Valid direction; exact structure depends on the inequality and required bound |
| O(n²) enumeration | Easy to prove and implement | Compare n² with the stated maximum n | Keep as the baseline; use only if constraints permit |
Contiguous does not automatically mean sliding window, “search” does not automatically mean binary search, and “locally best” does not automatically mean greedy. The required monotonicity or exchange argument must survive the actual constraints.
Classification Drill
Applied exercise
Produce a constraint-to-pattern brief
You receive three prompts: schedule the maximum number of non-overlapping meetings; find the shortest transformation between words; and report the largest value in every window of width k.
- For each prompt, write the target complexity implied by realistic input bounds.
- List two candidate families and the state each would maintain.
- Choose one family and write its invariant in one sentence.
- Reject the strongest alternative with a concrete counterexample or complexity argument.
- List one edge case that could invalidate an implementation even when the pattern choice is correct.
Deliverable
A one-page brief with three rows: evidence, shortlist, chosen invariant, rejection reason, target complexity, and edge test.
Completion checks
- Meeting scheduling names the ordering rule and explains why the earliest finishing compatible meeting is a safe greedy choice.
- Word transformation models words as nodes and one-letter changes as edges; unweighted shortest path leads to BFS.
- Window maximum explains expiry and dominance in a monotonic deque rather than rescanning every window.
- Every rejection cites a violated invariant or an unaffordable complexity—not preference.
Which fact is necessary before using the usual shrink-while-invalid sliding window for a sum bound?
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.