Custom Data Structures

Design a class whose every method meets a required time bound, by combining a hash map, a linked list, an array or a stack so that each covers what the others cannot.

Overview

What the problem asks

A design problem lists methods and a time bound for each: get and put in O(1), or push, pop, top and getMin in O(1). No single built-in structure meets every bound at once. The work is to pick two or three that together do, and to keep them in step on every call.

Find by key in O(1) — Hash map — Key to node or index
Remove a known node in O(1) — Doubly linked list — The node knows its neighbors
A random element in O(1) — Array — Index by a random number
Delete from an array in O(1) — Swap with the last element, then pop — Only the end of an array is cheap to remove
The min or max so far in O(1) — A second stack, or a min stored with each entry — The history is a stack too
The least or most frequent in O(1) — Buckets by frequency, linked in order — A count only moves by one

The method is always the same: list the operations, map each to a row above, and design the fields so every operation stays inside its bound.

LRU cache: hash map plus doubly linked list

An LRU cache holds at most a fixed number of key-value pairs and, when full, evicts the one used longest ago. Both get and put must be O(1). The hash map finds a key's node in O(1); the list keeps the nodes in order of use, most recent at the front, and a doubly linked node can be unlinked and re-linked at the front in O(1). Two sentinel nodes, head and tail, mean no method ever checks for an empty list.

A trace with capacity 2. The list is shown most recent first.

put(1, 1) — 1
put(2, 2) — 2, 1
get(1) — 1 — 1, 2 — Moved to the front
put(3, 3) — 3, 1 — Full: evicted 2, the last node
get(2) — −1 — 3, 1 — Not present
put(4, 4) — 4, 3 — Evicted 1
get(1) — −1 — 4, 3
get(3) — 3 — 3, 4

Two rules keep the structures in step: every unlink also updates the map, and put on an existing key updates the value and moves the node to the front rather than adding a second node. Python's OrderedDict (move_to_end and popitem(last=False)) and Java's LinkedHashMap in access order with removeEldestEntry give the same behavior in a few lines; say so, then build it by hand, which is the version worth knowing.

Insert, delete and random in O(1)

An array gives a random element in O(1) but deletes in O(n). The fix is to delete only from the end: swap the element to remove with the last one, pop, and keep a map from value to index so the swap can be found.

insert(10) — [10] — 10 → 0
insert(20) — [10, 20] — 10 → 0, 20 → 1
insert(30) — [10, 20, 30] — 10 → 0, 20 → 1, 30 → 2
remove(10) — [30, 20] — 30 → 0, 20 → 1 — 30 moved into index 0, then the end was popped
getRandom() — A random index into [30, 20]

Min stack: carry the minimum with each entry

A stack with getMin in O(1) stores, with each pushed value, the minimum of the stack at that moment. Pop discards both; getMin reads the top pair. No search is ever needed.

push(5) — (5, 5) — 5
push(3) — (5, 5), (3, 3) — 3
push(7) — (5, 5), (3, 3), (7, 3) — 3
pop() — (5, 5), (3, 3) — 3
pop() — (5, 5) — 5

LFU cache: buckets by frequency

An LFU cache evicts the key used least often, and among ties the one used longest ago. Keep a map from key to node (value and count), and a map from count to a doubly linked list of the keys with that count, in order of use. Track the smallest count in use.

Every step is a map lookup or a linked-list unlink, so get and put are O(1). Put on a new key with the cache full evicts the first key of bucket[minCount], then inserts the new key with count 1 and sets minCount to 1. The idea is from Matani, Shah and Mitra, whose paper gives O(1) for insertion, access and eviction. Their version keeps the frequency buckets themselves in a doubly linked list ordered by count, so the smallest bucket is always the first one and no minCount is needed; the map-plus-minCount form above is the same design with one more variable.

What you will be able to do

Turn a list of required bounds into a set of fields before writing a method.
Write an LRU cache with sentinels from memory, and name the library shortcut.
Explain the swap-with-last trick and why it keeps a random pick uniform.
Design min stack, max stack and LFU cache and state each method's cost.
Keep two structures in step and test the edge cases: empty, full, update of an existing key.

When to use it

The problem gives a class with named methods and a time bound for each
Two or more operations need O(1) and no single built-in gives both
A cache with an eviction rule: least recently used, least frequently used, or by time
A stack or queue that also reports its min or max in O(1)
A collection that needs insert, delete and a uniform random element in O(1)
Any container whose invariant must hold across several linked structures

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio