LRU cache

A buffer pool, a CDN edge, an embedding cache in front of a model API. Each one has a fixed amount of room, and when it fills up it throws out whatever was used longest ago.

Write a class LRUCache:

• LRUCache(capacity) makes an empty cache that holds at most capacity keys.
• get(key) returns the stored value, or None if the key isn’t there. A hit makes the key the most recently used.
• put(key, value) stores the value. If the key already exists, update it and make it the most recently used. If adding a new key goes over capacity, evict the least recently used key first.
• len(cache) returns the number of keys stored (implement __len__).
• A capacity of 0 stores nothing.

Both get and put should be O(1).

>>> c = LRUCache(2)
>>> c.put("a", 1); c.put("b", 2)
>>> c.get("a")
1
>>> c.put("c", 3)      # evicts "b", the least recently used
>>> c.get("b") is None
True

Approach

Keep keys in use order: oldest at the front, newest at the back. OrderedDict gives you a hash map and that order in one structure.

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self._data = OrderedDict()

    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)
        while len(self._data) > self.capacity:
            self._data.popitem(last=False)

    def __len__(self):
        return len(self._data)

Inside, OrderedDict is a hash map whose entries also sit on a doubly linked list. Moving an entry to the end is a few pointer swaps. In a language without it, you build the same pair yourself.

Complexity

get and put are O(1). Space is O(capacity).

Why this matters

A database buffer pool is an LRU over disk pages. Many real ones use a variant like CLOCK or LRU-K, because one big table scan would otherwise flush every hot page. An embedding cache keyed by a content hash saves a model call on every hit. In both cases the eviction policy decides your hit rate, and the hit rate decides your latency and your bill.