DataData/13 · Composite & Beyond
CHAPTER 13 · Composite & Beyond

Composite & Beyond

The first 12 chapters gave you single structures. This chapter combines them into working machines: LRU caches, segment trees, skip lists, and Bloom filters. Real systems almost never run on one structure alone. They run on a pair of structures that cover each other's weak operation.

§01

Combining structures into machines

No new base structures in this chapter, only new ways to combine them

Look back at the course. An array (chapter 1) gives O(1) random access. A linked list (chapter 3) gives O(1) insert and remove once you hold the node. A hash map (chapter 6) gives O(1) lookup by key. A heap (chapter 9) gives O(log n) access to the minimum or maximum. Each structure is fast at one thing and slow at something else.

Real requirements rarely need only one of those. "A cache must read in O(1) and evict the least recently used entry in O(1)." "An array must support updates and fast range sums." Every single structure gets stuck on one of the two operations. The usual answer is not a new structure. It is to put two structures together so that each one only performs the operation it can finish quickly. All six machines in this chapter are built that way.

MachineBuilt fromWhat it buys youWhere it is used
LRU cachehash map + doubly linked listO(1) read and O(1) eviction of the least recently used entryRedis, browser caches, OS page replacement
LFU cachetwo hash maps + one list per frequencyO(1) eviction of the least frequently used entrythe Redis allkeys-lfu policy
Segment treearray + binary tree over rangesrange queries with updates, both O(log n)database statistics, time-series aggregation, contests
Fenwick treearray + the lowbit bit operationprefix sums that stay correct after updatescounting problems, inversion counts, contests
Skip listsorted linked list + random index levelsexpected O(log n) search, insert, and delete in sorted orderRedis zset, LevelDB MemTable
Bloom filterbit array + k hash functionsa very small structure that can prove an element is absentcrawler deduplication, protecting a database from lookups of missing keys
Rule 01
Cover each other's weak operation

Each member only performs the operation it can finish in O(1) or O(log n), and never the one that would cost it O(n). In an LRU cache the hash map only looks up, and the list only maintains order.

Rule 02
Point at each other

The members store references to each other. The hash map value is a list node, and the list node stores the key back. Either side reaches the other in one step, with no search.

Rule 03
⚖️ Update every member together

Every operation must update all members in the same step. Removing a list node also removes its hash map entry. Losing that synchronization is the most common source of bugs in composite structures.

A method for design questions

When you are asked to "design an X", work in three steps. First, list every operation (get, put, delete, random, and so on). Second, write down the complexity budget for each one: does the problem require O(1) or O(log n)? Third, check where a single structure goes over budget, and add a second structure that covers exactly that operation. Every section in this chapter is one run through this method.

§02

LRU cache: hash map + doubly linked list

★ The most common design question in interviews

The main section of this chapter. Start from the requirements, rule out the alternatives, and build it.

Start from the requirement. A cache is storage that is fast but small. Memory is far faster than disk but cannot hold everything, so a cache keeps only the part of the data most likely to be read again. Being small leads to one unavoidable question: when the cache is full, which entry leaves?

The classic answer is to evict the entry that has not been used for the longest time. That policy is called LRU (least recently used). The reason it works is temporal locality: programs tend to read again, very soon, the data they have just read, and data that has not been touched for a long time is usually not needed soon either.

So the requirement list is fixed, and it is exactly LC 146: get(key) reads, put(key, value) writes, and a full cache evicts the least recently used entry automatically. Both operations must be O(1). A cache exists to be fast, so if its own operations were O(n) it would defeat its purpose.

Ruling out the alternatives: why this pair?

Do not memorize the answer. Cross out the candidates one at a time, the way you would in an interview, and the answer appears on its own.

Option 1 ✕

A hash map aloneget and put really are O(1). But which entry do you evict when it is full? A hash map spreads keys across buckets and has no notion of order, so it cannot tell which key was used least recently. To find out you would store a timestamp per key and scan the whole map for the smallest one: O(n). Ruled out.

Option 2 ✕

An array or a list alone, kept in access orderKeep the entries in a line ordered by last use: whatever is accessed moves to the front, and the last one is the eviction candidate. The order works. But get(key) must find the entry first, and there is no index to compute and no hash to look up, so you scan from the front: O(n). Ruled out.

Option 3 ✕

Array + hash map (the map stores the index)The map locates the array index in O(1), and the array keeps the order. But moving the accessed element to the front means deleting from the middle and inserting at the front of an array. As chapter 1 showed, every element after it shifts, which is O(n), and it also invalidates a whole range of indices stored in the map. Ruled out.

Option 4 ✕

Singly linked list + hash map (the map stores the node)Very close. The map stores key to list node, so you reach the node in one step, and list insertion and removal are O(1) once you hold the right node. But unlinking a node from the middle means setting the predecessor's next pointer to this node's next, and a singly linked node cannot reach its predecessor. Finding it means scanning from the head: O(n). One pointer short.

Option 5 ✓

Doubly linked list + hash mapGive every node a prev pointer. Now unlinking has both neighbors at hand, so removal is O(1) and inserting at the head is O(1), and the hash map still locates any node in O(1). The map answers "where is this key" and the list answers "how old is it". Each structure's O(n) operation is handled by the other one. This is the standard LRU design.

Common mistake: "list search is O(n), so LRU is O(n)"

That is wrong, because nothing in an LRU cache ever walks the list to find a node. Locating a node always goes through the hash map, which maps a key straight to a node reference. The list is used only after the node is already in hand, to unlink it and relink it at the head, and those are pointer updates in O(1). Each structure does only the operation it is fast at.

How an LRU cache is assembled: two structures, one job each
hash mapA → node refB → node refC → node refdoubly linked list (newest on the left, oldest on the right)HEADdummyBkey:valAkey:valCkey:valTAILdummyanswers "where": O(1)answers "how old": O(1) unlink and insert at head (prev + next)
The hash map does not store the value. It stores a reference to the list node. Lookup is the hash map's job, so nobody ever walks the list. Order is the list's job, so nobody ever scans the hash map. Each structure only does the operation it can finish in O(1).

There are only three rules, and all of them are O(1). ① A get that hits moves the node to the head of the list, which records that it was just used. ② A put of a new key links a node at the head and adds a hash map entry. ③ When the cache is full, unlink the last real node (tail.prev, the least recently used one) and delete its hash map entry in the same step. Run a few operations yourself:

LRU lab — capacity 3, hash map and doubly linked list side by side
hash map (key → list node reference)
A(no entry)
B(no entry)
C(no entry)
D(no entry)
HEADdummy
⇄
TAILdummy
← head = just used · tail = least recently used (evicted next) →
An empty cache with capacity 3. Put four different keys in a row to force one eviction. Then get an old key and watch it move back to the head.
0 ops · each O(1)
OperationWhat the hash map doesWhat the list doesCost
get(key), hitkey → node reference, one stepunlink the node, insert it at the headO(1)
get(key), missno such key, return -1not involvedO(1)
put, key existslocate the node, overwrite the valueunlink, then insert at the headO(1)
put, new key, not fulladd key → new nodeinsert the new node at the headO(1)
put, new key, fulldelete the evicted key's entry, add the new oneunlink tail.prev, insert the new node at the headO(1)

Writing it out (LC 146)

Dummy head and tail nodes come from chapter 3: put one empty node at each end and never delete them. Every insertion and removal then happens between two existing nodes, which removes all the null checks.

lc146_lru_cache.py
1class Node:
2 __slots__ = ("key", "val", "prev", "next") # saves memory per node
3 def __init__(self, key=0, val=0):
4 self.key, self.val = key, val
5 self.prev = self.next = None
6
7class LRUCache:
8 def __init__(self, capacity: int):
9 self.cap = capacity
10 self.map = {} # key -> node reference (one-step lookup)
11 self.head, self.tail = Node(), Node() # dummy head / dummy tail
12 self.head.next = self.tail # empty list: the dummies point at each other
13 self.tail.prev = self.head # from now on no null checks are needed
14
15 def _unlink(self, n): # O(1) removal: this needs the prev pointer
16 n.prev.next = n.next # the predecessor is right there, no scan
17 n.next.prev = n.prev
18
19 def _link_first(self, n): # O(1) insertion right after the dummy head
20 n.next = self.head.next
21 n.prev = self.head
22 self.head.next.prev = n
23 self.head.next = n
24
25 def get(self, key: int) -> int:
26 if key not in self.map:
27 return -1 # the map answers "present?" in O(1)
28 n = self.map[key]
29 self._unlink(n) # just used, so it becomes the newest
30 self._link_first(n) # unlink it, then put it back at the head
31 return n.val
32
33 def put(self, key: int, value: int) -> None:
34 if key in self.map: # already there: overwrite, move to head
35 n = self.map[key]
36 n.val = value
37 self._unlink(n)
38 self._link_first(n)
39 return
40 if len(self.map) == self.cap: # full: evict tail.prev, the oldest node
41 old = self.tail.prev
42 self._unlink(old)
43 del self.map[old.key] # list and map must be updated together
44 n = Node(key, value)
45 self.map[key] = n
46 self._link_first(n)
In production you can use collections.OrderedDict, which is itself a hash map plus a doubly linked list, or the functools.lru_cache decorator. Interviews ask for the hand-written version. A short version is in worked example A.

Java already ships this machine

The name of LinkedHashMap in the JDK says what it is: Linked (a doubly linked list) plus HashMap (a hash table). Every Entry sits in a hash bucket and also carries before/after pointers that link all entries into one doubly linked list. That is the machine you just wrote by hand. The constructor argument accessOrder = true makes the list follow access order instead of insertion order, and one overridden hook method completes the cache.

LRU with LinkedHashMap (accepted on LC 146)
1class LRUCache extends LinkedHashMap<Integer, Integer> {
2 private final int cap;
3
4 public LRUCache(int capacity) {
5 super(capacity, 0.75f, true); // accessOrder=true: each access moves the entry to the end
6 this.cap = capacity;
7 }
8
9 public int get(int key) { return super.getOrDefault(key, -1); }
10
11 public void put(int key, int value) { super.put(key, value); }
12
13 @Override // called after every put: returning true deletes the eldest entry
14 protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
15 return size() > cap;
16 }
17}
In an interview, write the full version first to show you understand the design, then add that in production you would use LinkedHashMap, because it is the same hash map plus doubly linked list.

Where LRU runs in practice

Redis: with maxmemory-policy allkeys-lru, Redis evicts by LRU when memory runs low. It uses an approximate LRU: keeping one global list of hundreds of millions of keys would cost too much memory for the pointers, so Redis samples a few keys at random and evicts the least recently used one among them. That trades a little accuracy for a large memory saving. Browsers: HTTP caches and decoded-image caches control their size with LRU variants. Operating systems: when physical memory runs out, the system must choose which page to write to disk. Common page replacement algorithms such as Clock are also approximations of LRU, because exact LRU would require updating a list on every single memory access.

§03

LFU: adding one more dimension

Least frequently used — evict by use count, and how LC 460 (hard) reaches O(1)

LRU asks how long ago an entry was used. LFU asks how often it has been used: it evicts the entry with the smallest use count, and when several entries have the same count, it evicts the least recently used one among them. LFU suits workloads where the popular items stay popular. One very popular entry should not be pushed out by a burst of one-time reads just because nobody touched it for ten minutes.

Why is LFU harder than LRU? In an LRU cache the oldest entry is always sitting at the tail of the list, so it is ready without any work. In an LFU cache the frequency changes on every access: the count goes up by one, so the entry has to move to a different position in the frequency order. A heap (chapter 9) would give O(log n) per adjustment, and it still would not break ties by recency. The O(1) solution is one bucket per frequency.

The core of LFU: one bucket per use count
freq = 1 ← minFreq points here
DE
Ordered by time inside the bucket: D entered before E, so an eviction removes D — the least recently used key among the least frequently used ones.
freq = 2
AC
One more access and A moves into the freq = 3 bucket
freq = 5
B
A frequent key. It is safe until every other key catches up
Each bucket is a list ordered by time, so a bucket is itself a small LRU. Add two hash maps (key to value and frequency, and frequency to bucket) plus one minFreq variable. An access moves the key from its freq bucket into the freq+1 bucket, and an eviction removes the oldest key in the minFreq bucket. Every step is O(1).

Three pieces of state. ① A hash map key → (value, freq). ② A hash map freq → bucket, where each bucket holds every key with that frequency in time order, so a bucket is itself a small LRU. ③ One variable minFreq holding the smallest frequency currently in use. An access moves the key from its freq bucket into the freq+1 bucket, which is two O(1) list operations. An eviction removes the oldest key in the minFreq bucket, which is the least recently used key among the least frequently used ones. minFreq needs no search either, because only two events change it: it goes up by 1 when the old bucket becomes empty (the key that just left was the last one in the minFreq bucket), and it resets to 1 when a new key is inserted, since a new key has frequency 1 and nothing can be lower.

lc460_lfu_core.py
1from collections import defaultdict, OrderedDict
2
3class LFUCache:
4 def __init__(self, capacity: int):
5 self.cap = capacity
6 self.kv = {} # key -> (val, freq)
7 # freq -> its keys (OrderedDict keeps insertion order: a small LRU)
8 self.buckets = defaultdict(OrderedDict)
9 self.min_freq = 0
10
11 def _touch(self, key): # one access: freq + 1, change bucket
12 val, f = self.kv[key]
13 del self.buckets[f][key]
14 if not self.buckets[f] and f == self.min_freq:
15 self.min_freq += 1 # old bucket is empty: minimum moves up
16 self.buckets[f + 1][key] = None
17 self.kv[key] = (val, f + 1)
18
19 def get(self, key: int) -> int:
20 if key not in self.kv:
21 return -1
22 self._touch(key)
23 return self.kv[key][0]
24
25 def put(self, key: int, value: int) -> None:
26 if self.cap == 0:
27 return
28 if key in self.kv: # already there: overwrite, freq + 1
29 self._touch(key)
30 self.kv[key] = (value, self.kv[key][1])
31 return
32 if len(self.kv) == self.cap: # evict the oldest key in the min_freq bucket
33 old, _ = self.buckets[self.min_freq].popitem(last=False)
34 del self.kv[old]
35 self.kv[key] = (value, 1)
36 self.buckets[1][key] = None
37 self.min_freq = 1 # a new key has frequency 1, the minimum
popitem(last=False) pops from the front of an OrderedDict, which is the oldest key in that bucket. There is no loop anywhere in this class, which is the direct evidence that every operation is O(1).

LRU or LFU? Each has a failure mode

LFU's weakness is that a formerly popular entry takes a long time to leave. An entry that was read tens of thousands of times yesterday and is never read again still has a very high count, so new entries need a long time to push it out. In practice this is fixed by decaying the counts over time; the Redis LFU policy has a decay factor. LRU's weakness is that a single large scan destroys it: one full-table read touches every row once and flushes the genuinely hot data out of the cache. Redis offers both policies so you can pick the one that matches your access pattern.

§04

Segment tree: a binary tree over ranges

Range query and point update, both O(log n)

A different kind of requirement. Given an array, you are asked many times for the sum of the range l to r. The prefix sum from chapter 1 already solves that: build the table once, then every query is O(1). Now add one condition: the elements can be modified. Changing a single a[i] invalidates every prefix sum after it, so the table has to be rebuilt in O(n). With 100,000 updates that is 100,000 rebuilds, and prefix sums stop being usable.

ApproachUpdate one elementOne range sum queryVerdict
Plain arrayO(1)O(n)Fast to update, slow to query. Fails when queries are frequent.
Prefix sumsO(n) rebuildO(1)Fast to query, slow to update. Fails when updates are frequent.
Segment treeO(log n)O(log n)Neither operation is the fastest possible, but neither one collapses.

Between those two extremes you want something where neither operation is bad. Split the whole range in half, and keep splitting until every part is a single element. That gives a binary tree (chapter 7), and each node stores the sum of its own range. The knowledge about sums is now spread over O(n) nodes, and any single update or query only has to touch O(log n) of them.

The segment tree built from nums = [2, 5, 1, 4, 9, 3] — every node stores the sum of its own range
24[0,5]8[0,2]16[3,5]7[0,1]1a[2]13[3,4]3a[5]2a[0]5a[1]4a[3]9a[4]
The root holds the sum of the whole array (24). Each level down splits the range in half, and a leaf holds a single element. A range of odd length gives the extra element to the left child: for [0,2], mid = (0+2)/2 = 1, so the children are [0,1] and [2,2]. The tree has ⌈log₂6⌉ + 1 = 4 levels, so its height is 3 edges, and every operation only walks one path from top to bottom.
update: change a leaf, then walk up

To change a[i], descend from the root, halving the range each time, until you reach that leaf, and write the new value. On the way back up, recompute the sum of every ancestor on the path as left child + right child. The number of nodes touched equals the height of the tree, so it is O(log n). Every other node still holds a correct sum, and that is what makes it better than prefix sums here.

query: three cases per node

To get the sum of [l,r], every node is in one of three situations. ① No overlap with [l,r]: return 0. ② Fully inside [l,r]: return the stored sum and stop descending. ③ Partial overlap: split and ask both children. At most 2 nodes per level end up in case ③, so the total number of visited nodes is O(log n).

Try it yourself. In update mode, click a leaf and watch one path from the leaf to the root light up. In query mode, set a range and watch which nodes are fully covered: the green nodes hand over a stored sum directly, without ever descending to a leaf.

Segment tree lab — 8 leaves, update mode and query mode
36[0,7]18[0,3]18[4,7]7[0,1]11[2,3]7[4,5]11[6,7]5a[0]2a[1]7a[2]4a[3]6a[4]1a[5]3a[6]8a[7]
Update mode: click any leaf and watch the update light up one path from that leaf back to the root.
n=8 · height log₂8+1 = 4

Writing it out (LC 307)

The tree is stored in a plain array: tree[1] is the root, and the children of node i are 2i and 2i+1, the same layout as the heap in chapter 9, so no node objects are created. The array is allocated with 4n entries. Here is why 4n and not 2n. If n is a power of two, the tree is perfect: it has n leaves and n−1 internal nodes, and the largest index used is below 2n. When n is not a power of two, the bottom level is incomplete, and the recursion can still place a leaf at an index in the level below the deepest full level. In the worst case the deepest index is under 4n, so 4n is always safe and needs no case analysis.

lc307_segment_tree.py
1class NumArray:
2 def __init__(self, nums: list[int]):
3 self.n = len(nums)
4 self.tree = [0] * (4 * self.n) # 4n entries is enough in the worst case
5 if self.n:
6 self._build(1, 0, self.n - 1, nums)
7
8 # build: node is responsible for the range [lo, hi]
9 def _build(self, node, lo, hi, nums):
10 if lo == hi: # a leaf holds one element
11 self.tree[node] = nums[lo]
12 return
13 mid = (lo + hi) // 2
14 self._build(2 * node, lo, mid, nums) # left child, left half
15 self._build(2 * node + 1, mid + 1, hi, nums) # right child, right half
16 self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
17
18 def update(self, index: int, val: int) -> None:
19 self._update(1, 0, self.n - 1, index, val)
20
21 def _update(self, node, lo, hi, i, val):
22 if lo == hi: # reached the leaf, write the value
23 self.tree[node] = val
24 return
25 mid = (lo + hi) // 2
26 if i <= mid:
27 self._update(2 * node, lo, mid, i, val)
28 else:
29 self._update(2 * node + 1, mid + 1, hi, i, val)
30 # on the way back up, recompute each ancestor on the path
31 self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
32
33 def sumRange(self, left: int, right: int) -> int:
34 return self._query(1, 0, self.n - 1, left, right)
35
36 def _query(self, node, lo, hi, l, r):
37 if r < lo or hi < l: # 1. no overlap: contributes 0
38 return 0
39 if l <= lo and hi <= r: # 2. fully inside: return the sum
40 return self.tree[node]
41 mid = (lo + hi) // 2 # 3. partial overlap: split
42 return (self._query(2 * node, lo, mid, l, r)
43 + self._query(2 * node + 1, mid + 1, hi, l, r))
The recursion depth is log n, so it will not reach Python's default recursion limit of 1000. That would need n larger than 2^1000.

Two extensions worth knowing by name

Replace + in the code with Math.max and the same tree answers range maximum queries. Any operation that is associative works here: sum, minimum, maximum, GCD, matrix product. That generality comes from the tree structure itself. The second extension is lazy propagation. A bulk update such as "add 5 to every element in [l,r]" is written as a mark on the large node that covers the range, and the mark is only pushed down to the children when a later operation actually needs them. Without lazy propagation, a range update means one point update per element, which is O(n log n). With it, a range update is O(log n). It is standard in programming contests and rare in interviews.

§05

Fenwick tree: prefix sums through the lowest set bit

Binary indexed tree — about 15 lines, smaller and faster than a segment tree, but it does less

A segment tree works, but it takes dozens of lines. If the only requirement is point update plus prefix sum query, there is a much smaller structure: the Fenwick tree, also called a binary indexed tree. It keeps a single array tree[1..n] and one rule: tree[i] holds the sum of the segment that ends at i and is lowbit(i) elements long.

lowbit(i) is the value of the lowest set bit in the binary form of i. You compute it with lowbit(x) = x & (-x). Here is why that works. In two's complement, -x = ~x + 1. Inverting turns the lowest 1 into a 0 and every bit below it into 1. Adding 1 then carries through those bits and stops exactly at the position of the original lowest 1. So x and -x agree on that one bit and differ everywhere else, and the AND keeps only that bit. Check it with 6: 6 = 0110, -6 = 1010, and 0110 & 1010 = 0010 = 2.

ibinarylowbit(i)range covered by tree[i]length
100011[1, 1]1
200102[1, 2]2
300111[3, 3]1
401004[1, 4]4
501011[5, 5]1
601102[5, 6]2
701111[7, 7]1
810008[1, 8]8

Read the pattern in the table: the more trailing zeros i has in binary, the longer the segment it covers. To get the prefix sum a[1..7], note that 7 = 0111 = 4 + 2 + 1, and the sum splits into tree[7] (1 element) + tree[6] (2 elements) + tree[4] (4 elements). Those three ranges meet end to end and never overlap. i -= lowbit(i) strips one set bit at a time, which is exactly this binary decomposition, so it runs at most log n times. An update goes the other way: i += lowbit(i) jumps to every larger segment that contains position i, also at most log n times. Worked example B animates both walks.

fenwick_tree.py
1class BIT:
2 def __init__(self, n: int):
3 self.n = n
4 self.tree = [0] * (n + 1) # indices 1..n; tree[0] is unused
5
6 def lowbit(self, x: int) -> int:
7 return x & (-x) # the lowest set bit of x
8
9 def add(self, i: int, delta: int) -> None:
10 while i <= self.n: # a[i] += delta (i starts at 1)
11 self.tree[i] += delta # every segment covering i gets +delta
12 i += self.lowbit(i)
13
14 def query(self, i: int) -> int: # prefix sum a[1..i]
15 s = 0
16 while i > 0:
17 s += self.tree[i] # add the next disjoint segment
18 i -= self.lowbit(i)
19 return s
20
21 def range_sum(self, l: int, r: int) -> int:
22 return self.query(r) - self.query(l - 1)
Python integers also use two's complement semantics for negative values, so x & -x works the same way. Python integers have unlimited precision, so there is no overflow to worry about.
CompareSegment treeFenwick tree
Amount of codeabout 50–60 linesabout 15 lines
Constant factor and spacerecursive calls and a 4n array, larger constant factorplain loops and an array of n+1, small constant factor, cache friendly
What it can answersum, minimum, maximum, GCD — any associative operation; with lazy propagation it also does range updatesonly operations where a range answer can be recovered by subtracting two prefixes (sum, xor). A minimum cannot be recovered that way, so range minimum is out.
Index convention0-based or 1-based, either worksmust be 1-based (lowbit(0) = 0 loops forever)
How to chooseIf you need prefix sums that survive updates, use a Fenwick tree. If you need minimum or maximum, range updates, or any merge that is not reversible by subtraction, use a segment tree.
§06

Skip list: express lanes over a sorted list

Expected O(log n) from coin flips — the structure behind the Redis sorted set

A limitation from chapter 3: searching a sorted linked list is O(n). The data is sorted, but you cannot binary search it, because binary search needs O(1) random access and a linked list does not provide it (chapter 1). You can only follow next one node at a time, and the sortedness is wasted.

A skip list fixes that by adding express lanes above the list. The bottom level L0 is the complete sorted list, and each level above it holds roughly half the nodes of the level below. A higher level has fewer nodes, so one step there covers more ground. A search starts at the top level and follows one rule: move right while the next node is still smaller than the target, otherwise drop down one level. By the time you reach L0 you are already next to the target.

Skip list lab — search(23): move right, drop down when the next node overshoots
L2L1L0H19∞H7192937∞H37111923293743∞
search(23). Start at the head node H on the top level L2. The top level has the fewest nodes, so each step there covers the most ground.
1 / 5

Each level holds about half the nodes of the level below, so there are about log₂n levels, and on each level you take only a couple of steps before dropping down. If you could take many steps on one level, the level above would have carried you further. The expected search cost is therefore O(log n). For n = 1,000,000 a plain sorted list needs about 500,000 comparisons on average, while a skip list needs on the order of 40. That matches binary search and a balanced tree, while keeping the linked list property that insertion and deletion only rewrite a few pointers.

Why decide the height with a coin flip?

Promoting exactly every second node would be ideal, but a single insertion destroys it: the new node shifts the position of every node after it, so the index levels would have to be rebuilt in O(n). A skip list instead lets each new node flip a coin for its height: heads means one more level, tails means stop, so each extra level has probability 1/2. Nobody maintains the exact pattern, but in expectation each level still holds half the nodes of the one below. The expected height of one node is 1 + 1/2 + 1/4 + … = 2, and the expected height of the whole list of n nodes is about log₂n.

What the expectation is over

This is important: the O(log n) is expected over the coin flips, not over the input. There is no bad input for a skip list, because the structure does not depend on the data at all. A very unlucky run of coin flips could still make it slow, but the probability of that is negligible. This is the same trade as choosing a random pivot in quicksort, or spreading keys with a hash function (chapter 6): randomness replaces expensive deterministic maintenance.

Why the Redis sorted set uses a skip list instead of a red-black tree

Both give O(log n) search, insert, and delete. Salvatore Sanfilippo, the author of Redis, gave three reasons. ① The implementation is far simpler: red-black tree insertion has a dozen rotation and recolouring cases, while skip list insertion is an ordinary linked-list insertion repeated once per level. ② Range operations are natural: ZRANGE asks for a rank interval, and a skip list locates the start and then walks forward along L0, while a tree needs repeated in-order traversal steps. ③ It is easier to modify; Redis added a span field to skip list nodes to support rank queries. LevelDB and RocksDB also use a skip list for their in-memory write buffer (the MemTable), partly because it suits lock-free concurrency: updating a few pointers is easier to make atomic than rotating a tree.

How to implement it (LC 1206): each node carries an array next[], where entry i is its successor on level i. All three operations share the same navigation logic. Start at the top level, move right on each level while the next value is still smaller than the target, and record the last node visited on each level in update[]. Insertion and deletion are then ordinary linked-list pointer updates performed after those recorded nodes.

lc1206_skiplist.py
1import random
2
3MAX_LEVEL = 16 # enough for about 2^16 nodes
4P = 0.5 # probability of one more level
5
6class Node:
7 def __init__(self, val, level):
8 self.val = val
9 self.next = [None] * level # next[i] = successor on level i
10
11class Skiplist:
12 def __init__(self):
13 self.head = Node(-1, MAX_LEVEL) # sentinel, has every level
14 self.level = 1 # highest level currently in use
15
16 def _random_level(self):
17 lv = 1
18 while random.random() < P and lv < MAX_LEVEL:
19 lv += 1 # keep flipping the coin
20 return lv
21
22 def search(self, target: int) -> bool:
23 cur = self.head
24 for i in range(self.level - 1, -1, -1): # start at the top level
25 while cur.next[i] and cur.next[i].val < target:
26 cur = cur.next[i] # move right while it is smaller
27 # cannot move right here, so the loop drops one level
28 cand = cur.next[0]
29 return cand is not None and cand.val == target
30
31 def add(self, num: int) -> None:
32 update = [self.head] * MAX_LEVEL
33 cur = self.head
34 for i in range(self.level - 1, -1, -1):
35 while cur.next[i] and cur.next[i].val < num:
36 cur = cur.next[i]
37 update[i] = cur # last node visited on level i
38 lv = self._random_level() # coin flips decide the new node's height
39 self.level = max(self.level, lv)
40 node = Node(num, lv)
41 for i in range(lv): # one ordinary list insertion per level
42 node.next[i] = update[i].next[i]
43 update[i].next[i] = node
44
45 def erase(self, num: int) -> bool:
46 update = [self.head] * MAX_LEVEL
47 cur = self.head
48 for i in range(self.level - 1, -1, -1):
49 while cur.next[i] and cur.next[i].val < num:
50 cur = cur.next[i]
51 update[i] = cur
52 cur = cur.next[0]
53 if cur is None or cur.val != num:
54 return False
55 for i in range(len(cur.next)): # bypass the node on each level
56 if update[i].next[i] is cur:
57 update[i].next[i] = cur.next[i]
58 return True
update = [self.head] * MAX_LEVEL stores the same head reference many times. That is safe here because the code only replaces list elements and never mutates one through the shared reference.

The title of the paper says it all

Skip lists come from a 1990 paper by William Pugh: Skip Lists: A Probabilistic Alternative to Balanced Trees. The paper argues that balanced trees are hard to implement correctly, and that a simpler randomized structure gives the same expected performance. More than thirty years later, Redis and LevelDB both use skip lists, which supports that argument.

§07

Bloom filter: trading accuracy for memory

A bit array plus k hash functions — it can prove absence, not presence

The last machine answers one very simple question: have I seen this before? A web crawler has to know whether a URL has already been fetched. With 10 billion URLs at about 60 bytes each, storing them in a hash set (chapter 6) would need roughly 600 GB, before counting any per-entry overhead. That does not fit.

A Bloom filter answers by not storing the data at all. It stores only the hash positions. It keeps one bit array of m bits and uses k different hash functions. Note what it cannot do: a Bloom filter cannot return the stored values, and it cannot tell you for certain that an element is present. It is not a fast set.

insert(x): set k bits

The k hash functions give k positions, and all of those bits are set to 1. x itself is not stored. One element costs at most k bits, and the bits are shared by all elements.

query(x): check the same k bits

Recompute the k positions. If any of those bits is 0, x was definitely never inserted, because insertion would have set it. If all k bits are 1, x may have been inserted, but other elements could also have set exactly those bits.

Notice how one-sided this is. The only two answers are definitely not present and possibly present. The reason is that bits only go from 0 to 1 and are never cleared. Another element can set your bits as a side effect, which produces a false positive, but no operation ever clears a bit, so there is never a false negative. Try to produce a false positive yourself:

Bloom filter lab — m = 16 bits, k = 3 hash functions
00
01
02
03
04
05
06
07
08
09
010
011
012
013
014
015
inserted: (nothing yet)
16 bits and 3 hash functions. Insert a few words, then query a word you never inserted. With this few bits you will see a false positive quickly.

The false positive rate is not fixed. It depends on three things: the size of the bit array m, the number of hash functions k, and the number of elements actually inserted n. Two qualitative rules. A larger bit array relative to the number of elements (larger m/n) lowers the rate, because the bits fill up more slowly. The number of hash functions k has an optimum: too few and each element leaves too small a fingerprint, so collisions are likely; too many and each element sets too many bits, so the array fills up and the rate rises again. In practice you pick m and k from a target rate. For example, 10 bits per element with k = 7 gives about 1 percent. A hash set needs hundreds of bits per element, so the saving is one to two orders of magnitude.

Using it as a first filter

Crawler deduplication: 10 billion URLs at 10 bits each is about 12 GB, which fits on one machine. A 1 percent false positive rate only means skipping a very small number of new pages. Protecting a database from lookups of missing keys: a flood of requests for keys that do not exist in the database passes straight through the cache and reaches the database every time. Put all existing keys into a Bloom filter in front of the cache, and every request the filter reports as definitely absent is rejected immediately. Spam and malicious URL lists: the blocklist is too large to keep in memory, so the filter decides whether an expensive exact check is worth running. The pattern is always the same: nothing that was inserted is ever wrongly rejected, and the small number of wrongly accepted items are checked again by a slower exact lookup.

Two common mistakes

① A plain Bloom filter does not support deletion. One bit can be shared by several elements, so clearing it would also remove those other elements from the filter, which would create false negatives and break the one guarantee the structure provides. If you need deletion, use a counting Bloom filter, where each position is a small counter instead of a single bit, or a cuckoo filter. ② The false positive rate rises with the number of inserted elements. If you size the filter for 10 million entries and insert 100 million, almost every bit is 1, "possibly present" becomes the answer for everything, and the filter stops being useful. Estimating the number of elements in advance is a precondition for using one.

Proposed in 1970, used more today

Burton Bloom proposed this structure in 1970, when memory was measured in kilobytes and giving up a little accuracy for a large memory saving was a necessity. Memory has become far cheaper since then, yet the structure is used more than ever, because data volumes have grown faster than memory. Redis, HBase, Cassandra, and Chrome all contain one.

§09

Problem set: 8 composite structures

Final problem set

Easiest first. Do 303 and 307 together as a pair, then work through the three hard ones.

§10

Chapter quiz

✎ Quiz

Answer all 7 correctly to complete the last chapter

QUESTION 01 / 7

In a hand-written LRU cache the hash map already reaches any list node in O(1). So why does the list still have to be doubly linked?

QUESTION 02 / 7

In Java, new LinkedHashMap<>(cap, 0.75f, true) plus an override of removeEldestEntry is already a working LRU cache. What does it maintain internally that makes this possible?

QUESTION 03 / 7

The data is loaded once and never modified afterwards, and then you answer a very large number of range sum queries. Which structure should you choose?

QUESTION 04 / 7

A Fenwick tree is built on one bit operation: it extracts the lowest set bit of x (the value usually called lowbit). Write that expression, using x as the variable.

QUESTION 05 / 7

When a skip list inserts a node, it flips a coin to decide how many index levels the node gets, instead of maintaining an exact "every second node is promoted" structure. Why?

QUESTION 06 / 7

A Bloom filter can be wrong in one direction only. Which kind of mistake can it make?

QUESTION 07 / 7

Which pair of structures does Redis use for a sorted set (zset) once the data is large?

What to take away from this chapter
  • The method: list every operation and its complexity budget, then pick base structures that cover each other. Each member performs only the operation it can finish in O(1) or O(log n), and the two are joined by storing references to each other and updating all members in the same step.
  • LRU = hash map (answers "where") + doubly linked list (answers "how old"), with get and put both O(1). The list must be doubly linked, because unlinking a node updates its predecessor's next pointer and a singly linked node cannot reach its predecessor. The node must store the key, so the matching hash map entry can be deleted on eviction. Java gives you the same machine as LinkedHashMap with accessOrder = true.
  • LFU is harder than LRU because the frequency changes on every access. O(1) needs a frequency map, one time-ordered list per frequency, and a minFreq pointer. The eviction rule is: least frequently used, and among those, least recently used.
  • Range queries in three cases: queries only means prefix sums with O(1) queries; updates mixed with queries means a segment tree or a Fenwick tree, both O(log n). A segment tree handles any associative merge and, with lazy propagation, range updates in O(log n) instead of O(n log n). A Fenwick tree is about 15 lines and uses lowbit = x & (−x) to isolate the lowest set bit, but it only works for operations recoverable by subtracting two prefixes, and it must be 1-based.
  • Skip list = sorted linked list + index levels grown by coin flips: expected O(log n), where the expectation is over the coin flips and not over the input, so there is no bad input. Randomization replaces the rotation maintenance of a balanced tree. It is the structure behind the Redis sorted set (skip list + hash table) and the LevelDB MemTable.
  • Bloom filter = bit array + k hash functions: "not present" is certain, "present" is only possible, because bits only go from 0 to 1. You cannot delete from a plain one, and the false positive rate depends on the bit array size, the number of hash functions, and the number of inserted elements. It is a first filter, not a faster set.
  • None of these six machines uses a new base structure. Arrays, linked lists, hash maps, trees, and bit operations all came from the first 12 chapters. For a design question: restate the operations and the complexity target, then name the combination, then point out yourself what has to be kept in sync between the two structures.