LRU Cache

⏱️ ~3-minute bite · solve the sandbox to master

0%lesson

🧒

5-Year-Old Metaphor

— The physical, real-world picture. No jargon.

🅿️ A parking lot with 3 spots. The last car parked is closest to the exit. When full, the car furthest from the exit gets towed.

The mental model

Park a new car — it goes to spot #1 (MRU). Everyone else shifts back one. If the lot is full, the car in the last spot (LRU) gets towed first.
Retrieve your car (GET) — it gets re-parked at spot #1 (MRU). You used it, so it's "recently used" again. Everyone else shifts back.
Car not found (MISS) — you ask for a car that was towed (or never parked). You get back nothing (−1). The lot is unchanged.

Why this works in real systems

Most programs have temporal locality: if you accessed a piece of data recently, you are likely to access it again soon. LRU exploits this by keeping recently-used items in fast storage (cache) and evicting the ones that haven't been touched in a while.

put(1,10) → [{1:10}] MRU→LRU: [1]

put(2,20) → [{1:10, 2:20}] MRU→LRU: [2, 1]

put(3,30) → [{...}] MRU→LRU: [3, 2, 1]

get(1) → 10 (HIT) MRU→LRU: [1, 3, 2] ← 1 moves front

put(4,40) → evicts 2 MRU→LRU: [4, 1, 3] ← 2 was LRU

Where you encounter LRU in the wild

CPU L1/L2/L3 cache lines (hardware-level)
Browser page cache (Cache-Control: max-age)
Redis eviction policy (maxmemory-policy allkeys-lru)
Database buffer pool (PostgreSQL shared_buffers)
CDN edge nodes — evict cold content to serve hot content faster

🎛️

Interactive Sandbox

— Move something, see it react instantly.

How to use: pick a pattern below, then step through operations one by one. Green = MRU slot, amber = LRU slot (eviction candidate). Explore all 5 patterns to master.

Cache (capacity=3)

1→node1

MRU

key

val=10

MRU

empty

LRU

Last op:PUT(1,10)→inserted

Operations

put(1,10)insertedInserted key 1=10 at MRU position.

put(2,20)inserted

put(3,30)inserted

get(1)→10 (HIT)

get(2)→20 (HIT)

Pattern insight

The cache is a live-ordered list. Reads are not passive.

⚠️ Gotcha: Every GET moves the item to MRU — order always reflects recency.

1 / 5

🎯

Challenge

Explore all 5 patterns to understand every LRU behavior. (1/5 explored)

Try it

🎯

Why Should I Care?

— The exact interview question + the bug it kills.

Q: Why does doubly-linked list + hashmap give O(1)?

A hashmap alone gives O(1) lookup, but moving a node to the front of a singly-linked list requires traversal — O(n). A doubly-linked list lets you unlink a node in O(1) (you have the prev pointer), then insert it at the head in O(1). The hashmap stores key → node, so you jump directly to the node without any traversal.

1	// The "aha": both get and put are O(1)
2	// get(key):
3	// 1. hashmap.get(key) → O(1) → node
4	// 2. unlink(node) → O(1) → uses node.prev + node.next
5	// 3. insertAtHead(node)→ O(1) → update head/sentinel pointers
6	//
7	// put(key, val):
8	// Same as get, plus:
9	// 4. if full: remove tail → O(1) (tail sentinel gives direct access)
10	// hashmap.delete(tail.key) → O(1)

Q: What is the difference between LRU and LFU?

LRU (Least Recently Used) evicts the item that was accessed furthest back in time, regardless of how many times it was accessed.

LFU (Least Frequently Used) evicts the item with the lowest access count, regardless of when it was last accessed.

Sequence: put(A), get(A)×10, put(B), put(C) → capacity full → put(D)

LRU evicts C (least recently used: C was inserted last but never touched)

LFU evicts B or C (both accessed 0 times — tie broken by recency)

LFU is better when some keys are permanently hot (e.g., a homepage). LRU is better for sequential scans where you want to avoid cache pollution from one-time-reads.

Q: When is LRU a bad cache policy?

Sequential scans (cache thrashing): a full-table scan reads every row once, evicting genuinely hot rows. Postgres uses a "clock sweep" to detect scan patterns and avoid this.
Periodic batch jobs: a nightly job that touches all keys resets the LRU order, making the cache useless for the daytime workload that follows.
Skewed frequency: if 10% of keys are accessed 99% of the time, LFU outperforms LRU because those hot keys never get evicted no matter how recently others were touched.

🐛 Common bug: not updating order on cache hit

The most common LRU implementation mistake: implementing get as a pure read without moving the node to the front.

1	// ❌ WRONG — returns value but silently corrupts eviction order
2	get(key) {
3	return this.map.has(key) ? this.map.get(key).val : -1;
4	// ^^ missing: move node to head of the DLL
5	}
6
7	// ✅ CORRECT — O(1) lookup AND correct order maintenance
8	get(key) {
9	if (!this.map.has(key)) return -1;
10	const node = this.map.get(key)!;
11	this.moveToHead(node); // ← the part most people forget
12	return node.val;
13	}

This bug is subtle: the cache still returns correct values. It only fails eviction correctness, which is invisible until you stress-test with a sequence that should keep a specific key alive.

🔬

The Deep Dive

— Spec refs, engine internals, the minutiae.

Full TypeScript implementation

1	class DLLNode {
2	key: number; val: number;
3	prev: DLLNode \| null = null;
4	next: DLLNode \| null = null;
5	constructor(k: number, v: number) { this.key = k; this.val = v; }
6	}
7
8	class LRUCache {
9	private cap: number;
10	private map = new Map<number, DLLNode>();
11	// Sentinels: head.next = MRU, tail.prev = LRU
12	private head = new DLLNode(0, 0);
13	private tail = new DLLNode(0, 0);
14
15	constructor(capacity: number) {
16	this.cap = capacity;
17	this.head.next = this.tail;
18	this.tail.prev = this.head;
19	}
20
21	get(key: number): number {
22	if (!this.map.has(key)) return -1;
23	const node = this.map.get(key)!;
24	this.remove(node);
25	this.insertFront(node);
26	return node.val;
27	}
28
29	put(key: number, val: number): void {
30	if (this.map.has(key)) this.remove(this.map.get(key)!);
31	const node = new DLLNode(key, val);
32	this.insertFront(node);
33	this.map.set(key, node);
34	if (this.map.size > this.cap) {
35	const lru = this.tail.prev!;
36	this.remove(lru);
37	this.map.delete(lru.key);
38	}
39	}
40
41	private remove(node: DLLNode) {
42	node.prev!.next = node.next;
43	node.next!.prev = node.prev;
44	}
45
46	private insertFront(node: DLLNode) {
47	node.next = this.head.next;
48	node.prev = this.head;
49	this.head.next!.prev = node;
50	this.head.next = node;
51	}
52	}
53	// Time: O(1) get + O(1) put · Space: O(capacity)

LFU implementation (frequency buckets)

LFU requires tracking frequency per key. The trick is maintaining a min-frequency pointer and a Map<freq, DoublyLinkedList>. On access, move the node from freq bucket N to N+1. On eviction, remove the LRU node from the min-freq bucket. Still O(1) amortized.

LFU is harder to implement correctly (off-by-one on min-freq pointer) and is less commonly asked at interviews than LRU, but appears at senior/staff level.

Cache-oblivious algorithms

Cache-oblivious algorithms are designed to be optimal without knowing the cache size. They exploit spatial/temporal locality naturally — e.g., recursive merge sort has better cache behavior than iterative merge sort because the recursion naturally fits sub-problems into L1/L2 cache. LRU is the typical eviction policy assumed for cache-oblivious analysis.

Redis LRU/LFU modes

Redis does not maintain a true LRU list (it would be too expensive for millions of keys). Instead it uses probabilistic LRU: on eviction, it samples 5 random keys and evicts the one with the oldest access time. This is maxmemory-policy allkeys-lru.

Redis 4.0+ added LFU mode (allkeys-lfu). It approximates frequency using a Morris counter (logarithmic increment probability) to fit frequency into 8 bits per key.

Browser cache (HTTP)

Cache-Control: max-age=3600 — fresh for 1 hour, then stale
stale-while-revalidate=60 — serve stale for 60s while revalidating in background (async LRU-like pattern)
stale-if-error=86400 — serve stale for 1 day if origin is down
Browser disk cache uses a variant of LRU/LFU hybrid; Chrome uses a scored eviction that weights recency, frequency, and resource size.

Related patterns

Doubly Linked List — the DLL pattern alone: O(1) insert/remove at any position
HashMap + DLL — the structural heart of LRU; reusable for ordered-map needs
Monotonic Deque — sliding window max/min in O(1); similar "order maintenance" idea
Skip List — probabilistic sorted structure; Redis sorted sets use this

🎤

Interview Questions

— Real questions from real interviews — with answers.

HashMap gives O(1) lookup; doubly linked list gives O(1) reordering without scanning.

LRU evicts the least recently used key; LFU evicts the least frequently used — and breaks ties by recency.

Wrap all get/put in a mutex; or use a concurrent hashmap with lock striping to reduce contention.

Maintain a secondary min-stack alongside the LRU — each node stores the current minimum at insertion time.

🎮

Memory Game

— Quick quiz — lock the concept in long-term memory.

1/4

What is clock/CLOCK cache replacement algorithm, and how does it relate to LRU?