System Design DSA — Master Recap & Pattern Cheatsheet

System Design DSA — Master Recap

Pattern → Problem Mapping

Pattern	Problems	Core Structures
DLL + HashMap	LRU Cache	O(1) get/put
FreqMap + DLL + HashMap	LFU Cache	O(1) freq-aware eviction
Global Timer + Heap	Twitter Feed	k-way merge
HashMap path strings	File System	O(L) create/get
Circular Array	Hit Counter	O(1) time-bucketed
Binary Search on timestamps	Time-Based KV	O(log n) get
Trie + Freq Map	Autocomplete	O(L) prefix search
Array + Index Pointer	Browser History	O(1) nav
Max-Heap + Min-Heap	Median Finder	O(log n) add
Skip List	Sorted Structure	O(log n) expected

The Decision Framework

Need O(1) lookup by key?
  → HashMap as base

Need ordering (min/max/sorted)?
  → + Heap, TreeMap, or Sorted List

Need O(1) move-to-front/back?
  → + Doubly Linked List

Need frequency tracking?
  → Two HashMaps (key→freq, freq→OrderedSet)

Need prefix matching?
  → Trie

Need range queries on timestamps?
  → Sorted list + Binary Search

Need running statistics (median)?
  → Two Heaps (lo max-heap, hi min-heap)

LRU vs LFU Comparison

Feature	LRU	LFU
Eviction	Least recently used	Least frequently used (+ LRU tie-break)
Structures	1 DLL + 1 HashMap	2 DLL + 2 HashMap + min_freq
Complexity	O(1)	O(1)
Use case	Web cache, CDN	Database buffer pool

Two-Heap Pattern (Median)

lo = max-heap  (lower half, negate values)
hi = min-heap  (upper half)

# Invariant: len(lo) >= len(hi) and lo.max <= hi.min
def addNum(n):
    push to lo
    move lo.top to hi
    if len(hi) > len(lo): move hi.top to lo

def median():
    if odd: return lo.top
    else: return (lo.top + hi.top) / 2

Skip List Levels

Probability of reaching level k = (1/2)^k
Expected levels = O(log n)
Expected search cost = O(log n)

_random_level():
    level = 1
    while random() < 0.5 and level < MAX:
        level += 1
    return level

Circular Buffer Formula

tail = (tail + 1) % capacity   # advance tail
head = (head + 1) % capacity   # advance head
full  → size == capacity
empty → size == 0

Quick Reference: All 20 Problems

00 — Guide (7 patterns, DLL template)
01 — LRU Cache         → DLL + HashMap
02 — LFU Cache         → 2x DLL + 2x HashMap + min_freq
03 — Design Twitter    → Global timer + k-way heap merge
04 — File System       → HashMap with parent-path check
05 — Hit Counter       → Circular buffer (300 buckets)
06 — Time-Based KV     → HashMap of sorted lists + bisect
07 — Autocomplete      → Trie with per-node freq map
08 — Browser History   → Array + curr index
09 — Leaderboard       → HashMap + nlargest
10 — Snake Game        → Deque + HashSet
11 — Skiplist          → Probabilistic layered list
12 — Log Storage       → Array + granularity prefix compare
13 — Phone Directory   → Queue + bool array
14 — In-Memory DB      → HashMap of TreeMaps
15 — Min Stack         → Stack + parallel min stack
16 — Median Finder     → max-heap lo + min-heap hi
17 — Circular Queue    → Ring buffer with head/tail/size
18 — TinyURL           → Counter + base-62 + HashMap
19 — Parking System    → Array[3] counters
20 — Master Recap      → This file

Common Mistakes

LRU: Forgetting to delete cache[lru.key] when evicting
LFU: Not decrementing min_freq correctly when freq set becomes empty
Median: Pushing to hi first then rebalancing (not pushing to lo first)
Hit Counter: Using < instead of <= in window check (ts - 300 < hit_ts <= ts)
Skip List: Forgetting to update self.level when top levels become empty after erase