ZERO / HERO
A desk with limited space

Designing an LRU Cache

The analogy

Your desk holds five books. Every time you use one you put it back on the left. When a sixth arrives, you get rid of whatever is furthest right — the one you have not touched in the longest time. The trick is doing both the "find a book instantly" part and the "know which is oldest" part at the same time.

Visualizer

Promote and evict

step 1 / 11
head→null

An LRU cache of capacity 4. The list is ordered most-recently-used first; a hash map (not drawn) points straight at each node.empty — capacity 4

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()

    def get(self, k):
        if k not in self.d:
            return -1
        self.d.move_to_end(k)          # promote — O(1)
        return self.d[k]

    def put(self, k, v):
        if k in self.d:
            self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap:
            self.d.popitem(last=False)  # evict oldest

# hash map = O(1) find, linked list = O(1) reorder
from functools import lru_cache        # the real one
Check yourself

Why must the recency list be DOUBLY linked?