39. LRU Semantic Cache

Problem

Semantic caching matches incoming queries by embedding similarity rather than exact string match, and embedding generation is flagged as the most cacheable layer in a RAG pipeline like Fin's. Once similarity-matched entries exceed available memory, the cache needs a capacity-management policy — evict something to make room for the next entry.

A plain dict gives O(1) lookup but no notion of "recency" at all — there's no cheap way to find the least-recently-used entry without scanning every key. A plain list or array can track order, but moving an accessed element to the front (or back) means shifting every element in between, which is O(n) per access. Neither structure alone gets you O(1) get, O(1) put, and O(1) eviction-by-recency.

The fix is to combine them: a hashmap gives O(1) lookup from key straight to a node, and a doubly linked list gives O(1) reordering of that node once you already have a reference to it — no traversal required. Implement LRUCache from scratch with this combination (not a wrapper around collections.OrderedDict) so that both get and put run in true O(1) time.

Source: src/39_lru_semantic_cache.py

class LRUCache:
    def __init__(self, capacity: int): ...
    def get(self, key) -> int: ...          # returns -1 if key not present
    def put(self, key, value) -> None: ...  # evicts LRU entry if over capacity

>>> c = LRUCache(2)
>>> c.put(1, 1)
>>> c.put(2, 2)
>>> c.get(1)
1
>>> c.put(3, 3)   # capacity full -> evicts key 2 (the LRU entry)
>>> c.get(2)
-1
>>> c.put(4, 4)   # evicts key 1 (now the LRU entry)
>>> c.get(1)
-1
>>> c.get(3)
3
>>> c.get(4)
4

Step-by-Step Approach

1. Set up two sentinel nodes, head and tail, and link them to each other. They never hold real data — they exist purely so every real node always has a non-null prev and next, removing every boundary null-check from the list operations.
2. Keep a hashmap cache from key to the _Node holding that key's value. This is the only way anything ever finds a node — the list itself is never searched by key.
3. Write _remove(node): splice a node out of wherever it currently sits by pointing its neighbors at each other. Works identically whether the node is in the middle, right after head, or right before tail.
4. Write _add_to_front(node): splice a node in immediately after head, i.e. the most-recently-used position.
5. get(key): if the key isn't in cache, return -1. Otherwise look the node up in O(1), move it to the front via _remove + _add_to_front (an access counts as a "use"), and return its value.
6. put(key, value): if the key already exists, update the existing node's value and move it to the front. Otherwise, check whether the cache is already at capacity before inserting — if so, evict tail.prev (the true least-recently-used node) from both the list and the hashmap, then create and insert the new node at the front.
7. Trace the canonical example: capacity 2, put(1,1), put(2,2), get(1) (moves 1 to front), put(3,3) (evicts 2, the LRU), get(2) → -1, put(4,4) (evicts 1, now the LRU), get(1) → -1, get(3) → 3, get(4) → 4.

The key insight is that node identity, not key, is what the linked list manipulates — once you have a node reference, splicing it anywhere is O(1) regardless of list size. The hashmap's only job is to jump from a key straight to its node in O(1), skipping any list traversal entirely; the two structures each cover the other's weak point.

Reference solution

class _Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    # hashmap (key -> node) for O(1) lookup + doubly linked list with sentinel
    # head/tail for O(1) reorder; get() and put() are both O(1) time, O(n) space
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}          # key -> _Node
        self.head = _Node()      # sentinel; head.next = most recently used
        self.tail = _Node()      # sentinel; tail.prev = least recently used
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        # unlink node from its current position, O(1) given the node reference
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        # splice node in right after head, i.e. the most-recently-used slot
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # a read counts as a use too, so move the node to the front
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.cache) >= self.capacity:
            # evict the least-recently-used entry, which sits right before tail
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
        node = _Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)

Key Functions & Tricks

• Sentinel head/tail nodes — dummy endpoints that always exist, so _remove/_add_to_front never need a null-check for an empty or single-element list.
• _remove(node) — pointer surgery: node.prev.next = node.next then node.next.prev = node.prev unlinks a node in O(1).
• _add_to_front(node) — pointer surgery: splice node in between head and head.next, four pointer writes, O(1).
• get() also calls _remove + _add_to_front — reading an entry counts as "using" it, so it must move to the most-recently-used end too, not just put().
• Eviction check before insertion — if len(self.cache) >= self.capacity runs before the new node is created, so capacity is never briefly exceeded.
• self.tail.prev — always the true least-recently-used node, O(1) to find via the sentinel.
• self.cache = {} — the hashmap only ever stores key -> node; the list is what tracks order, never the hashmap.

How to Recognize This Pattern