Lesson 8 of 8 · 52 min

DP, backtracking, and the capstone mock

Core DP and backtracking templates, then a full rubric mock on LRU cache, token-bucket rate limiter, and streaming median — production-flavored close to the track.

DP is caching with a story; backtracking is search with undo

Applied engineers already know memoization (“cache this function”) but freeze when asked to name state and transition on a whiteboard. DP = overlapping subproblems + optimal substructure + defined state. Backtracking = build a partial solution, abandon when invalid, undo. Capstone closes the track with production-flavored structures (LRU, token bucket, streaming median) run as a full live loop under the four-axis rubric.
DP recognition: can the answer for n be built from answers for smaller n? Can you name dp[i] or dp[i][j] in one sentence? 1D classics: climbing stairs, house robber, coin change. 2D: unique paths, LCS. LIS is O(n²) DP or O(n log n) patience. Grid DP: obstacles, path counts. Knapsack-ish: 0/1 with capacity loop backward. Always speak recurrence before code.
Backtracking: permutations, subsets, combination sum, word search. Template: path list, for each choice append → recurse → pop. Prune when remaining budget exceeded or cell visited. Complexity exponential; pruning is the interview content. Production: generating config permutations under constraints; not for hot paths without bounds.

DP core: robber and coin change

python
1HOUSE ROBBER — 1D DP state is max through i23def rob(nums: list[int]) -> int:4    prev2 = prev1 = 0  # dp[i-2], dp[i-1]5    for x in nums:6        prev2, prev1 = prev1, max(prev1, prev2 + x)7    return prev189# Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])10# Coin change (min coins): dp[0]=0; dp[a]=min over coin c of dp[a-c]+1; inf if impossible.
python
1COIN CHANGE — unbounded knapsack style23def coin_change(coins: list[int], amount: int) -> int:4    INF = amount + 15    dp = [INF] * (amount + 1)6    dp[0] = 07    for a in range(1, amount + 1):8        for c in coins:9            if c <= a:10                dp[a] = min(dp[a], dp[a - c] + 1)11    return dp[amount] if dp[amount] < INF else -11213# O(amount * |coins|). State sentence: min coins to make exact sum a.

Backtracking template

python
1SUBSETS — include/exclude backtracking23def subsets(nums: list[int]) -> list[list[int]]:4    ans: list[list[int]] = []5    path: list[int] = []67    def bt(i: int) -> None:8        if i == len(nums):9            ans.append(path.copy())10            return11        # exclude12        bt(i + 1)13        # include14        path.append(nums[i])15        bt(i + 1)16        path.pop()1718    bt(0)19    return ans2021# Word search: mark board[r][c] visited, recurse 4 dirs, unmark — same undo discipline.

LCS / LIS and state sentences

LCS: dp[i][j] = length of LCS of a[:i] and b[:j]; if equal chars diagonal+1 else max of skip either. O(n m) time and space (compressible to 1D). LIS: dp[i] = best ending at i (O(n²)) or patience sorting tails array O(n log n) — mention both, implement O(n²) under time pressure unless asked for optimal.
Grid unique paths / dungeon-style min path: fill first row/col base carefully (Verification), then recurrence inward. Obstacles: treat cell as 0 ways. The interview is usually base cases and obstacle handling, not the middle formula.
python
1LCS LENGTH — 2D DP with a one-sentence state23def lcs(a: str, b: str) -> int:4    n, m = len(a), len(b)5    dp = [[0] * (m + 1) for _ in range(n + 1)]6    for i in range(1, n + 1):7        for j in range(1, m + 1):8            if a[i - 1] == b[j - 1]:9                dp[i][j] = dp[i - 1][j - 1] + 110            else:11                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])12    return dp[n][m]1314# State: dp[i][j] = LCS length of a[:i], b[:j]. Say it before loops.

Capstone mock — production structures under the rubric

Run these as a timed mock (45–60 min total or one deep 45 on two of three). For each: clarify → approach → complexity → code → test → self-grade the four axes. Do not skip narration. These mirror AI-lab / strong-startup “build a small thing” rounds more than pure LeetCode, while still using structures you know.
1. LRU Cache. get/put O(1): hash map key→node + doubly linked list for recency. Clarify capacity, behavior when capacity 0, update moves to front. 2. Token-bucket rate limiter. Refill based on elapsed time; allow if tokens≥1; O(1) per request. Clarify rate, burst, clock source. 3. Streaming median. Two heaps from L5 — re-implement under time pressure with dry-runs.
python
1LRU CACHE — map + doubly linked list (interview skeleton)23class Node:4    def __init__(self, k=0, v=0):5        self.k, self.v = k, v6        self.prev = self.next = None78class LRUCache:9    def __init__(self, capacity: int):10        self.cap = capacity11        self.map: dict[int, Node] = {}12        self.head, self.tail = Node(), Node()  # sentinels13        self.head.next, self.tail.prev = self.tail, self.head1415    def _remove(self, n: Node) -> None:16        n.prev.next, n.next.prev = n.next, n.prev1718    def _add_front(self, n: Node) -> None:19        n.next, n.prev = self.head.next, self.head20        self.head.next.prev, self.head.next = n, n2122    def get(self, key: int) -> int:23        if key not in self.map:24            return -125        n = self.map[key]26        self._remove(n); self._add_front(n)27        return n.v2829    def put(self, key: int, value: int) -> None:30        if key in self.map:31            self._remove(self.map[key])32        n = Node(key, value)33        self.map[key] = n34        self._add_front(n)35        if len(self.map) > self.cap:36            lru = self.tail.prev37            self._remove(lru)38            del self.map[lru.k]
python
1TOKEN BUCKET — O(1) allow() with fractional refill23import time45class TokenBucket:6    def __init__(self, rate: float, burst: float):7        self.rate = rate          # tokens per second8        self.burst = burst        # max tokens9        self.tokens = burst10        self.updated = time.monotonic()1112    def allow(self) -> bool:13        now = time.monotonic()14        elapsed = now - self.updated15        self.updated = now16        self.tokens = min(self.burst, self.tokens + elapsed * self.rate)17        if self.tokens >= 1.0:18            self.tokens -= 1.019            return True20        return False2122# Clarify: multi-thread needs a lock; distributed needs Redis — say as follow-up.
Full mock protocol: 5 min clarify+approach for problem 1 (LRU), 20 min code+test, 5 min rubric self-grade; then 15 min token bucket or median. Speak complexity every time. If stuck, narrate options — do not go silent (L1). This is the track’s final exam.
Self-grade worksheet (write scores, not vibes): Communication 1–4 — did partner always know your plan? Problem Solving 1–4 — clarify + alternatives + hint recovery? Technical 1–4 — correct complexity and edge-safe code? Verification 1–4 — multi-case dry-run before “done”? Any axis ≤2 → re-mock that problem within 48 hours. Pattern-first prep without rubric feedback recreates silent coding.

What this track deliberately skipped

On-demand only (not core drills): tries/autocomplete, union-find, bit tricks, segment trees, heavy geometry. If a specific company asks them, learn that week — do not burn your 4–8 week runway on <5% frequency topics. Monotonic stack is adjacent (next greater element); if you have extra time after mocks, add it as a bonus pattern day.
Caching is DP in production clothing. Rate limits and LRUs are the “build from scratch” rounds AI labs actually run. Narrate them like incidents, not like trivia.

Interview prep

Close the track by scheduling real mocks. The answers below should be automatic; the capstone structures should be re-typed from memory at least twice.
  1. 01“How do you know it’s DP?” → overlapping subproblems + optimal substructure; name state.
  2. 02“Coin change recurrence?” → dp[a] = min(dp[a−c]+1); dp[0]=0.
  3. 03“Backtracking template?” → choose → recurse → undo; prune early.
  4. 04“LRU O(1)?” → hashmap + doubly linked list (or OrderedDict with move_to_end).
  5. 05“Token bucket vs fixed window?” → burst-friendly continuous refill vs rigid window counters.
  6. 06“Streaming median?” → two heaps; rebalance; O(log n) add.
  7. 07“DP vs backtracking for word break?” → DP boolean reachability vs listing all segmentations.
  8. 08“Self-grade?” → four axes 1–4; any 1 is fail; redo within 48h.
  9. 09"LRU two structures?" -> hashmap + doubly linked list for O(1) reorder/evict.
  10. 10"Token vs leaky?" -> token allows bursts to C; leaky smooths at constant drain.
  11. 11"Median heaps invariant?" -> lo max-heap, hi min-heap; sizes balanced; all lo <= all hi.
  12. 12"Distributed rate limit?" -> Redis Lua atomic refill+consume across instances.
  13. 13"DP vs backtracking word break?" -> boolean/count = DP; list segmentations = backtracking.
  14. 14"Self-grade capstone?" -> four axes 1-4 after timed mock; redo any <=2 within 48h.
docsNeetCode — LRU CacheNeetCodearticleTIH — Dynamic programmingTech Interview HandbookarticleToken bucket — WikipediaWikipediaarticleAlgoMaster — DP / Backtracking patternsAlgoMasterLRU Cache — NeetCodeNeetCode

Capstone full teach: LRU + token bucket + streaming median

These three are the AI-lab / strong-startup "build a small thing" set. Run them under the four-axis rubric from L1. LRU: hashmap key->node + doubly linked list (head=MRU, tail=LRU); get moves to front; put inserts front and evicts tail.prev when over capacity; capacity 0 => always miss; DLL not SLL because O(1) remove needs predecessor; lock or shard for threads; Redis for multi-node. Token bucket: state (tokens, last_ts); refill min(C, tokens+(now-last)*r); allow if tokens>=cost; bursts up to C vs leaky smooth drain vs fixed-window boundary burst; Redis Lua for distributed atomicity. Streaming median: max-heap lo + min-heap hi; all lo <= all hi; sizes |lo|==|hi| or |lo|==|hi|+1; O(log n) add, O(1) median; empty-stream contract first; sliding-window p50 may need approx (t-digest/KLL) at scale. Re-type LRU from memory twice this week — pointer bugs only show under time pressure.
python
1STREAMING MEDIAN — two heaps full (LC 295)23import heapq45class MedianFinder:6    def __init__(self):7        self.lo: list[int] = []  # max-heap via negation8        self.hi: list[int] = []  # min-heap910    def add_num(self, num: int) -> None:11        if not self.lo or num <= -self.lo[0]:12            heapq.heappush(self.lo, -num)13        else:14            heapq.heappush(self.hi, num)15        if len(self.lo) < len(self.hi):16            heapq.heappush(self.lo, -heapq.heappop(self.hi))17        elif len(self.lo) - len(self.hi) > 1:18            heapq.heappush(self.hi, -heapq.heappop(self.lo))1920    def find_median(self) -> float:21        if len(self.lo) > len(self.hi):22            return float(-self.lo[0])23        return (-self.lo[0] + self.hi[0]) / 2.02425# Dry-run 1,2,3 -> 2; +4 -> 2.5. Rebalance after every insert.
python
1TOKEN BUCKET — lock + fractional refill (distributed note)23import time, threading45class TokenBucket:6    def __init__(self, rate: float, burst: float):7        self.rate, self.burst = rate, burst8        self.tokens = burst9        self.updated = time.monotonic()10        self._lock = threading.Lock()1112    def allow(self, cost: float = 1.0) -> bool:13        with self._lock:14            now = time.monotonic()15            elapsed = now - self.updated16            self.updated = now17            self.tokens = min(self.burst, self.tokens + elapsed * self.rate)18            if self.tokens >= cost:19                self.tokens -= cost20                return True21            return False2223# Multi-instance: Redis Lua EVAL atomic refill+consume. Metrics: reject rate, burst usage.
Mock rubric protocol (45 min). 0-5 clarify LRU (capacity, -1 miss, threads). 5-25 code + dry-run put/get/evict. 25-30 self-score C/PS/T/V 1-4. 30-45 token bucket or median: approach first, code, edges (burst of C+1 at t=0 should reject last; wait 1/r and show refill; median after 1/2/3 inserts). Any axis <=2 => re-mock that structure in 48h. Spoken checklist: map+DLL O(1); refill by elapsed time, burst C, rate r, lock/Redis; two heaps rebalance O(log n). Then dry-run. Then complexity. Then unprompted production follow-up. That sequence is Strong Hire on build-from-scratch rounds. DP/backtracking still matter for classic FAANG: state sentence before table; backtracking is choose/recurse/undo. Schedule Pramp/interviewing.io mocks and grade them with the same worksheet — the track is not complete until two timed mocks clear all axes at >=3. Silence >90s scores Communication 1 even if code is perfect.
Find Median from Data Stream — NeetCodeNeetCodearticleRate limiting algorithms — AlgoMasterAlgoMaster

Checkpoint

You need min number of coins to make amount (unlimited coins). Approach?

ABacktracking all combinations without memo onlyBDP: dp[a] min coins for sum a; try each coin; O(amount * |coins|)CGreedy always take largest coin
Sign up free to answer and see why

Checkpoint

Implement LRU: you use a list and .remove(key) each access. Interviewer asks complexity?

AStill O(1) because Python is fastBget/put degrade to O(n); need hash + doubly linked list (or OrderedDict) for O(1)CO(log n) with binary search on the list
Sign up free to answer and see why

Checkpoint

Token bucket allow() under multi-threaded web server. What do you mention unprompted?

ANothing — single-thread code is enough alwaysBNeed synchronization around tokens/updated; for multi-node, centralize store (Redis) — single-process lock is only one machineCUse sleep() to refill tokens
Sign up free to answer and see why

Checkpoint

Capstone self-grade: perfect code, zero narration, no tests. Axes?

AStrong Hire overall because code is perfectBTechnical may be 3–4 but Communication and Verification likely No-Hire — not a hire packetCOnly Problem Solving suffers
Sign up free to answer and see why

Checkpoint

Word search on board: after exploring one path that failed, what must you do?

ALeave the cell marked visited permanentlyBUnmark / pop the cell (undo) before trying the next direction — backtracking disciplineCRestart BFS from the beginning of the board
Sign up free to answer and see why

Could you run a 45-minute mock on LRU + one of (token bucket, streaming median), narrate the four axes, and honestly self-score?

New to itGetting thereConfident

Takeaways

  • DP: name state + recurrence + base; memo or bottom-up.
  • Backtracking: choose → recurse → undo; prune.
  • Capstone: LRU (map+DLL), token bucket O(1) refill, two-heap median.
  • Self-grade all four axes; silence fails even with correct code.
  • Pattern-first track complete — keep a failure log of dry-run bugs.

Track complete. Schedule 2–3 timed mocks/week; review failures by pattern, not by random problem count.

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with EnzoSign up free