The problem
Design an LRU (Least Recently Used) cache with a fixed capacity: get(key) returns the value or −1; put(key, value) adds or updates, and if the cache is full it first throws out the key that was used least recently. Both must be O(1).
Input: capacity 2; put 1 1, put 2 2, get 1, put 3 3, get 2, put 4 4, get 1, get 3, get 4 Output: get 1 → 1, get 2 → −1, get 1 → −1, get 3 → 3, get 4 → 4
Picture it
Picture a tiny hotel with a fixed number of rooms and a queue of guests ordered by when they last did something. Whenever a guest is used (get or put), they move to the “most recent” end. When a new guest arrives and the hotel is full, the guest at the “least recent” end is checked out. A dictionary finds any guest’s room instantly; a doubly linked list keeps the order and lets us move a guest in one step.
How to recognise it
- You are asked to design a data structure, with several operations that must each run in O(1).
- You need two things at once: find any key instantly (a dictionary) and keep keys in order of last use so the oldest can be removed (a list ordered by time).
- An ordinary list can keep the order, but moving a key from the middle to the end costs O(n). A doubly linked list (each node links to both neighbours) can unhook any node in O(1) if you already hold a reference to it, and the dictionary gives you that reference.
- "Least recently used", "evict the oldest", "move to front when touched" all point to hash map + doubly linked list. In Python,
collections.OrderedDictis exactly that pair.
Start with brute force
Keep the values in a dictionary and the keys in a Python list ordered from oldest to newest. On every use, remove the key from the list and append it again.
class LRUCacheBrute:
def __init__(self, capacity):
self.cap, self.data, self.order = capacity, {}, [] # order: oldest first
def get(self, key):
if key not in self.data:
return -1
self.order.remove(key)
self.order.append(key)
return self.data[key]
def put(self, key, value):
if key in self.data:
self.order.remove(key)
elif len(self.data) == self.cap:
del self.data[self.order.pop(0)]
self.data[key] = value
self.order.append(key)
order.remove(key) searches the list and shifts everything after it, and pop(0) shifts the whole list, so each operation is O(c) for capacity c. LeetCode allows c = 3,000 and 2 × 10^5 calls: up to about 6 × 10^8 steps, and it breaks the O(1) requirement.
From brute force to the idea
- Find the waste. The dictionary already finds a key in O(1). The slow part is finding the same key again inside the order list.
- Link the order. Store the order as a doubly linked list and let the dictionary point at each key's node. Unhooking a node and re-attaching it at the "newest" end is a few pointer changes.
- Use the ready-made version.
OrderedDictkeeps its keys in insertion order using exactly this design.move_to_end(key)makes a key the newest in O(1), andpopitem(last=False)removes the oldest in O(1). - get: if the key is missing return −1; otherwise move it to the end (it was just used) and return its value.
- put: store the value and move the key to the end. If that pushed the size past the capacity, evict the oldest. Updating an existing key never grows the cache, so it never evicts.
This is the key idea: a dictionary for finding, a doubly linked list for ordering, kept in step on every operation.
The key idea
Hash map for O(1) lookup + doubly linked list for O(1) reordering and eviction.
Python solution
class LRUCache:
def __init__(self, capacity):
self.cap, self.data = capacity, OrderedDict() # oldest first
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key) # just used: now newest
return self.data[key]
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.cap:
self.data.popitem(last=False) # evict the oldestLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import OrderedDict
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(c) per call: list.remove and pop(0) scan and shift the order list | O(c): the dictionary and the list |
OrderedDict (shown code) | O(1) per call: dictionary lookup, move_to_end and popitem(last=False) are all constant time | O(c): one entry per cached key |
Edge cases
- Capacity 1: every put of a new key evicts the previous one.
- Updating an existing key (
put(1, 10)when 1 is cached): changes the value, makes 1 the newest, and evicts nothing. - get of a missing key: returns −1 and changes nothing.
- Stored value 0:
getreturns 0, because the code checkskey not in self.data, not the truthiness of the value. - get counts as a use: in the LeetCode example (capacity 2: put 1, put 2, get 1, put 3), key 2 is evicted, not key 1.
- Imports: the shown code needs
from collections import OrderedDict.
Common mistakes
- Forgetting
move_to_endinget, so reads do not refresh a key and the wrong one is evicted. - Evicting before inserting, even when the key already exists. That throws out a key needlessly when you are only updating.
- Using
popitem()withoutlast=False, which removes the newest key instead of the oldest. - Building the order with timestamps and scanning for the smallest on eviction: O(c) again.
Interviewers often ask you to build the same cache without OrderedDict. Write it with a plain dictionary and your own doubly linked list. Describe your approach, then write it if you like.
Compare with our answer
Use two sentinel nodes (dummy nodes that are never removed), old and new, so every real node always has neighbours on both sides and no None checks are needed. The dictionary maps key → node. Each node stores its key too, so the evicted node can be deleted from the dictionary.
class DNode:
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCacheDLL:
def __init__(self, capacity):
self.cap, self.map = capacity, {}
self.old, self.new = DNode(), DNode() # sentinels at both ends
self.old.next, self.new.prev = self.new, self.old
def _remove(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _add_newest(self, node):
node.prev, node.next = self.new.prev, self.new
self.new.prev.next = node
self.new.prev = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_newest(node)
return node.val
def put(self, key, value):
if key in self.map:
self._remove(self.map[key])
node = DNode(key, value)
self.map[key] = node
self._add_newest(node)
if len(self.map) > self.cap:
lru = self.old.next
self._remove(lru)
del self.map[lru.key]
Every operation is O(1); space O(c).
A strong answer mentions: sentinel nodes, storing the key inside each node for eviction, and updating both the dictionary and the list on every put and get.
1. A server caches up to 10,000 thumbnails. When full, it must drop the one not viewed for the longest time, with O(1) lookups and updates. Which design fits best?
The dictionary finds a node in O(1) and the doubly linked list moves or removes it in O(1). A heap needs O(log n) per update, and scanning or shifting a list is O(n).
2. Why is move_to_end O(1) in the shown code rather than O(c)?
OrderedDict pairs its hash table with a doubly linked list of keys, so a key can be unhooked and attached at the end without shifting anything. Keys are kept in insertion order, not sorted order.
3. A learner deletes self.data.move_to_end(key) from get. With capacity 2, the calls are put 1, put 2, get 1, put 3, get 2. What changes?
Without the move, reading key 1 does not refresh it, so key 1 is still the oldest when put 3 needs room. Key 1 is evicted and key 2 survives.
Score 60% or more and the lesson is marked complete.