AI Hints
Home›DSA in Python Tutorial›Designing Data Structures
DSA in Python · Lesson 112 of 132

Practice: LRU Cache

Forget the oldest.

⏱ 2 min read▶ Video at 2:13:44🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: LRU Cache
From the video: Practice: LRU Cache
  • 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.

lru.pypython
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))
Output
['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.

keyvalue
Dictionarykey to node, O(1) lookup
Doubly linked listorder of use
Frontleast recent, evict it
Backmost 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
Next up: Practice: Min Stack — the minimum in O(1)