Data Structure Design
What is this?
Here someone hands you a wish list of operations — "add a number, remove a number, and give me a random one, all instantly" — and your job is to build a container that grants every wish at full speed. It is like designing a backpack with the perfect set of pockets so that whatever you reach for comes out immediately. The catch: one kind of pocket can't do it all, so you stitch two simple structures together and let each cover the other's weak spot.
💡 Fun fact: The LRU cache built in this chapter — a hash map glued to a doubly linked list — is exactly how real systems decide what to keep in fast memory. It powers browser caches, CPU caches, and databases like Redis, all to hit that magic O(1) lookup and eviction.
🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: You're handed an API with required complexities and must build a structure that honors all of them at once. Since operations pull in different directions, the winning move is almost always to combine two simple structures so each does what it's best at — turning every operation into O(1) or O(log n).
The method
- List the operations and their target complexities. That's the spec.
- For each op, name the structure that makes it cheap (lookup → hash map; random index → array; ordering/recency → linked list/heap; windowed/versioned → ring buffer / history + bisect).
- If no single structure covers all ops, pair two and keep them in sync.
- State the invariant — what's always true between calls (e.g. "the map and the list reference the same nodes"). Bugs live where the invariant slips.
The five problems
| Problem | Structures combined | Key op made cheap |
|---|---|---|
| Design Circular Queue | array + head + count, % k |
O(1) bounded FIFO |
| Insert Delete GetRandom O(1) | dynamic array + value→index map | O(1) remove via swap-to-end |
| Design Hit Counter | 300 fixed buckets keyed by t % 300 |
O(1) windowed count, bounded memory |
| LRU Cache | hash map + doubly linked list | O(1) get/put + recency eviction |
| Snapshot Array | per-index (snap_id, val) log + binary search |
versioned read ∝ writes, not snaps×length |
The progression builds the core trick: Circular Queue introduces the ring; RandomizedSet the array+map pairing; LRU the canonical map+DLL combo; Hit Counter and Snapshot Array show the same "don't store more than you need" instinct for time windows and versions.
The recurring trade
No single structure is great at everything. A hash map finds fast but has no order; an array indexes fast but deletes slowly; a linked list reorders fast but can't random-access. Pair them — map+DLL, array+map — and each covers the other's weakness. That pairing is data-structure design.
📓 Draw it yourself
- LRU map+DLL. Draw the hash map pointing into a doubly linked list; promote on
get, evict the tail on overflow. - Swap-to-end. For RandomizedSet, delete a middle element by swapping with the last and popping — update the moved element's index.
Snap photos and embed them with the /host-diagrams skill.
Key takeaways
- Start from the API + complexities; pick structures that make each op cheap.
- Combine two structures when one can't do it all (map+DLL, array+map) — the defining pattern.
- Bound your memory: ring buffers for windows (Hit Counter), change-logs for versions (Snapshot Array).
- State and preserve the invariant linking the two structures — that's where bugs hide.
- Why interviewers love it: it's how real caches, queues, and indexes are actually built.
Order: Design Circular Queue → Insert Delete GetRandom O(1) → Design Hit Counter → LRU Cache → Snapshot Array.
Snapshot Array
Core idea: Don't photograph the whole array on every snapshot — instead let each cell keep a tiny diary of
(snap_id, value)entries written only when it changes, and answer "what were you at snapshot S?" with a binary search.
This problem looks innocent — set values, take a snapshot, read old values back — but it quietly punishes the obvious solution. Copy the entire array on every snap() and you'll burn O(length) time and memory per snapshot, which detonates the moment someone snaps a million-element array a thousand times. The elegant answer flips the whole frame: instead of versioning the array, we version each cell, and the cost collapses to "memory proportional to the number of writes." Let's build up to it.
Problem, rephrased
Imagine you run the settings panel for a collaborative document editor. Every paragraph has a numbered slot, and a slot holds the latest formatting code an editor typed. Periodically the system takes a named version of the whole document so users can later say "show me the formatting as it was at version 3" — like Google Docs version history, or a "restore to this point" button.
You're asked to build the engine behind that:
SnapshotArray(length)— createlengthslots, every one starting at0(unstyled).set(index, val)— the editor atindextypes a new formatting codeval. This affects only the current (not-yet-named) version.snap()— freeze the current state as a new named version. Returns that version's id: the first snap returns0, the next1, then2, … and the internal counter advances.get(index, snap_id)— what was slotindexshowing at the moment versionsnap_idwas frozen?
Many slots, many edits, many versions. The engine must answer historical reads fast without storing a full copy of the document for every single version.
| Operation | Effect | Returns |
|---|---|---|
SnapshotArray(3) |
three slots, all 0 |
— |
set(0, 5) |
slot 0 → 5 in the live version | — |
snap() |
freeze live state as version 0 | 0 |
set(0, 6) |
slot 0 → 6 in the new live version | — |
get(0, 0) |
slot 0 as of version 0 | 5 |
get(0, 1) |
(after another snap()) slot 0 as of version 1 |
6 |
That get(0, 0) == 5 even after set(0, 6) is the entire problem: a write to the live version must not disturb already-frozen history.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson