Pattern Guide
Design Data Structures
"LRU, LFU, iterators — combine primitives for O(1) every operation."
Design problems ask you to implement a data structure with specific O(1) or O(log n) operations. The pattern: identify which primitive structures (HashMap, DLL, heap, set) give you each operation you need, then combine them. LRU, LFU, Randomized Set, Twitter, and Iterator patterns all follow this blueprint.
20 min readmiscellaneous problems →
Problems you can solve with this pattern
4 problems · click any to start solving
LRU Cache — O(1) get and put
// Doubly linked list + HashMap
// Head (dummy) = Most Recently Used end
// Tail (dummy) = Least Recently Used end
class Node { constructor(k,v){this.key=k;this.val=v;this.prev=this.next=null;} }
class LRUCache {
constructor(cap) {
this.cap=cap; this.map=new Map();
this.head=new Node(0,0); this.tail=new Node(0,0);
this.head.next=this.tail; this.tail.prev=this.head;
}
_remove(n){n.prev.next=n.next;n.next.prev=n.prev;}
_addFront(n){n.next=this.head.next;n.prev=this.head;this.head.next.prev=n;this.head.next=n;}
get(k){
if(!this.map.has(k)) return -1;
const n=this.map.get(k);
this._remove(n); this._addFront(n);
return n.val;
}
put(k,v){
if(this.map.has(k)){const n=this.map.get(k);n.val=v;this._remove(n);this._addFront(n);return;}
const n=new Node(k,v); this.map.set(k,n); this._addFront(n);
if(this.map.size>this.cap){const lru=this.tail.prev;this._remove(lru);this.map.delete(lru.key);}
}
}Design problems have a consistent pattern: you need multiple O(1) operations that no single structure supports alone. The solution is always to combine structures, each handling what the others can't. HashMap gives O(1) lookup. Doubly linked list gives O(1) insert/delete at any position. Array gives O(1) random access. Know what each primitive does in O(1) and you can compose anything.
| Need O(1)... | Use | Why |
|---|---|---|
| Lookup by key | HashMap | O(1) average access by key |
| Insert/delete anywhere | Doubly Linked List | O(1) with pointer to node |
| Random access by index | Array | O(1) index access |
| Min/max of sliding window | Monotonic Deque | Front always = current extreme |
| Min/max with insertions | Heap | O(log n) insert, O(1) peek |
| Delete arbitrary + random | Array + HashMap | Swap-with-last trick for delete |
| Order by recency | DLL + HashMap (LRU) | Move-to-front in O(1) via pointers |
| Order by frequency+recency | Multi-DLL + 2 HashMaps (LFU) | Per-freq buckets |
LRU Cache — HashMap + DLL
LRU Cache — O(1) get and put
// Doubly linked list + HashMap
// Head (dummy) = Most Recently Used end
// Tail (dummy) = Least Recently Used end
class Node { constructor(k,v){this.key=k;this.val=v;this.prev=this.next=null;} }
class LRUCache {
constructor(cap) {
this.cap=cap; this.map=new Map();
this.head=new Node(0,0); this.tail=new Node(0,0);
this.head.next=this.tail; this.tail.prev=this.head;
}
_remove(n){n.prev.next=n.next;n.next.prev=n.prev;}
_addFront(n){n.next=this.head.next;n.prev=this.head;this.head.next.prev=n;this.head.next=n;}
get(k){
if(!this.map.has(k)) return -1;
const n=this.map.get(k);
this._remove(n); this._addFront(n);
return n.val;
}
put(k,v){
if(this.map.has(k)){const n=this.map.get(k);n.val=v;this._remove(n);this._addFront(n);return;}
const n=new Node(k,v); this.map.set(k,n); this._addFront(n);
if(this.map.size>this.cap){const lru=this.tail.prev;this._remove(lru);this.map.delete(lru.key);}
}
}LFU Cache — Frequency Buckets
LFU structure: Three maps:
1. keyMap: key → {val, freq} — for O(1) value+frequency lookup
2. freqMap: freq → DoublyLinkedList of keys at that frequency (MRU order)
3. minFreq: track the minimum frequency currently in the cache
On access: increment freq, move key from freqMap[old] to freqMap[new]. On evict: evict LRU from freqMap[minFreq] (tail of that list).
1. keyMap: key → {val, freq} — for O(1) value+frequency lookup
2. freqMap: freq → DoublyLinkedList of keys at that frequency (MRU order)
3. minFreq: track the minimum frequency currently in the cache
On access: increment freq, move key from freqMap[old] to freqMap[new]. On evict: evict LRU from freqMap[minFreq] (tail of that list).
LFU Cache — O(1) all operations
class LFUCache {
constructor(cap) {
this.cap=cap; this.minFreq=0; this.size=0;
this.keyMap=new Map(); // key → {val, freq}
this.freqMap=new Map(); // freq → Set of keys (insertion-ordered)
}
_increment(key) {
const {val,freq}=this.keyMap.get(key);
this.freqMap.get(freq).delete(key);
if(this.freqMap.get(freq).size===0){
this.freqMap.delete(freq);
if(this.minFreq===freq) this.minFreq++;
}
const newFreq=freq+1;
if(!this.freqMap.has(newFreq)) this.freqMap.set(newFreq,new Set());
this.freqMap.get(newFreq).add(key);
this.keyMap.set(key,{val,freq:newFreq});
}
get(key) {
if(!this.keyMap.has(key)) return -1;
this._increment(key);
return this.keyMap.get(key).val;
}
put(key,val) {
if(this.cap===0) return;
if(this.keyMap.has(key)){this.keyMap.get(key).val=val;this._increment(key);return;}
if(this.size===this.cap){
// Evict LRU from minFreq bucket
const evictSet=this.freqMap.get(this.minFreq);
const evictKey=evictSet.keys().next().value;
evictSet.delete(evictKey); if(evictSet.size===0) this.freqMap.delete(this.minFreq);
this.keyMap.delete(evictKey); this.size--;
}
this.keyMap.set(key,{val,freq:1});
if(!this.freqMap.has(1)) this.freqMap.set(1,new Set());
this.freqMap.get(1).add(key);
this.minFreq=1; this.size++;
}
}Design problem blueprint:
1. List all operations and their required complexity
2. For each operation, identify what primitive gives O(1) or O(log n)
3. Combine: usually HashMap for lookup + another structure for ordering
4. Handle the edge cases: empty structure, single element, capacity exactly full
Common combinations:
- O(1) lookup + O(1) recency order → HashMap + DLL (LRU)
- O(1) lookup + O(1) frequency order → HashMap + per-freq DLL (LFU)
- O(1) insert/delete + O(1) random → Array + HashMap (swap-with-last)
- O(1) min/max + O(1) insert → Heap (O(log n) insert but O(1) peek)
1. List all operations and their required complexity
2. For each operation, identify what primitive gives O(1) or O(log n)
3. Combine: usually HashMap for lookup + another structure for ordering
4. Handle the edge cases: empty structure, single element, capacity exactly full
Common combinations:
- O(1) lookup + O(1) recency order → HashMap + DLL (LRU)
- O(1) lookup + O(1) frequency order → HashMap + per-freq DLL (LFU)
- O(1) insert/delete + O(1) random → Array + HashMap (swap-with-last)
- O(1) min/max + O(1) insert → Heap (O(log n) insert but O(1) peek)