Problem. Design a cache with a fixed capacity:
get(key): return the value if present (and mark it as recently used), else −1;put(key, value): insert or update; if the cache is now over capacity, evict the least recently used key.
Both must run in O(1) average time.
cache = LRU(2)
put(1, 1); put(2, 2)
get(1) → 1 (1 is now the most recent)
put(3, 3) (evicts 2, the least recent)
get(2) → -1
put(4, 4) (evicts 1)
get(1) → -1, get(3) → 3, get(4) → 4
ML context. Caches with LRU eviction sit in front of every expensive call in an ML system: embeddings of repeated texts (lesson 7.8), tokenised prompts, retrieval results for popular queries, model weights or LoRA adapters kept on the GPU while others wait on disk, and prefix (KV) caches in serving engines. The question is always the same: which entry to drop when memory is full, decided in O(1).