latency.lab
Algorithms · Topic 19

Design

Level: foundationTool: Combining data structures to hit per-operation time boundsTime: ~90 min

By the end you can

Every earlier topic in this track hands you a single function and asks for one answer. Design problems hand you a class — a handful of operations that all have to stay correct and fast together, across however many calls come in, in whatever order. The skill this topic teaches isn't a new algorithm so much as a new question: which data structure(s), combined, give every required operation the time bound it needs — and what do you do when no single built-in container can do that alone?

One structure isn't enough: combine two for a reason

This is the throughline of the topic. LRU Cache needs O(1) lookup by key (a hash map's specialty) and O(1) "move this to the front, evict the back" (a doubly linked list's specialty) — neither alone gives you both, so the hash map stores an iterator directly into the list, letting one operation use both structures' strengths at once. Insert Delete GetRandom O(1) needs O(1) lookup (hash map) and O(1) uniform-random access by position (a plain array) — same idea, different pairing. Design Underground System just uses two hash maps side by side, each answering a different question (who's mid-trip; what's the running average for this station pair), because forcing one structure to answer both would be more awkward than just using two.

The habit to build

When a problem's requirements don't fit any single container's strengths, ask what a second structure could hold that makes the missing operation O(1) too — and what has to stay in sync between them (LRU Cache's map-of-iterators; Insert Delete GetRandom's map-of-indices) every time either one changes.

k1 k2 k3 k4 MRU LRU (evict me)
hash map (key → node)
k1 → node 1 (O(1) jump, no scan)
k4 → node 4
LRU Cache: the linked list orders entries by recency (most-recently-used on the left); the hash map jumps straight to any key's node in O(1), so accessing k1 doesn't require scanning the list to find it — splicing it to the front is then O(1) too.

Amortized cost, and where it does (and doesn't) even out

Implement Queue using Stacks achieves amortized O(1) per operation: every element moves from the "in" stack to the "out" stack at most once in its whole lifetime, no matter how many pushes and pops happen around it. Implement Stack using Queues looks like the mirror image, but it genuinely isn't: with only queue operations available, there's no way to avoid an O(n) rotation on every single push — some operation has to pay to reverse FIFO order into LIFO order, and with a queue's limited interface, that cost never amortizes away. Knowing which direction of a problem *can* amortize and which fundamentally can't is as important as knowing the trick itself.

Building the primitive yourself

Design HashMap and Design Circular Queue both ask you to build, from raw arrays, something you've been calling as a black box in every earlier topic. Design HashMap's separate-chaining bucket array is exactly what's underneath std::unordered_map; Design Circular Queue's modulo-indexed ring buffer is the same trick behind any fixed-size FIFO buffer used in latency-sensitive code, where resizing (and its unpredictable pause) isn't acceptable.

Generalizing a technique on top of a technique

LFU Cache is LRU Cache with a second dimension bolted on: instead of one recency-ordered list, it needs a *list of lists* — one doubly linked list per frequency, so ties at the same frequency still break by recency, exactly like plain LRU. Time Based Key-Value Store leans on a different earlier idea instead: since each key's timestamped history is appended in increasing order by construction, it's already sorted — turning what looks like a new problem into "binary search over data you get to assume is pre-sorted." Design Twitter's news feed reuses the k-way-merge idea from merging sorted lists, just applied across each followed user's already-chronological tweet history instead of literal linked lists.

Common mistakes

  • Assuming a "mirror image" problem shares the same amortized guarantee — Implement Stack using Queues cannot achieve the same amortized O(1) that Implement Queue using Stacks does; some direction of the reversal is fundamentally O(n) every time.
  • Forgetting to keep two combined structures in sync — LRU Cache's hash map and linked list, or Insert Delete GetRandom's hash map and array, both need every mutation applied to *both* structures, or the two fall out of sync silently.
  • Missing the swap-with-last-element edge case — when the element being removed happens to already be at the last array position, Insert Delete GetRandom's swap becomes a harmless self-assignment, but it's worth explicitly reasoning through rather than assuming it "just works."
  • Not updating the tracked minimum when a bucket empties — LFU Cache's min_freq only needs incrementing when the bucket that just lost its last member was itself the current minimum; skipping this check is the single most common LFU bug.
  • Re-sorting data that's already sorted by construction — Time Based Key-Value Store's per-key timestamp history never needs re-sorting; it's appended in increasing order already, which is exactly what makes binary search applicable.

Takeaways

  • When no single container satisfies every required operation's time bound, combine two — and identify exactly what has to stay synchronized between them.
  • "Amortized O(1)" isn't automatic just because a similar-looking problem elsewhere achieved it — check whether the direction of the reversal or cost-shifting genuinely evens out.
  • Building a hash map or a circular buffer from raw arrays is the same mechanism you've been trusting as a black box all along.
  • A new-looking design problem is often an earlier technique (LRU, binary search, k-way merge) with one more dimension or one more assumption (data already sorted by construction) layered on top.

Try it: combining two structures for two guarantees

LRU Cache — a hash map and a doubly linked list, each covering what the other can't do alone.

Live

Loading starter code…

Try it: an asymmetry that isn't obvious at first

Implement Stack using Queues — work out why this direction can't match Queue-from-Stacks' amortized bound before checking the hint.

Live

Loading starter code…

Try it: generalizing LRU with a second dimension

LFU Cache — the hardest problem in this topic, and the clearest test of whether the LRU mental model really landed.

Live

Loading starter code…

Keep going

That's 3 of the 12 problems in this topic. Insert Delete GetRandom O(1) is worth doing next — it's the clearest single example of the "combine two structures" idea in its simplest form. See the full Design set →

Checkpoint · Design

5 questions · pass at 70%

Q01
Implement Queue using Stacks achieves amortized O(1) per operation using two stacks, but Implement Stack using Queues cannot achieve the same amortized bound for push using only queue operations. Why not?
WhyQueue-from-stacks achieves amortized O(1) because each element crosses from the 'in' stack to the 'out' stack at most once ever, no matter how many operations happen -- that one-time cost per element spreads thin over many calls. Stack-from-queues has no equivalent: with only enqueue/dequeue/front available, producing LIFO order requires rotating the queue on every push, and that rotation cost recurs every time, so it never amortizes down to O(1). The two directions are NOT symmetric.
Q02
LRU Cache stores, in its hash map, an ITERATOR directly into the doubly linked list (not just the key's position or index). Why does this matter for keeping get() and put() at O(1)?
WhyA std::vector's indices would shift whenever an earlier element moved, forcing every affected entry's stored position to be updated -- expensive. std::list::splice relocates a node by adjusting a few pointers, and critically, does not invalidate iterators or references to any node (not even the one being moved) -- so an iterator stored for a completely different key remains valid and correct even after some other key's node gets spliced to the front. That's exactly what keeps every operation O(1): only the touched key's bookkeeping needs any update at all.
Q03
LFU Cache's touch(key) function increments min_freq only when the bucket that just lost its last member WAS the current minimum frequency. Why is that specific condition the correct one to check?
Whymin_freq tracks 'the smallest frequency that currently has at least one key in it.' If some other bucket (not the minimum) empties out, the minimum-frequency bucket is untouched and still valid -- no update needed. Only when the bucket AT min_freq itself loses its last remaining key does the old minimum stop being valid, which is exactly when it needs to advance (and since frequencies only ever increase by exactly 1 per touch, incrementing by 1 is always correct in that specific case).
Q04
Design Underground System keeps two separate hash maps (checkins by passenger id; running stats by station pair) rather than trying to fold both into one structure. What's the reasoning behind that choice?
WhycheckIn/checkOut needs a lookup keyed by passenger id (to find where and when THIS passenger started); getAverageTime needs a lookup keyed by (station, station) pair (to find the running total for THAT route). These are different keys answering different questions -- there's no natural single structure that indexes efficiently by both a passenger id AND a station pair at once, so using two purpose-built maps, each doing the one job it's suited for, is simpler and just as fast as trying to unify them would be complicated.
Q05
Time Based Key-Value Store answers get(key, timestamp) using binary search (upper_bound) over each key's timestamp history, without ever sorting that history first. Why is no sorting step needed?
WhyThe problem guarantees timestamps arrive in strictly increasing order for any given key. Since each set() call simply appends to that key's history, and appending a larger value to an already-sorted-ascending sequence keeps it sorted, the history is sorted by construction -- with no separate sorting step ever required. That's precisely what makes binary search (rather than a linear scan) valid and correct for every get() call.

Finished Design?

Pass the quiz to complete it automatically.