Design Patterns

"Singleton, factory, observer, strategy, decorator, adapter, command, iterator. OOP design in coding interviews."

Deep Dive Tutorial

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

lightbulb

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

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++;
    }
}

Worked Problems

Medium

Hard

All O(1) Data Structure

Hard

Solve ↗

Design a Number Container System

Medium

Solve ↗

brain

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)

← All Patterns