What is a data-structure design problem?
A data-structure design problem asks for a class instead of one function. The statement lists the methods, what each one returns and, in three of this lesson's four problems, how fast each call must run: on average. The judge then calls the methods in some order, up to 200,000 times in each problem here, and checks every return value. Let's start with an example.
Design a class RandomizedSet that holds a set of integers. insert(val) adds val and returns true, or returns false if val is already stored. remove(val) deletes val and returns true, or returns false if val is missing. getRandom() returns one stored value, each stored value with the same probability. Every method must run in time on average.
LeetCode creates the object and calls the methods in the order given. The output lists what each call returns, with null for the constructor.
Constraints
-
val - At most calls in total
getRandomis only called when the set holds at least one value
Sample · Input
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]
Output
[null,true,false,true,2,true,false,2]
Before thinking about structures, let's read the sample call by call. insert(1) returns true. remove(2) returns false, because 2 was never inserted. insert(2) returns true, so the set holds 1 and 2 and the first getRandom() may return either; the output shows one possible run. remove(1) returns true, the second insert(2) returns false because 2 is already stored, and the last getRandom() must return 2, the only value left.
A hash set and an array each manage part of the job in . A hash set inserts and removes in on average, but its members have no positions 0, 1, 2 to choose among, so picking a random member means walking the set. An array picks values[k] for a random index in one step, but finding val to remove it is a scan. With values stored, removals of a value that is not there each read every slot:
At a judge's rough rate of simple steps a second, that is around 100 seconds.
Keep two views of the same items
Each structure is fast for part of the job, so we store the same items in both. A design built this way keeps two views of the same items: one finds an item by its key, and the other keeps the position, order or count the remaining methods ask about. The price is bookkeeping: every method that adds, moves or removes an item updates both views before it returns, so the next call finds them in agreement.
We build four designs this way: the set above, a cache that evicts the key used longest ago, a store that answers by timestamp, and a cache that evicts the key used the fewest times.
Keep an array and an index map
Let's start with RandomizedSet. Its two views are an array values, which holds the members in any order, and a hash map where, which records each member's index in that array. insert appends to the array and records the new index, and getRandom picks a random index. For remove, the map gives us val's index, so we never scan.
Removing from the middle of an array, though, shifts every later value one place left, which takes time proportional to the number of values shifted and leaves each shifted value's map entry wrong. The array keeps its members in any order, so any value can fill the gap. We copy the last value into the gap, record its new index in where, and pop the last slot. Removing 10 from [10, 20, 30] moves 30 into index 0 and leaves [30, 20]. Only one value moved, so only one map entry changes.
class RandomizedSet:
def __init__(self):
self.values = [] # the stored values, in any order
self.where = {} # value -> its index in values
def insert(self, val):
if val in self.where:
return False
self.where[val] = len(self.values)
self.values.append(val)
return True
def remove(self, val):
if val not in self.where:
return False
i = self.where[val]
last = self.values[-1]
self.values[i] = last # move the last value into the gap
self.where[last] = i
self.values.pop()
del self.where[val]
return True
def getRandom(self):
return random.choice(self.values)
s = RandomizedSet()
print(s.insert(1), s.remove(2), s.insert(2))
print(s.getRandom() in (1, 2))
print(s.remove(1), s.insert(2), s.getRandom())The lines after the class replay the sample. The first getRandom() is random, so the program prints whether it returned 1 or 2.
remove(10) on [10, 20, 30]. One value moves, so one map entry changes, whatever the size of the set.When val is itself the last value, i is the last index, so the copy writes val onto itself and the pop removes it. This case works only because the code deletes val's map entry after where[last] = i runs. In the other order, that line would put val back into the map.
getRandom is fair because each value occupies exactly one slot of the array, so a uniformly random index in returns each value with probability . Every method does at most four map operations and a fixed number of array writes, so each runs in on average.
Recall What goes wrong if remove forgets to update the moved value's index?
Start from [10, 20, 30] and remove 10 without the line where[last] = i. The array becomes [30, 20], but the map still says 30 is at index 2, past the end. Removing 30 next sends the method to index 2: Python raises IndexError, and C++ writes past the end of the vector, which is undefined behavior.
Insert 50 before that removal and the failure turns quiet: 50 takes index 2, so removing 30 copies 50 onto itself and pops it. Now 30 is in the array but missing from the map, and getRandom() can return a value the set says it does not hold. Every one of these calls returned the right value, so the bug shows only later, through getRandom().
Match each question to a structure
RandomizedSet paired a map with an array because one method names an item by its value and another asks for a position. The other designs follow the same recipe: write down what each method has to find, then pick a structure that finds it in the time allowed.
| The method needs | Structure | Cost |
|---|---|---|
| The value or record stored under a key | Hash map, dict | average |
| The item at position , or a uniformly random item | Array, list | |
| To unlink or move an item it already holds | Doubly linked list node | |
| The oldest or newest arrival | Queue, deque or linked list | |
| The smallest or largest value | Heap | to read, to add or remove |
| The last entry at or before a time | Sorted list with binary search |
Evict the key used longest ago
Design a class LRUCache(capacity) that stores at most capacity keys, each with a value. get(key) returns the key's value, or -1 if the key is not stored. put(key, value) stores the value under the key, replacing any old value. If a put adds a new key and the cache then holds more than capacity keys, it removes the key whose last get or put is the oldest. Both methods must run in time on average.
Constraints
-
capacity -
keyandvalue - At most calls to
getandput
Sample · Input
["LRUCache","put","put","get","put","get","put","get","get","get"] [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output
[null,null,null,1,null,-1,null,-1,3,4]
Let's read the sample. The capacity is 2. After put(1, 1), put(2, 2) and get(1), key 1 has been used more recently than key 2, so put(3, 3) evicts key 2. Key 3 was then put after key 1's last use, so put(4, 4) evicts key 1. The gets return 1, -1, -1, 3 and 4.
This policy is called least recently used, or LRU. To make the least recently used key easy to find, we write the keys in a line from most recent to least recent. The policy then becomes two list operations: each use moves a key to the front, and an eviction removes the key at the back.
The methods then ask three questions: where is this key, how do we move its entry to the front, and which entry is at the back? A hash map answers the first. For the other two we need a list that can move an entry from anywhere in once we hold its node: a doubly linked list, whose nodes each link to both neighbours. Finding a node in a linked list means walking from one end, which is slow, but this design never searches the list: the map hands us the node, and unlinking or relinking it touches only the node and its neighbours.
Store recency in a linked list and find nodes with a map
We keep the entries in a doubly linked list, most recent first. Each node stores a key, a value and links to the nodes before and after it. Beside the list, a hash map sends each key to its node, so a get finds the node without walking the list.
The ends of the list need care. The first entry has no node before it and the last has none after it, so linking or unlinking at either end would need its own case in every method. Instead, we put a dummy node, which holds no entry, at each end: a head before the newest entry and a tail after the oldest. Every real node then has a node on both sides, even when it is the only entry, so the same few lines handle every position, and the entry to evict is always tail.prev.
Once we hold the node, a move takes a fixed number of writes. Unlinking node x rewrites two links, x.prev.next = x.next and x.next.prev = x.prev. Linking it in just after the head rewrites four: x's own two links, the back link of the node that was first, and head.next. In total:
That count is the same whether the cache holds 2 entries or 2 million.
get(4) unlinks node 4 and links it after the head. The map entry points at the node object, so it needs no update.Step through LRU cache lookup, update and eviction
The cache below has capacity 2 and starts after the sample's first two calls, put(1, 1) and put(2, 2). If we get 1, its node moves to the front while its map entry still points at the same node. If we then put 3, key 2, the node before the tail, leaves both the list and the map.
A hit costs 6 pointer writes and an insert costs 4, plus 2 more when it evicts.
Move and evict with unlink and push_front
Now let's put the pieces into code. The node stores its key as well as its value, because evicting a node means deleting its map entry, and the key is how we find that entry. unlink removes a node from the list, and push_front links it just after the head dummy.
class Node:
def __init__(self, key=0, value=0):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.nodes = {} # key -> its node
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
def unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.nodes.get(key)
if node is None:
return -1
self.unlink(node)
self.push_front(node)
return node.value
def put(self, key, value):
node = self.nodes.get(key)
if node is not None:
node.value = value
self.unlink(node)
self.push_front(node)
return
node = Node(key, value)
self.nodes[key] = node
self.push_front(node)
if len(self.nodes) > self.capacity:
oldest = self.tail.prev
self.unlink(oldest)
del self.nodes[oldest.key]
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3) # evicts key 2
print(cache.get(2))
cache.put(4, 4) # evicts key 1
print(cache.get(1), cache.get(3), cache.get(4))The lines after the class replay the sample and print the five gets.
A put on an existing key overwrites the value and moves the node like a hit, and it never evicts, because the number of keys stays the same. Only a new key can push the cache past capacity.
Worked example
Trace gets, updates and evictions
The trace below runs a list of calls, written [1, key, value] for a put and [0, key] for a get, and shows the list after each one, most recent first. The first preset is the sample. The others show a capacity of 1, where every new key pushes the previous one out, and puts on keys that are already stored, which move the key without evicting.
The cache starts empty with room for 2. The list runs from most to least recently used; the map points each key at its node.
- size
- 0 of 2
- answers
- none yet
Change the example input
Current result: [1,-1,-1,3,4]
Deeper read: why the map and the list never disagree
To see that the two views stay in step, we check one statement that holds between calls: the map and the list hold exactly the same keys, each key has one node, the list runs from most to least recently used, and it holds at most capacity keys. The constructor links an empty head and tail and creates an empty map, so this holds before the first call.
A miss changes nothing. A hit or an update unlinks the node the map found and links it at the front, so the set of keys is unchanged and that key becomes the most recent. A new key adds one node at the front of the list and one map entry. If the cache now holds keys, the node before the tail is the least recently used one by the list order, and removing it from both views restores the bound. Every call leaves the statement true, so a get finds a node exactly when its key is still cached.
Recall Why does a singly linked list not give the same update cost?
The map can find a node, but a singly linked node does not know its predecessor. Unlinking it would need a walk from the front to find the node before it, which is the search the design set out to avoid. A doubly linked node gives both neighbours directly.
An array of keys has a back end too, but moving a hit from the middle shifts every entry after it.
How do you look up a value as it was at time t?
Design a class TimeMap. set(key, value, timestamp) records that key held value from that timestamp on. get(key, timestamp) returns the value from the set for key with the largest timestamp at most the one asked for, or the empty string "" if no such set exists.
Constraints
- Keys and values have 1 to 100 lowercase letters and digits
-
timestamp - The timestamps passed to
setare strictly increasing - At most calls to
setandget
Sample · Input
["TimeMap","set","get","get","set","get","get"] [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output
[null,null,"bar","bar",null,"bar2","bar2"]
In the sample, get("foo", 3) returns "bar". No set happened at time 3 or 2, so the answer is the value set at time 1. After set("foo", "bar2", 4), gets at times 4 and 5 return "bar2".
The two views this time are the map, which still finds a key, and each key's history: the timestamps of its sets and the value set at each one. A get asks for the last timestamp at most , and a scan of the history would take longer with every set.
The timestamps passed to set only grow, so appending each set keeps every key's timestamps sorted, and in a sorted list a get is a binary search for the last timestamp at most . Python's bisect_right and C++'s upper_bound return the first position whose timestamp is greater than . Every position before holds a timestamp at most , so counts them, and the answer sits one position before it:
class TimeMap:
def __init__(self):
self.times = defaultdict(list) # key -> its timestamps, increasing
self.values = defaultdict(list) # key -> the value set at each timestamp
def set(self, key, value, timestamp):
self.times[key].append(timestamp)
self.values[key].append(value)
def get(self, key, timestamp):
i = bisect_right(self.times[key], timestamp)
return self.values[key][i - 1] if i > 0 else ""
store = TimeMap()
store.set("foo", "bar", 1)
print(store.get("foo", 1), store.get("foo", 3))
store.set("foo", "bar2", 4)
print(store.get("foo", 4), store.get("foo", 5))The lines after the class replay the sample.
In the figure, the timestamps of foo are [1, 4]. For a get at time 3, the first one greater than 3 is at index , so the answer is the value at index 0, "bar". For a time before the first set, such as 0 in the figure, ; no timestamp comes before position 0, so the method returns the empty string.
A set appends to two lists. Most appends write one entry, but when a list's block of memory is full, the append copies every entry into a new block a constant factor larger. A copy of entries leaves room for a number of further appends proportional to , so spread over those appends, the copying costs each one a constant number of steps. So a set costs amortized: any sequence of sets takes time per set in total, even though the set that triggers a copy takes longer.
A get costs , where is the number of sets for that key. At the limit, when one key holds close to sets, a get on it takes
Evict the key used the fewest times
Design a class LFUCache(capacity) with the same get and put as LRU Cache and a different eviction rule. Each stored key has a use counter, set to 1 by the put that adds it and raised by 1 on every later get or put of that key. When a put adds a new key to a full cache, it first removes the key with the smallest counter, and among keys tied on the smallest counter, the one whose last use is the oldest. Both methods must run in time on average.
Constraints
-
capacity -
keyandvalue - At most calls to
getandput
Sample · Input
["LFUCache","put","put","get","put","get","get","put","get","get","get"] [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
Output
[null,null,null,1,null,-1,3,null,-1,3,4]
Let's read the sample. put(3, 3) evicts key 2, used once by its put, rather than key 1, used twice by its put and a get. Then get(3) brings key 3 to two uses as well, so put(4, 4) has to break a tie between keys 1 and 3, and it evicts key 1, whose last use is older.
This policy is called least frequently used, or LFU. Among the keys with the smallest count, the rule is exactly LRU: evict the one used longest ago. So the design reuses the LRU idea once per count. We keep one recency list for each use count, holding the keys with that count from oldest use to newest, and a map from each key to its value and count. We also keep min_count, the smallest count that currently has any keys, so the key to evict is always the oldest entry of list min_count. Two kinds of call change the lists:
- A get hit or a put on an existing key moves the key from list to the newest end of list . This changes
min_countonly when list is now empty and wasmin_count. Then the moved key itself has count , somin_countbecomes without any scan. - A put of a new key adds it to list 1 and sets
min_countto 1. If the cache was full, the put first removes the oldest key of listmin_count.
get(3) in the LFU sample empties list 1, the list min_count named, so min_count moves up to 2 with the key.Track the count lists after each call
Let's replay the sample with the lists written out. Each list is written oldest use first, so the key an eviction removes is the first one in list min_count.
| Call | Returns | Lists after | min_count |
|---|---|---|---|
put(1, 1) | count 1: [1] | 1 | |
put(2, 2) | count 1: [1, 2] | 1 | |
get(1) | 1 | count 1: [2]; count 2: [1] | 1 |
put(3, 3) | count 1: [3]; count 2: [1] (key 2 evicted) | 1 | |
get(2) | -1 | unchanged | 1 |
get(3) | 3 | count 2: [1, 3] | 2 |
put(4, 4) | count 1: [4]; count 2: [3] (key 1 evicted) | 1 | |
get(1) | -1 | unchanged | 1 |
get(3) | 3 | count 1: [4]; count 3: [3] | 1 |
get(4) | 4 | count 2: [4]; count 3: [3] | 2 |
Move keys between count lists
Python's OrderedDict serves as each recency list: assigning a key appends it at the newest end, del removes any key in , and popitem(last=False) removes the oldest. C++ uses a std::list per count and stores each key's position in that list, so a move is an erase and a push_back.
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.value = {} # key -> value
self.count = {} # key -> times used
self.by_count = defaultdict(OrderedDict) # count -> keys, oldest use first
self.min_count = 0
def touch(self, key):
c = self.count[key]
del self.by_count[c][key]
if not self.by_count[c]:
del self.by_count[c]
if self.min_count == c:
self.min_count = c + 1
self.count[key] = c + 1
self.by_count[c + 1][key] = None
def get(self, key):
if key not in self.value:
return -1
self.touch(key)
return self.value[key]
def put(self, key, value):
if key in self.value:
self.value[key] = value
self.touch(key)
return
if len(self.value) == self.capacity:
oldest, _ = self.by_count[self.min_count].popitem(last=False)
if not self.by_count[self.min_count]:
del self.by_count[self.min_count]
del self.value[oldest], self.count[oldest]
self.value[key] = value
self.count[key] = 1
self.by_count[1][key] = None
self.min_count = 1
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3) # evicts key 2
print(cache.get(2), cache.get(3))
cache.put(4, 4) # evicts key 1
print(cache.get(1), cache.get(3), cache.get(4))The lines after the class replay the sample and print the six gets.
Empty lists are deleted, so every remaining list holds at least one key and there are never more lists than keys. Every step of touch and of an eviction is a map lookup or a constant number of list operations, so both methods are on average.
Time and space for each design
- RandomizedSet, each method
average - Removal moves exactly one value.
- LRU get and put
average - One map lookup and at most 6 pointer writes.
- TimeMap set / get
amortized / - A set appends to two lists; a get binary searches the timestamps of one key.
- LFU get and put
average min_countchanges without a scan.- Space
- One node, slot or list entry per item, plus its map entry.
- LRU with a plain list of keys
per call - Finding a key to move it is a search; 3,000 keys and 200,000 calls is up to steps.
The average bounds assume a hash map with constant expected cost per lookup, with occasional resizing spread over many inserts. The pointer and list operations themselves are worst-case .
Bugs that leave the two views out of step
Updating a key's value in an LRU cache without moving its node to the front.
- Where it breaks
- Capacity 2:
put(1, 1),put(2, 2),put(1, 10),put(3, 3), thenget(2),get(1)andget(3). The right answers are[-1, 10, 3]; without the move, key 1 is evicted and the answers are[2, -1, 3]. - The fix
- A put on an existing key is a use, so it overwrites the value and moves the node.
Evicting before checking whether the key is already stored.
- Where it breaks
- Capacity 2 after
put(1, 1)andput(2, 2):put(2, 20)evicts key 1, the least recently used, although updating key 2 adds no key, soget(1)returns-1instead of1. - The fix
- The put looks the key up first and evicts only when a new key pushes the size past capacity.
Unlinking the evicted node but leaving its key in the map.
- Where it breaks
- Capacity 1:
put(1, 10),put(2, 20),get(1). The map still finds the old node and returns10instead of-1, and moving that node links it back into the list. - The fix
- The eviction reads the key from
tail.prevbefore unlinking the node, then deletes that key from the map.
Building the linked list without dummy nodes.
- Where it breaks
- Removing the only node runs
node.prev.next = node.nextwithnode.prevset toNone, and Python raisesAttributeError. - The fix
- The constructor creates a head and a tail dummy once, so every real node has neighbours on both sides.
Raising
min_countafter an LFU hit without checking that its list became empty.- Where it breaks
- In the LFU sample,
get(1)raisesmin_countto 2 while key 2 still has count 1.put(3, 3)then evicts key 1 from list 2, so the gets return[1, 2, 3, -1, 3, 4]instead of[1, -1, 3, -1, 3, 4]. - The fix
min_countrises only when the list it names has just become empty.
Further reading
- Pat MorinOpen Data Structures, Chapter 3: Linked lists(opens in a new tab)
Section 3.2 builds a doubly linked list around one dummy node that stands both before the first node and after the last, so adding and removing a node never needs a special case at either end, and shows that both take constant time once you hold the node. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.
- Python documentationcollections: OrderedDict objects(opens in a new tab)
move_to_endandpopitem(last=False)are the two LRU operations; the recipes after it build a time-bounded LRU cache from them. - cp-algorithmsMinimum Stack / Minimum Queue(opens in a new tab)
Another two-view design: each stack entry also stores the minimum below it, and a queue built from two such stacks answers its minimum in amortized.
- Redis documentationKey eviction(opens in a new tab)
How a production cache evicts: Redis samples a few keys at random instead of keeping an exact LRU list, and its LFU policy keeps a small decaying counter per key.
- WikipediaCache replacement policies(opens in a new tab)
LRU and LFU beside the other rules caches use, starting from Bélády’s optimal rule, which evicts the item needed furthest in the future.