Advanced coding progression
These are constructed practice questions, with candidate briefs before hidden worked solutions. Attempt each independently and record your invariant, tests, complexity, and response to a changed requirement before viewing the reference. Passing reference tests is implementation evidence, not an assessment of you.
Start with the foundations progression. These exercises then combine graph state, explicit structures, search, and runtime contracts.
| Order | Problem | Property to explain independently |
|---|---|---|
| 21 | Dependency order | Readiness counts and cycle detection |
| 22 | Word ladder | Implicit graph and shortest discovery |
| 23 | Disjoint-set connectivity | Partition preservation under union/compression |
| 24 | Grid shortest path | Movement contract and path reconstruction |
| 25 | Weighted shortest path | Finality, relaxation, and stale heap entries |
| 26 | Top k stream | Exact retained multiset and lost history |
| 27 | Merge k streams | One frontier per source and lazy failure |
| 28 | Manual LRU cache | Map/list identity and pointer invariants |
| 29 | Expiring key-value store | Strict expiry boundary and cleanup authority |
| 30 | Trie autocomplete | Terminal markers, traversal order, and output cost |
| 31 | Combination search | Canonical choices, termination, and output-sensitive work |
| 32 | Word search | Path-local visited state and restoration |
| 33 | Coin change | Optimal substructure, witness, and pseudopolynomial cost |
| 34 | Longest increasing subsequence | Dominating tails and historical predecessors |
| 35 | Edit distance | Prefix states, recurrence, and rolling-row limits |
| 36 | Decode ways | Disjoint counting cases and exact-integer growth |
| 37 | Daily temperatures | Unresolved candidates and amortized nearestness |
| 38 | Largest histogram rectangle | First smaller boundary and inherited start |
| 39 | Policy expression evaluator | Lexer/parser separation, precedence, and missing fields |
| 40 | Event-time windows | Watermark authority, lateness, and finality |
| 41 | Streaming median | Ordered halves, balancing, and exact arithmetic |
| 42 | Bounded blocking queue | Predicate loops, admission, deadlines, and shutdown |
Run a single reference from the repository root, substituting the chosen directory:
python -m unittest discover -s curriculum/04-scale-and-evolution/01-data-at-scale/problems/28-manual-lru-cache -p 'test_*.py'
Every directory supplies solution.py and test_solution.py; tests require only
Python's standard library. Use separate processes for different directories because
each intentionally imports its local module as solution.
For backend or infrastructure practice, spend extra time on dependency readiness, stream consumption, manual LRU, and expiration. For product/search practice, emphasize grid/word graph modeling, autocomplete, and policy parsing. The bounded queue is an explicit backend/infrastructure extension. For DP transfer, solve 33–36 together and explain why one minimizes, one uses dominance, one aligns prefixes, and one counts disjoint cases. Senior practice still requires defending the underlying invariants; lead extensions change ownership, resource budgets, and evolving contracts rather than replacing the coding floor.