Pattern Guide
LRU & LFU Cache Design
"O(1) get/put with HashMap + doubly linked list. LFU with frequency buckets."
LRU (Least Recently Used) cache evicts the least recently used item when full. Implementation: HashMap (O(1) lookup) + doubly linked list (O(1) move-to-front and evict-tail). LFU (Least Frequently Used) evicts the least frequently accessed item, with LRU as tiebreaker. Implementation: HashMap of key→(value, freq), HashMap of freq→doubly linked list, track minimum frequency.
Problems you can solve with this pattern
3 problems · click any to start solving
class LRUCache {
constructor(capacity) {
this.cap = capacity;
this.map = new Map(); // key → node
// Dummy head and tail
this.head = {key: 0, val: 0, prev: null, next: null};
this.tail = {key: 0, val: 0, prev: null, next: null};
this.head.next = this.tail;
this.tail.prev = this.head;
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_insertFront(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._remove(node);
this._insertFront(node);
return node.val;
}
put(key, value) {
if (this.map.has(key)) this._remove(this.map.get(key));
else if (this.map.size === this.cap) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
const node = {key, val: value, prev: null, next: null};
this._insertFront(node);
this.map.set(key, node);
}
}LRU cache: doubly linked list with dummy head and tail. head.next = most recently used, tail.prev = least recently used. On get: remove node, insert after head. On put: if exists, update and move to front; if full, remove tail.prev; insert new at front. HashMap stores key→node for O(1) access. LFU: additionally maintain freq→DLL map and minFreq to know which frequency to evict from.
class LRUCache {
constructor(capacity) {
this.cap = capacity;
this.map = new Map(); // key → node
// Dummy head and tail
this.head = {key: 0, val: 0, prev: null, next: null};
this.tail = {key: 0, val: 0, prev: null, next: null};
this.head.next = this.tail;
this.tail.prev = this.head;
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_insertFront(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._remove(node);
this._insertFront(node);
return node.val;
}
put(key, value) {
if (this.map.has(key)) this._remove(this.map.get(key));
else if (this.map.size === this.cap) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
const node = {key, val: value, prev: null, next: null};
this._insertFront(node);
this.map.set(key, node);
}
}LFU key insight: JavaScript Map preserves insertion order — use Map as an ordered set (LRU within same frequency). freqMap[f] is a Map where iteration order = insertion order = LRU order.
minFreq tracking: After put(new key), minFreq=1. After get/put(existing key), only increment minFreq if the old frequency's bucket is empty AND was minFreq.