System Design DSA — Master Recap and Pattern Cheatsheet

Problem Statement#

This master recap covers the complete system design DSA category: 20 problems across data structure design patterns. Use this as your final review before interviews covering design problems at Google, Amazon, Meta, and Microsoft.

Patterns covered:

• Hashmap + Sorted List (Time-Based KV)
• Trie + Frequency Map (Autocomplete)
• Circular Buffer (Hit Counter)
• Two Heaps (Median Finder)
• Deque + HashSet (Snake Game)
• Skip List (Probabilistic sorted structure)

Pattern:  Two Heaps
Problem:  Find Median from Data Stream
Approach: lo = max-heap (lower half), hi = min-heap (upper half)

Pattern:  Circular Buffer
Problem:  Hit Counter
Approach: 300-slot array, timestamp % 300 as index

Why This Category Matters#

System design DSA problems bridge the gap between pure algorithms and real-world engineering. Every major company—Google, Amazon, Meta, Microsoft—has a design component in their interview loops. These 20 problems represent the coding implementations of data structures that power production systems: Redis uses skip lists, browsers use the history stack, rate limiters use circular buffers.

Mastering this category signals that you can not only solve algorithmic problems but also design reusable, composable abstractions. Senior engineers at FAANG are evaluated primarily on design quality, not just correctness.

The Core Insight#

Each system design DSA problem reduces to choosing the right combination of two or three primitive structures. The decision framework:

Need O(1) lookup by key: start with a HashMap. Need ordering (min/max/sorted): add a Heap, TreeMap, or SortedList. Need O(1) move-to-front/back: add a Doubly Linked List. Need frequency tracking: use two HashMaps (key to freq, freq to OrderedSet). Need prefix matching: use a Trie. Need range queries on sorted data: sorted list plus binary search. Need running statistics: two Heaps.

Visual Dry Run#

Solution (Optimal)#

# The Two-Heap Pattern (Median Finder)
import heapq
 
class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negate values)
        self.hi = []  # min-heap
 
    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
 
    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0

// The Circular Buffer Pattern (Hit Counter)
class HitCounter {
    constructor() {
        this.times = new Array(300).fill(0);
        this.hits = new Array(300).fill(0);
    }
 
    hit(ts) {
        const i = ts % 300;
        if (this.times[i] !== ts) { this.times[i] = ts; this.hits[i] = 0; }
        this.hits[i]++;
    }
 
    getHits(ts) {
        let total = 0;
        for (let i = 0; i < 300; i++) {
            if (ts - this.times[i] < 300) total += this.hits[i];
        }
        return total;
    }
}

Time: varies by pattern — see table above
Space: O(N) for all patterns where N is the number of stored entries

Common Mistakes#

• LRU: forgetting to delete cache[lru_key] from the hashmap when evicting the LRU node from the DLL
• LFU: not decrementing min_freq correctly when a frequency bucket becomes empty after removal
• Median Finder: pushing to hi first breaks the invariant—always push to lo first
• Hit Counter: using <= instead of < in the window check causes boundary errors
• Skip List: forgetting to shrink self.level after erase when top levels become empty after deletion

Interview Tips#

• For each design problem, state the pattern name before coding: "This is a two-heap problem, similar to Median Finder"
• Always discuss time and space complexity for every operation, not just the most common one
• Connect each data structure to a real system: skip list = Redis sorted sets, circular buffer = API rate limiter, two heaps = P99 latency tracking
• If you forget the exact implementation, describe the invariant and the rebalancing logic—partial credit is real

Follow-up Questions#

• How do these data structures change at distributed scale? (Shard by key, aggregate with eventual consistency, use consensus protocols for atomicity)
• Which of these 20 problems is most likely to appear in a Google L5 interview? (Median Finder, LRU Cache, and Autocomplete are the top 3)
• How do you choose between a SortedList and a Heap for top-K queries? (SortedList if you need arbitrary inserts and deletes; Heap if you only need the top or bottom K)
• What is the common failure mode in a two-heap median implementation? (Pushing to hi before lo; forgetting to rebalance after each insert)
• How would you implement a Max Stack using the Min Stack pattern? (Parallel max stack storing running maximum at each depth)

Key Takeaways#

• System design DSA problems combine 2-3 primitive structures; master the combination patterns, not individual structures in isolation
• The two-heap pattern (lo max-heap + hi min-heap) enables O(log N) insert and O(1) median—used in all streaming quantile problems
• The circular buffer (N-slot array with ts % N indexing) gives O(1) sliding window counts with fixed memory
• Skip lists provide O(log N) expected sorted operations and are used in Redis, LevelDB, and HBase
• Browser history, parking system, and phone directory demonstrate that simple structures (array, counter, queue) are often the right answer
• DLL + HashMap is the canonical O(1) cache design—LRU uses one DLL, LFU uses one DLL per frequency level
• Every design problem has a "why this matters" angle: connect your solution to a real production system for maximum interview impact