Design Problems and the LRU Cache
30 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A hash map is fast but plain. Many interview designs add one more idea to it: order, a list or a counter. You will build a cache that drops the least recently used item, first with the tool Python gives you and then by hand, and a set that can return a random element.
Design problems: a map plus one more idea
A cache is a small, fast store that keeps recent or frequent results, so repeating the same request does not redo slow work.
A design problem asks for a small class whose operations all run in constant time. A hash map gives fast lookup by key. It cannot give order or a random pick, so you pair it with a second structure.
def two_sum(nums, target): seen = {} for i, n in enumerate(nums): if target - n in seen: return seen[target - n], i seen[n] = i return NoneExample 1 · Two sum: nested loops against a map
nums, target = [11, 15, 2, 7], 9
checks = 0for i in range(len(nums)): for j in range(i + 1, len(nums)): checks += 1 if nums[i] + nums[j] == target: break else: continue breakprint("pairs checked:", checks)
seen = {}for i, n in enumerate(nums): if target - n in seen: print("indices:", seen[target - n], i) break seen[n] = ipairs checked: 6 indices: 2 3
What this code does
- The nested loops try pairs until they hit the right one: O(n squared) time in the worst case, O(1) extra space.
- The map version checks each number once: O(n) time and O(n) space. It trades memory for speed, which is the usual use of a hash map.
The map remembers each number and where it was seen, so the partner is found in one lookup instead of a second loop. Many designs follow this shape: a dictionary for speed and something else for what it lacks.
LRU cache with OrderedDict
An LRU cache keeps at most a fixed number of items and, when full, removes the least recently used one. Each get or put counts as a use.
A cache has room for only a few items. When it is full, it should drop the one not used for the longest time. That rule is least recently used. OrderedDict is a hash map that also remembers order.
from collections import OrderedDictclass LRUCache: def __init__(self, capacity): self.capacity = capacity self.items = OrderedDict() def get(self, key): if key not in self.items: return -1 self.items.move_to_end(key) return self.items[key] def put(self, key, value): self.items[key] = value self.items.move_to_end(key) if len(self.items) > self.capacity: self.items.popitem(last=False)Example 2 · Tracing an LRU cache
from collections import OrderedDict
class LRUCache: def __init__(self, capacity): self.capacity = capacity self.items = OrderedDict()
def get(self, key): if key not in self.items: return -1 self.items.move_to_end(key) return self.items[key]
def put(self, key, value): self.items[key] = value self.items.move_to_end(key) if len(self.items) > self.capacity: self.items.popitem(last=False)
cache = LRUCache(2)cache.put(1, 10)cache.put(2, 20)print(cache.get(1))cache.put(3, 30)print(cache.get(2))cache.put(4, 40)print(cache.get(1), cache.get(3), cache.get(4))10 -1 -1 30 40
What this code does
- After
put(1),put(2)andget(1), key 2 is the oldest. Putting 3 evicts 2, soget(2)is -1. - Putting 4 evicts 1, leaving 3 and 4. Each line is one constant-time operation.
move_to_end marks a key as the newest in constant time. popitem(last=False) removes the oldest. Both get and put run in O(1) time. The cache uses O(capacity) space.
The same cache built by hand
Interviewers often ask for the cache without OrderedDict. Use a dictionary from key to node, and a doubly linked list that keeps nodes in use order. Unlinking a node needs no search, because the node knows both neighbours.
self.head, self.tail = Node(), Node()self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node): node.prev.next, node.next.prev = node.next, node.prev
def _add_front(self, node): node.next, node.prev = self.head.next, self.head self.head.next.prev = node self.head.next = nodeExample 3 · LRU cache with a map and a linked list
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.map = {} self.head, self.tail = Node(), Node() self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node): node.prev.next, node.next.prev = node.next, node.prev
def _add_front(self, node): node.next, node.prev = self.head.next, self.head self.head.next.prev = node self.head.next = node
def get(self, key): if key not in self.map: return -1 node = self.map[key] self._remove(node) self._add_front(node) return node.value
def put(self, key, value): if key in self.map: self._remove(self.map[key]) node = Node(key, value) self.map[key] = node self._add_front(node) if len(self.map) > self.capacity: oldest = self.tail.prev self._remove(oldest) del self.map[oldest.key]
cache = LRUCache(2)cache.put(1, 10)cache.put(2, 20)print(cache.get(1))cache.put(3, 30)print(cache.get(2))cache.put(4, 40)print(cache.get(1), cache.get(3), cache.get(4))10 -1 -1 30 40
What this code does
- The output matches the
OrderedDictversion, because both follow the same rule. - The dictionary finds the node in one step, and the list moves it to the front without searching.
Example 4 · LRU cache with a plain dict
class DictLRU: def __init__(self, capacity): self.capacity = capacity self.items = {}
def get(self, key): if key not in self.items: return -1 value = self.items.pop(key) self.items[key] = value return value
def put(self, key, value): self.items.pop(key, None) self.items[key] = value if len(self.items) > self.capacity: del self.items[next(iter(self.items))]
cache = DictLRU(2)cache.put(1, 10)cache.put(2, 20)print(cache.get(1))cache.put(3, 30)print(cache.get(2))cache.put(4, 40)print(cache.get(1), cache.get(3), cache.get(4))10 -1 -1 30 40
What this code does
- Since Python 3.7 a dict remembers insertion order. Popping and re-inserting a key moves it to the end, and the first key is the oldest.
- This is short and still O(1) on average. In an interview, say which version you use and why.
The head and tail are dummy nodes, so removing or adding never meets an empty edge case. The node next to the tail is always the least recently used. The full class is in the examples.
Constant-time random pick: swap-delete
Swap-delete removes an item from a list in constant time by overwriting it with the last item and then popping the end. It does not keep order.
A set cannot return a random element, and a list cannot delete from the middle quickly. Combine them: a list of values and a dictionary from value to its position. To delete, move the last value into the freed place.
def remove(self, value): if value not in self.where: return False i = self.where.pop(value) last = self.items.pop() if i < len(self.items): self.items[i] = last self.where[last] = i return TrueExample 5 · Random set with swap-delete
class RandomSet: def __init__(self): self.items = [] self.where = {}
def add(self, value): if value in self.where: return False self.where[value] = len(self.items) self.items.append(value) return True
def remove(self, value): if value not in self.where: return False i = self.where.pop(value) last = self.items.pop() if i < len(self.items): self.items[i] = last self.where[last] = i return True
bag = RandomSet()for v in (10, 20, 30, 40): bag.add(v)print(bag.add(20), bag.remove(10), bag.remove(99))print(bag.items)print(bag.where)False True False
[40, 20, 30]
{20: 1, 30: 2, 40: 0}What this code does
- Adding 20 again returns False. Removing 10 moves the last value, 40, into its place.
- The list is now [40, 20, 30], and the map says 40 lives at position 0.
Popping the last element of a list is O(1), and overwriting one place is O(1), so delete is constant time. The order of the list changes, which is fine because a random pick does not care.
Next step
Check your understanding
11 quick questions