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.

flowchart TD A["List the operations and their target speeds"] --> B["Pick the structure that makes each op cheap"] B --> C["No single one fits, so pair two structures"] C --> D["Keep them in sync via one invariant"]

💡 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

Data structure design branching to its five problems: Circular Queue (ring buffer), Insert/Delete/GetRandom O(1) (array + index map), Hit Counter (fixed-bucket ring), LRU Cache (map + doubly linked list), Snapshot Array (per-cell history + bisect)

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.

Design Circular Queue

Core idea: A circular queue is just a fixed-size array that "wraps around" — keep a head index and a count, and compute every position with % capacity so you never shift elements.

When people first hear "queue" they imagine an infinitely growing line. But a circular queue is the opposite: a small, fixed slab of memory you reuse forever. That constraint is exactly what makes it fast and predictable, and it's why this pattern lives inside network cards and audio drivers. Let's build it from the ground up.

Problem, rephrased

You're writing the firmware for a parking garage with exactly k reserved spots numbered in a loop. Cars arrive and leave in FIFO order (the car that's been waiting longest is the next to be released). You need four instant answers and two actions:

park a car (enQueue) — succeeds only if there's a free spot
release the oldest car (deQueue) — succeeds only if a car is parked
who's at the front? (Front) — the oldest car, or -1 if none
who's at the back? (Rear) — the newest car, or -1 if none
is it empty? / is it full?

Every one of these must be O(1) — no scanning the lot. You also must never allocate more than k slots; the memory budget is fixed.

Here's a trace with capacity k = 3:

Operation	Returns	Queue (front → rear)	Note
`enQueue(1)`	`True`	`[1]`	parked
`enQueue(2)`	`True`	`[1, 2]`	parked
`enQueue(3)`	`True`	`[1, 2, 3]`	lot now full
`enQueue(4)`	`False`	`[1, 2, 3]`	rejected — full
`Rear()`	`3`	`[1, 2, 3]`	newest car
`isFull()`	`True`	`[1, 2, 3]`
`deQueue()`	`True`	`[2, 3]`	released oldest (1)
`enQueue(4)`	`True`	`[2, 3, 4]`	reused the freed slot (wrap!)
`Front()`	`2`	`[2, 3, 4]`	new oldest

That last enQueue(4) is the whole point: slot 0 (which used to hold 1) gets reused. The array doesn't grow — the indices wrap.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Foundations