01 · DSA — File 10
Patterns Cheatsheet
In the interview you have ~90 seconds to map a novel-sounding problem onto a pattern you already know. This page is that mapping table — plus the triage script, the triaged 2-day problem list, and a self-test. Skim it first each study session and last before the interview.
01The master table: “if you see X → think Y”
Signal phrase on the left, pattern in the chip, one-line justification. Read a random row and cover the middle column — that is the drill.
Arrays, strings, windows file 02
| If you see… | Think… | Why |
|---|---|---|
| pair/complement summing to target, unsorted | Hashmap of seen values | Lookup replaces inner loop: O(n²)→O(n) |
| same, but array sorted (or sorting is free) | Two pointers from both ends | Monotonic sum ⇒ safely discard an end |
| longest/shortest substring/subarray with condition | Sliding window | Incremental state; each element in/out once |
| contiguous subarray sum = k (negatives possible!) | Prefix sums + hashmap | Window breaks on negatives; prefix diff doesn’t |
| many range-sum queries | Prefix sums | O(1) per query after O(n) prep |
| “have I seen this before?” / dedupe | Set | O(1) membership |
| group equivalent items (anagrams…) | Hashmap keyed on canonical form | Sorted-tuple / count-tuple as key |
| in-place remove / compact / partition | Reader–writer pointers | Slow marks the write slot |
| next greater/smaller, stock span, temperatures | Monotonic stack | Stack holds the unresolved; pop = resolved |
| sliding window max/min | Monotonic deque | Front is always the extreme |
Linked lists, stacks, queues file 03
| If you see… | Think… | Why |
|---|---|---|
| middle / cycle / “k-th from end” of a list | Fast & slow pointers | Speed differential encodes position |
| reverse (all or part of) a list | prev/cur/nxt three-pointer flip | Memorized cold |
| head might change (delete, merge) | Dummy node | Kills the special case |
| nested structure, matching, undo, “most recent” | Stack | LIFO = nesting |
| process in arrival order / by level | Queue (deque) | FIFO = fairness |
| O(1) get + O(1) recency update (LRU) | Hashmap + doubly linked list | Each covers the other’s weakness |
Trees & graphs files 04–05
| If you see… | Think… | Why |
|---|---|---|
| any tree question | Recursion: base + combine(left, right, node) | Trees ARE recursion |
| “by level”, zigzag, right-side view, min depth | BFS with level-size snapshot | Layers = levels |
| BST + “sorted”, “k-th smallest”, “validate” | Inorder traversal / bounds-passing | The BST invariant: inorder is sorted |
| subtree answers feed parent (height, diameter…) | Postorder | Children before parent |
| shortest path / “minimum steps”, unweighted | BFS | First visit = shortest |
| shortest path, weighted, non-negative | Dijkstra (heap-BFS) | Greedy by total distance |
| ordering with dependencies / “can finish?” / prereqs | Topological sort (Kahn’s) | Leftover nodes ⇒ cycle |
| count blobs / regions / islands / provinces | DFS/BFS flood per unvisited node | Component counting |
| dynamic “same group?” as merges stream in | Union-Find | α(n) merges/queries, no re-traversal |
| spread / infection “how many minutes” | Multi-source BFS | Seed all sources at t=0 |
| states + legal moves (word ladder, locks, knights) | Implicit graph → BFS | If you can write neighbors(), it’s a graph |
Heaps, tries, intervals, binary search files 06, 08
| If you see… | Think… | Why |
|---|---|---|
| “k largest/smallest/closest/most frequent” | Heap of size k (opposite polarity) | O(n log k); root = weakest member |
| “median / percentile of a stream” | Two heaps straddling the middle | Roots bracket the boundary |
| “merge k sorted …” | Heap of k heads | O(N log k) |
| repeatedly take “most urgent next” | Priority queue | Scheduling shape |
| “prefix”, “starts with”, autocomplete, dictionary | Trie | O(L) independent of corpus size |
| overlapping meetings / ranges / bookings | Sort by start, sweep (± heap of ends) | Only adjacent relations matter after sorting |
| “min rooms / max concurrent” | Heap of ends or +1/−1 sweep | Peak concurrency |
| sorted anything + “find/first/last/count” | Binary search / bisect | O(log n) boundary finding |
| “minimize the maximum / maximize the minimum” | Binary search on the answer | Monotone feasibility check |
| rotated sorted array | Modified binary search | One half is always sorted |
Recursion, backtracking, DP file 07
| If you see… | Think… | Why |
|---|---|---|
| “generate ALL subsets/permutations/combos/paths” | Backtracking (choose–explore–unchoose) | Output is exponential; enumerate with undo |
| n ≤ 20 in constraints | Backtracking / bitmask intended | 2ⁿ is affordable |
| “count the ways”, min/max cost over compounding choices | DP | Overlapping subproblems |
| greedy feels right but a counterexample exists | DP | Coins [1,3,4] energy |
| take/skip items under a budget | Knapsack DP | dp[i][w] = max(skip, take) |
| two strings compared/aligned/edited | 2-D grid DP (LCS / edit distance) | State = (prefix of A, prefix of B) |
| “longest … subsequence ending here” | dp[i] = best ending at i | Composability trick |
| best path/sum in grid moving right/down | Grid DP | dp[r][c] from top/left |
Meta-signals from constraints file 01
| Constraint | Expected complexity | Usually means |
|---|---|---|
| n ≤ 12 | O(n!) | permutations, brute force |
| n ≤ 20–25 | O(2ⁿ) | subsets / backtracking / bitmask |
| n ≤ 500 | O(n³) | interval DP, Floyd–Warshall |
| n ≤ 5,000 | O(n²) | 2-D DP, nested loops |
| n ≤ 10⁵–10⁶ | O(n log n) / O(n) | sort / heap / window / hashmap / one pass |
| n huge, or “answer in a range” | O(log n) | binary search (often on the answer) |
02The 90-second triage script
Run this on every problem, in order. It is the difference between flailing and a plan.
Step 1 — Restate + constraints. Read n. The constraints table above converts n → intended complexity → shortlist of patterns.
Step 2 — Name the brute force out loud and its cost. Never skip — it’s free signal and a safety net.
Step 3 — Interrogate the ask: shortest? (BFS / Dijkstra / BS-on-answer) · all of them? (backtracking) · count ways / optimize? (DP) · contiguous? (window / prefix) · k-something? (heap) · ordering with deps? (topo) · groups? (DSU / flood) · prefix-shaped? (trie).
Step 4 — Pick structure + pattern, state the plan in 2 sentences, get a nod, then code.
Step 5 — Trace a size-3 example + one edge case; state time/space unprompted.
03Pattern quiz — train the reflex
04The 2-day practice list (progress saved)
Rules of engagement: 25 minutes per problem max. Stuck at 25 → read the solution, understand it, then re-code it from scratch without looking. That loop (attempt → study → re-derive) is worth 3× grinding new problems. Say your reasoning out loud even alone — you’re training the narration, not just the solution.
Checkboxes persist in this browser (localStorage), so your progress survives reloads. must · day 1 must · day 2 bonus — 0/20 must-do done
Arrays, strings & hashing
Linked lists, stacks & queues
Trees & BSTs
Graphs
Heaps, intervals & binary search
DP & backtracking
Nice-to-do (only if ahead of schedule, priority order)
05Final 30 minutes before the interview
Re-skim this page’s table and the triage script.
Re-write from pure memory: linked-list reversal, BFS level-order, the backtracking template, first_true binary search. Four shapes ≈ 25 lines total — they anchor everything else.
Re-read the Python gotchas so [[0]*c]*r and pop(0) never happen to you.
The meta-rules: brute force first, narrate complexity unprompted, trace an example before saying “done,” and ask a clarifying question before coding (empty input? duplicates? value ranges? — always have one).
06Self-test: the whole folder in 12 questions
Close everything. If any answer takes more than 10 seconds, that file is your weak spot.
1. “Longest subarray with sum ≤ k, all positives” vs “…with negatives allowed” — pattern for each, and why they differ. 02
2. Amortized O(1): give the doubling argument in two sentences, and name three places it appeared. 01 · 02 · 03
list.append, hashmap resize, and the monotonic stack / two-stack queue (each element pushed and popped at most once).3. Why does BFS find shortest paths only in unweighted graphs, and what’s the minimal change for weighted non-negative? 05
4. Detect “this is topological sort” from problem wording — give three phrasings that mean it. 05
5. Top-K largest: which heap polarity, which size, what complexity, and what does the root represent? 06
6. The three-decision binary search template — write it and defend each decision. 08
while lo < hi; hi = mid when mid could be the answer (keep the candidate); lo = mid + 1 when mid is proven false (drop it). Mid rounds low so both branches strictly shrink the range — no infinite loop.7. “Minimize the maximum X” — pattern, and the two properties that must hold. 06 · 08
8. DP vs backtracking: the one-sentence discriminator. 07
9. Knapsack 1-D: which loop direction for 0/1 vs unbounded, and why? 07
10. Why do databases use B-trees over binary trees, in ≤ 2 sentences? 04
11. Name the Python trap in each: def f(x, m={}) · [[0]*3]*4 · list.pop(0) in BFS · results.append(path) in backtracking. 09 · 07
collections.deque); aliased result lists (append path[:], not path).12. Recite the 90-second triage script from memory. this page
Two days, ten files. Day 1: files 01–04 + the Day-1 problems above. Day 2: files 05–08 + the Day-2 problems, then 09–10 as the final skim. Go.