LRU Cache
An LRU (Least Recently Used) cache evicts the item that has not been accessed for the longest time when the cache is full. This policy approximates "keep what you are likely to need again" — it is used in CPU caches, database buffer pools, browser page caches, and key-value stores like Redis.
The interview requirement: both get and put operations must run in O(1) time.
Why O(1) Is Hard
get(key): look up a value — easy with a HashMap
put(key, value): insert and possibly evict the LRU item — eviction needs "which item is oldest"
Every access (get or put) must move the accessed item to the "most recently used" position
A plain array gives O(1) eviction but O(n) access; a balanced BST gives O(log n) for both
The O(1) trick: combine a HashMap with a Doubly Linked List
The Data Structure
The doubly linked list maintains usage order — head = most recently used, tail = least recently used. The HashMap maps each key to its node in the list.
- get(key): find node in O(1) via map, move it to the front (head), return value.
- put(key, value): if key exists, update and move to front. If new: insert at front, evict tail if over capacity.
Both operations are O(1) because:
- HashMap gives O(1) node lookup.
- Removing and inserting a node in a doubly linked list is O(1) given a pointer.
Full Implementation
class DLinkedNode {
key: number;
val: number;
prev: DLinkedNode | null = null;
next: DLinkedNode | null = null;
constructor(key = 0, val = 0) {
this.key = key;
this.val = val;
}
}
class LRUCache {
private capacity: number;
private map: Map<number, DLinkedNode>;
private head: DLinkedNode; // dummy head (most recent side)
private tail: DLinkedNode; // dummy tail (least recent side)
constructor(capacity: number) {
this.capacity = capacity;
this.map = new Map();
// Dummy sentinels eliminate edge-case checks for empty list
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
this.head.next = this.tail;
this.tail.prev = this.head;
}
private addToFront(node: DLinkedNode): void {
node.prev = this.head;
node.next = this.head.next!;
this.head.next!.prev = node;
this.head.next = node;
}
private removeNode(node: DLinkedNode): void {
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
private removeLRU(): DLinkedNode {
const lru = this.tail.prev!;
this.removeNode(lru);
return lru;
}
get(key: number): number {
const node = this.map.get(key);
if (!node) return -1;
// Move to front: this is now the most recently used
this.removeNode(node);
this.addToFront(node);
return node.val;
}
put(key: number, value: number): void {
const existing = this.map.get(key);
if (existing) {
existing.val = value;
this.removeNode(existing);
this.addToFront(existing);
return;
}
const node = new DLinkedNode(key, value);
this.map.set(key, node);
this.addToFront(node);
if (this.map.size > this.capacity) {
const evicted = this.removeLRU();
this.map.delete(evicted.key);
}
}
}Walkthrough
const cache = new LRUCache(2);
cache.put(1, 1); // cache: {1=1}
cache.put(2, 2); // cache: {2=2, 1=1} (2 is more recent)
cache.get(1); // returns 1; cache: {1=1, 2=2} (1 moved to front)
cache.put(3, 3); // evicts key 2 (LRU); cache: {3=3, 1=1}
cache.get(2); // returns -1 (evicted)
cache.put(4, 4); // evicts key 1 (LRU); cache: {4=4, 3=3}
cache.get(1); // returns -1 (evicted)
cache.get(3); // returns 3
cache.get(4); // returns 4Complexity
Operation | Time | Space |
|---|---|---|
get(key) | O(1) | — |
put(key, value) | O(1) | — |
Total space | — | O(capacity) |
LFU Cache — Brief Overview
LFU (Least Frequently Used) evicts the item accessed the fewest number of times. When two items have the same frequency, it falls back to LRU order (evicts the older one).
O(1) LFU requires three data structures:
keyMap: key → {value, frequency}
freqMap: frequency → doubly linked list of keys at that frequency (most recent first)
minFreq: tracks the current minimum frequency for O(1) eviction
// O(1) LFU Cache sketch
class LFUCache {
private capacity: number;
private minFreq: number = 0;
private keyMap = new Map<number, { val: number; freq: number }>();
private freqMap = new Map<number, Map<number, number>>(); // freq → LinkedHashMap(key→order)
constructor(capacity: number) {
this.capacity = capacity;
}
// Full implementation follows the same pattern as LRU but tracks frequency per key
// and updates minFreq after each access
get(key: number): number {
const entry = this.keyMap.get(key);
if (!entry) return -1;
this.incrementFreq(key, entry);
return entry.val;
}
put(key: number, value: number): void {
if (this.capacity <= 0) return;
const entry = this.keyMap.get(key);
if (entry) {
entry.val = value;
this.incrementFreq(key, entry);
return;
}
if (this.keyMap.size >= this.capacity) this.evict();
this.keyMap.set(key, { val: value, freq: 1 });
if (!this.freqMap.has(1)) this.freqMap.set(1, new Map());
this.freqMap.get(1)!.set(key, Date.now());
this.minFreq = 1;
}
private incrementFreq(key: number, entry: { val: number; freq: number }): void {
const oldFreq = entry.freq;
this.freqMap.get(oldFreq)!.delete(key);
if (this.freqMap.get(oldFreq)!.size === 0) {
this.freqMap.delete(oldFreq);
if (this.minFreq === oldFreq) this.minFreq++;
}
entry.freq++;
if (!this.freqMap.has(entry.freq)) this.freqMap.set(entry.freq, new Map());
this.freqMap.get(entry.freq)!.set(key, Date.now());
}
private evict(): void {
const minList = this.freqMap.get(this.minFreq)!;
const keyToEvict = minList.keys().next().value;
minList.delete(keyToEvict);
this.keyMap.delete(keyToEvict);
}
}Real-World Use Cases
System | Cache type | Rationale |
|---|---|---|
CPU L1/L2 cache | Hardware LRU approximation | Recently used instructions are likely needed again |
Redis | LRU / LFU (configurable) | Keep hot keys in memory, evict cold ones |
Browser page cache | LRU | Recently visited pages more likely to be revisited |
Database buffer pool | LRU variant (Clock) | Hot pages stay in RAM; cold pages written to disk |
CDN edge nodes | LRU / LFU hybrid | Serve popular content from edge, less-popular from origin |