VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 07: Linked lists and caches

Lesson 7.7 of 8 in this module Unrolled Pro

LRU Cache

A fixed-capacity cache with O(1) get and put that evicts the least recently used key. From a list kept in recency order (O(n) per operation), to a dict with last-used timestamps (O(1) get, O(n) eviction), to a hash map pointing into a doubly linked list with sentinel nodes (O(1) everything), and Python's OrderedDict doing the same. Then least-frequently-used eviction in O(1), entries that expire after a TTL, thread safety, and functools.lru_cache for pure functions.

about 15 min 5 Python examples 2 quick checks

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.

text
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).


1. Step 1: Clarify

That's the preview. Modules 00–01 are free; this lesson is part of Unrolled Pro.
Staff AI & Pro Tier Lesson

Unlock "LRU Cache"

The foundations are free forever. Unrolled Pro unlocks the complete lesson, production architectures, and 55 battle-tested ML system design case studies.

Everything included with Pro:
All 234+ Deep-Dive Lessons across transformer internals, inference, RAG & agents
55 Staff-Level ML & System Design Case Studies with mathematical capacity estimates
AI Engineer Sheet & Exercises with worked solutions, self-checks, and code
100 Landmark Research Papers guided walkthroughs & progress tracking
14-Day Money-Back Guarantee — 100% full refund if you aren't satisfied
View Plans & Unlock All Lessons

From ₹167/mo (~$2/mo) · Cancel anytime · Instant activation

100% Risk-Free: 14-day no-questions-asked money-back guarantee