Data Structure Design

Build a class whose every operation meets a required cost by combining a hash map, an array, a linked list, a stack or a sorted list, each covering what the others cannot do.

Overview

The method: one structure per weakness

A design problem gives you a list of operations and a target cost for each one. No single built-in structure meets all of them, so you combine two or three. The method is always the same: write down the operations, find the one that is hardest to make fast, pick the structure that makes it fast, then add a second structure to cover what the first one cannot do.

Each building block is good at one or two things and bad at others. Knowing this table is most of the skill.

Hash map — lookup, insert, delete by key in O(1) average — anything about order; random pick
Array (dynamic) — index, append, pick a random slot in O(1) — delete from the middle, O(n)
Doubly linked list — remove or move a node you already hold in O(1) — find a node by value, O(n)
Stack — push, pop, top in O(1) — anything but the top
Sorted array — search in O(log n) — insert in the middle, O(n)
Min or max heap — smallest or largest in O(1), push and pop in O(log n) — find or remove an arbitrary item

Every combination below is two rows of this table glued together, plus a rule that keeps them consistent.

LRU cache: hash map plus doubly linked list

An LRU cache holds at most capacity items. get(key) returns the value and marks the key as most recently used. put(key, value) inserts or updates, and evicts the least recently used key when the cache is full. Both must be O(1).

The hash map gives O(1) lookup by key. It cannot say which key was used least recently. A doubly linked list ordered by recency can: the most recent node sits at one end, the least recent at the other, and any node can be unlinked and moved to the front in O(1) once you hold it. The map stores the node itself, not just the value, so a get can jump straight to the node.

The trace below uses capacity 2, and the order column lists keys from least recent to most recent.

put(1, 1) — 1 — insert
put(2, 2) — 1, 2 — insert
get(1) — 1 — 2, 1 — hit: move 1 to the front
put(3, 3) — 1, 3 — full: evict 2, the least recent
get(2) — -1 — 1, 3 — miss
put(4, 4) — 3, 4 — full: evict 1
get(1) — -1 — 3, 4 — miss
get(3) — 3 — 4, 3 — hit
get(4) — 4 — 3, 4 — hit

Two sentinel nodes, a fixed head and a fixed tail, remove every null check: the real nodes always sit between them. Write the list by hand at least once; after that, say that the standard libraries ship the same idea. Python's OrderedDict has move_to_end(key) and popitem(last=False), and Java's LinkedHashMap built with accessOrder = true reorders on get and calls removeEldestEntry after each insert.

Insert, delete and random pick in O(1)

A set that supports insert(x), remove(x) and getRandom(), all in O(1), where getRandom returns each stored value with equal probability.

A hash set gives O(1) insert and remove but cannot pick a random member in O(1). An array gives O(1) random pick by index but O(n) removal from the middle. Combine them: an array of values and a map from value to its index. To remove a value, overwrite its slot with the last value, update that value's index in the map, then pop the last slot. Removal is then O(1) and the array never has holes. Insert is an append, so it is O(1) amortized: the array grows by copying now and then, but the cost per insert averages out to constant.

insert(10) — [10] — 10 to 0
insert(20) — [10, 20] — 10 to 0, 20 to 1
insert(30) — [10, 20, 30] — 10 to 0, 20 to 1, 30 to 2
remove(10) — [30, 20] — 20 to 1, 30 to 0
insert(40) — [30, 20, 40] — 20 to 1, 30 to 0, 40 to 2
remove(30) — [40, 20] — 20 to 1, 40 to 0

getRandom is a random index into the array. Picking from the map's keys instead is the classic mistake: iterating to a random position is O(n).

Time-based key-value store: hash map plus binary search

set(key, value, timestamp) stores a value at a time, and get(key, timestamp) returns the value with the largest stored time that is at most the query time, or an empty string. In the usual version of the problem, timestamps for one key arrive in increasing order.

A map from key to two parallel lists, timestamps and values, works. Because timestamps arrive in order, set is an append, O(1). Get is a binary search for the rightmost timestamp at most the query, O(log n) for that key. In Python that is bisect.bisect_right(times, t), which returns the count of timestamps at or below t, so the answer sits at index count - 1.

times [1, 4], values [bar, bar2] — t = 0 — 0 — empty string
same — t = 1 — 1 — bar
same — t = 3 — 1 — bar
same — t = 4 — 2 — bar2
same — t = 5 — 2 — bar2

If timestamps could arrive out of order, appending breaks the sort. Inserting in place with bisect.insort finds the position in O(log n) but shifts the list in O(n); say so, and mention a balanced tree map (Java TreeMap.floorEntry) as the O(log n) alternative.

Min stack: two stacks

A stack with push, pop, top and getMin, all O(1). Keep a second stack that holds the running minimum. On push, also push onto the min stack when the value is at most its top. On pop, also pop the min stack when the popped value equals its top. The top of the min stack is always the minimum of what remains.

push(-2) — [-2] — [-2] — -2
push(0) — [-2, 0] — [-2] — -2
push(-3) — [-2, 0, -3] — [-2, -3] — -3
pop() — [-2, 0] — [-2] — -2
top() returns 0 — [-2, 0] — [-2] — -2

Pushing equal values onto the min stack (at most, not strictly less) matters: with duplicates of the minimum, popping one copy must not lose the minimum.

Maximum frequency stack: buckets by count

push(x) adds a value and pop() removes the value that occurs most often, breaking ties by the most recently pushed. Keep a map from value to its count, a map from count to a stack of values that reached that count, and the current maximum count. Push increments the value's count and pushes it onto that count's stack. Pop takes from the stack at the maximum count, decrements the value's count, and lowers the maximum when that stack empties.

push(5) — 5:1 — 1: [5] — 1
push(7) — 5:1, 7:1 — 1: [5, 7] — 1
push(5) — 5:2, 7:1 — 1: [5, 7], 2: [5] — 2
push(7) — 5:2, 7:2 — 1: [5, 7], 2: [5, 7] — 2
pop() — 5:2, 7:1 — 1: [5, 7], 2: [5] — 2 — 7
pop() — 5:1, 7:1 — 1: [5, 7], 2: [] — 1 — 5
pop() — 5:1, 7:0 — 1: [5] — 1 — 7

A value appears once in each stack from 1 up to its count, which is what makes the tie-break by recency fall out for free.

Questions to ask before you code

What is the capacity, and what happens at the limit? — eviction rule and which end of the list is evicted
Can a key be updated, and does an update count as a use? — whether put moves a node to the front
Are duplicates allowed? — set versus multiset; a multiset needs a set of indexes per value
Do timestamps or ids arrive in order? — append versus insert, and whether binary search is enough
Which operation is called most? — which side to make cheapest when both cannot be O(1)
Will several threads use it? — one lock around the whole structure is the honest first answer

What you will be able to do

Turn a list of operations and target costs into a choice of two or three building blocks, and say what each one covers.
Write an LRU cache from scratch with a hash map and a doubly linked list, and name the library shortcuts.
Explain the swap-with-last trick, the two-stack minimum and frequency buckets, and trace each by hand.
Ask the clarifying questions that change the design before writing code.

When to use it

A problem asks you to design a class with several operations, each with a required time cost
A cache with O(1) get and put and an eviction rule (LRU, LFU)
O(1) insert, delete and random pick from a set
Values stored with timestamps or versions and read back as of a time
A stack or queue that also answers min, max or most frequent in O(1)
No single built-in structure meets every required cost

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio