Practice: LRU Cache
Forget the oldest.
A cache keeps recent answers close by, so you don't have to fetch them again. But it has limited room. When it's full, an LRU cache forgets the item that was used least recently. Every get and every put must be O of one.

- A cache has limited room
- Forget the least recently used
- Everything in O(1)
An ordered dictionary
Python's ordered dict remembers the order of its keys, and can move a key to the end in O of one. So the end is the most recent, and the front is the oldest. Get moves a key to the end. Put adds or updates a key, and if we're over capacity, pops the oldest from the front. Run it. B was the least recently used, so B was forgotten.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.data, self.capacity = OrderedDict(), capacity
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(list(cache.data))['a', 'c']
Under the hood
In an interview, you may be asked to build it without ordered dict. The classic answer is a dictionary plus a doubly linked list. The dictionary finds a node in O of one. The linked list moves it, or removes the oldest, in O of one. Together, they give every operation in constant time.
| key | value |
|---|---|
| Dictionary | key to node, O(1) lookup |
| Doubly linked list | order of use |
| Front | least recent, evict it |
| Back | most recent |
Summary
An LRU cache is a dictionary plus an ordering. Ordered dict gives you both, with move to end and pop item. Next, a stack that always knows its minimum.
Key takeaways- OrderedDict
- move_to_end on use
- popitem(last=False) to evict