Week 20 — Cache & High-Throughput Design

Month 05 · Week 20 · Theme: O(1) data structures behind every production system

This week is the design round that’s really an algorithms round. Every problem here is “build a textbook DS from scratch with O(1) guarantees” — exactly the trap question that separates a Mid-level fumble from a Staff-level reflex.

Why This Week Matters

LRU was Week 4 (p16). Every other cache, rate limiter, ranker, and suggestion engine you’ll ever build derives from the same three primitives this week drills:

1. Doubly-linked list + hashmap → eviction in O(1).
2. Sorted-by-frequency bucket of nodes → LFU in O(1) (not O(log n)).
3. Heap-merge of k sorted streams → personalized timelines in O(k log k).
4. Trie + per-node top-k heap → autocomplete in O(prefix + suggestions).
5. Pre-bucketed time windows → rate limiting in O(1) amortized.

You will fail the design round if you reach for dict + sorted() on the eviction path. These five problems show you what a real production cache, feed, suggester, or rate limiter looks like — and what the interviewer wants to hear when they ask “now scale it 1000×”.

Daily Schedule

Readiness Gate

By Friday you should be able to:

• Implement LFU in 25 min with both get and put strictly O(1) — and explain why the min_freq pointer never needs to scan.
• Implement a hit counter with both naive deque and bucketed circular array variants and explain when each wins (single-thread vs. wide-time-range queries).
• Implement Twitter’s getNewsFeed as a k-way heap merge in O(k log n) and articulate the alternative fan-out-on-write tradeoff.
• Implement Autocomplete with trie + top-k heap maintained per node, including the input-stream state machine ('#' resets) — most candidates forget the state.
• Implement All O(1) inc/dec/getMax/getMin without a SortedDict, using bucket DLLs — the canonical “I’ve actually built one of these” signal.

Connection to Interview Loop

These are the system-design-but-really-coding problems at Meta (LFU, Twitter), Google (Autocomplete), Microsoft (Hit Counter), and Bloomberg (All O(1)). Failure mode at Senior+ is always the same: candidate reaches for sorted() or heapify() in the hot path. The interviewer says nothing, marks the candidate down one level, and the loop is over.

The transferable lesson: every O(log n) call on a per-request path is a downlevel signal. If you internalize that this week, you’re playing at Staff caliber.