Real World DSA

[!NOTE] This module explores the core principles of Real World DSA, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: From LeetCode to Production

In an interview, O(N) is enough. In production, O(N) might crash the server. Real-world engineering is about tradeoffs between Latency, Throughput, and Consistency.

---

2. The 4 Pillars of System Design Mastery

Pillar	Focus	Why it matters
1. Latency	Sequential vs Random I/O	Why reading from RAM is 100,000x faster than Disk.
2. Throughput	Batching & buffering	How implementations like LSM Trees absorb massive write spikes.
3. Availability	Replication & Sharding	Keeping the system up when nodes fail (Consistent Hashing).
4. Consistency	CAP Theorem	Deciding between “Latest Data” and “System Uptime”.

---

3. The Real-World Toolkit

Data Structure: HashMap + Doubly Linked List.

• HashMap: Key → Node Pointer (For O(1) lookup).
• Doubly Linked List: Maintains order.
• Head: Most Recently Used.
• Tail: Least Recently Used.

When we access an item, we move it to the Head. When we add an item, we add to Head. If full, remove Tail.

---

4. Rate Limiter (Token Bucket)

Requirement: Allow max K requests per second. Data Structure: Queue or Counter.

• Token Bucket: A bucket holds tokens. Refills at rate R. Request consumes a token. If empty, drop request.

---

5. Consistent Hashing (Load Balancing)

Requirement: Distribute keys across N servers. minimize movement when a server is added/removed. Data Structure: Sorted Map (TreeMap) / Ring.

• Hash servers and keys onto a circle (0 to 2³²).
• Key maps to the first server clockwise.

---

6. Code Example: LRU Cache

Java

import java.util.*;

class Node {
  int key, val;
  Node prev, next;
  Node(int k, int v) { key = k; val = v; }
}

class LRUCache {
  Node head = new Node(0, 0), tail = new Node(0, 0);
  Map<Integer, Node> map = new HashMap<>();
  int capacity;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    head.next = tail;
    tail.prev = head;
  }

  private void remove(Node n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
  }

  private void add(Node n) {
    Node headNext = head.next;
    head.next = n;
    n.prev = head;
    n.next = headNext;
    headNext.prev = n;
  }

  public int get(int key) {
    if (!map.containsKey(key)) return -1;
    Node n = map.get(key);
    remove(n);
    add(n);
    return n.val;
  }

  public void put(int key, int value) {
    if (map.containsKey(key)) remove(map.get(key));
    if (map.size() == capacity) {
      remove(map.remove(tail.prev.key));
    }
    Node n = new Node(key, value);
    add(n);
    map.put(key, n);
  }
}

Go

// Go's standard library "container/list" implements Doubly Linked List
import "container/list"

type LRUCache struct {
  Cap   int
  Keys  map[int]*list.Element
  List  *list.List
}

type Pair struct { K, V int }

func Constructor(capacity int) LRUCache {
  return LRUCache{
    Cap:  capacity,
    Keys: make(map[int]*list.Element),
    List: list.New(),
  }
}

func (this *LRUCache) Get(key int) int {
  if el, ok := this.Keys[key]; ok {
    this.List.MoveToFront(el)
    return el.Value.(Pair).V
  }
  return -1
}

func (this *LRUCache) Put(key int, value int) {
  if el, ok := this.Keys[key]; ok {
    el.Value = Pair{key, value}
    this.List.MoveToFront(el)
  } else {
    el := this.List.PushFront(Pair{key, value})
    this.Keys[key] = el
    if this.List.Len() > this.Cap {
      // Remove LRU (Back)
      back := this.List.Back()
      this.List.Remove(back)
      delete(this.Keys, back.Value.(Pair).K)
    }
  }
}

---

7. Deep Dive Strategy Lab: Applications

Intuition Through Analogy

Think of this chapter like running a high-traffic consumer app. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?