System Design DSA — Complete Guide (LRU, LFU, Caches, Data Structures)

Why System Design DSA?

System design interviews test your ability to combine multiple data structures to build scalable systems. Unlike pure algorithm problems, these require:

Choosing the right data structure for each operation
Maintaining invariants across multiple structures simultaneously
Reasoning about time/space trade-offs at scale

The 7 Core Patterns

Pattern 1 — Doubly Linked List + HashMap (O(1) LRU/LFU)

Constant-time get/put by combining O(1) hashmap lookup with O(1) DLL node manipulation.

Pattern 2 — Min-Heap + HashMap (Priority Queues with Updates)

For leaderboards, Twitter feeds — heap for ordering, map for O(1) lookup.

Pattern 3 — Trie (Prefix-Based Systems)

File systems, autocomplete, phone directories — insert/search in O(key length).

Pattern 4 — Segment Tree / BIT (Range Queries in Streams)

Hit counters, time-series data, log storage with range aggregation.

Pattern 5 — Skip List (Sorted Insert + O(log n) Search)

Redis-style sorted sets — probabilistic balanced structure.

Pattern 6 — Consistent Hashing (Distributed Key-Value)

URL shorteners, distributed caches — ring-based key distribution.

Pattern 7 — State Machine + Queue (Event-Driven Systems)

Snake game, parking systems — state transitions with bounded queues.

Complexity Reference

Design	Get	Put	Key Structure
LRU Cache	O(1)	O(1)	DLL + HashMap
LFU Cache	O(1)	O(1)	2x DLL + 2x HashMap
Twitter Feed	O(log n)	O(log n)	Heap + HashMap
Autocomplete	O(L)	O(L)	Trie
Hit Counter	O(1)	O(1)	Deque / BIT
Skip List	O(log n)	O(log n)	Probabilistic layers

The DLL Node Template (Python)

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = self.next = None

class DLL:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def remove_last(self):
        if self.size == 0:
            return None
        last = self.tail.prev
        self.remove(last)
        return last

This template powers both LRU and LFU — memorise it.