12. LRU Cache for the Embedding-Lookup Serving Layer

Problem

A lab's retrieval-augmented serving layer caches recently-used document embeddings in memory so repeat lookups for popular documents skip a round trip to the vector store. Memory is bounded, so once the cache is full, adding a new embedding must evict the least-recently-used entry — the one least likely to be requested again soon.

Implement LRUCache with fixed capacity. Both get and put must run in O(1) time since this sits directly in the request hot path; a missing key returns -1 from get.

Source: src/12_lru_serving_cache.py

class LRUCache:
    def __init__(self, capacity: int): ...
    def get(self, key: str) -> object: ...
    def put(self, key: str, value: object) -> None: ...

>>> cache = LRUCache(2)
>>> cache.put("a", 1)
>>> cache.put("b", 2)
>>> cache.get("a")
1
>>> cache.put("c", 3)
>>> cache.get("b")
-1

Step-by-Step Approach

1. Recognize that O(1) get/put with LRU eviction needs two structures working together: a hash map for O(1) key lookup, and an ordered structure for O(1) "move to most-recent" and O(1) "evict least-recent."
2. Python's collections.OrderedDict gives both for free: it's a hash map that also remembers insertion/access order, with O(1) move_to_end and O(1) popitem(last=False) to pop the oldest entry.
3. On get(key): if the key is absent, return -1. Otherwise, this access counts as a "use" — move the key to the most-recently-used end before returning its value.
4. On put(key, value): if the key already exists, move it to the most-recently-used end first (a re-put counts as a use too), then (re)assign its value.
5. After inserting, check len(store) > capacity; if so, evict the entry sitting at the least-recently-used end, since it hasn't been touched in the longest time.
6. Keep eviction as its own step after insertion (not before) so a re-put of an existing key never triggers a spurious eviction of itself.

The key insight is that "least recently used" is really just "position in an order that gets touched on every access" — once you see that, the whole problem reduces to picking a data structure that supports O(1) reordering, and OrderedDict (or a hand-rolled hash map + doubly linked list) is exactly that.

Reference solution

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # OrderedDict already tracks insertion/access order -- move_to_end and
        # popitem(last=False) give O(1) "touch" and O(1) "evict oldest"
        self._store: OrderedDict[str, object] = OrderedDict()

    def get(self, key: str):
        if key not in self._store:
            return -1
        # a read counts as a use: move this key to the most-recently-used end
        self._store.move_to_end(key, last=True)
        return self._store[key]

    def put(self, key: str, value) -> None:
        if key in self._store:
            self._store.move_to_end(key, last=True)
        self._store[key] = value
        if len(self._store) > self.capacity:
            # oldest entry sits at the front (least-recently-used) -- evict it
            self._store.popitem(last=False)

Key Functions & Tricks

• collections.OrderedDict — a hash map that also maintains insertion order, avoiding a hand-rolled doubly linked list.
• move_to_end(key, last=True) — O(1) reordering that marks a key as most-recently-used on both reads and writes.
• popitem(last=False) — O(1) removal of the oldest (least-recently-used) entry when the cache is over capacity.
• checking eviction after insertion — guarantees a re-put of an existing key never causes it to evict itself.
• key not in self._store — an explicit membership check before get keeps the "missing key" path from touching the ordering at all.

How to Recognize This Pattern