Learn Data Structures & Algorithms 🧠

An exhaustive, production-grade masterclass from absolute zero to staff-level algorithmic problem solving & Big-Tech coding interview mastery.
Master asymptotic Big-O analysis, pointer manipulation, monotonic stacks, Hash collision resolution, balanced trees (AVL/Red-Black), binary heaps, graph traversals (Dijkstra, Kruskal's with Union-Find), dynamic programming (0/1 Knapsack, LCS, LIS), and the 14 universal algorithmic patterns.

Getting Started • Linear Structures • Hash & Bitwise • Trees & Heaps • Graph Algorithms • Dynamic Programming • Big-Tech Interview Handbook

🗺️ 7-Stage Pedagogical Roadmap

flowchart LR
    S1["Stage 1: Asymptotic Big-O"] --> S2["Stage 2: Linear & Pointers"]
    S2 --> S3["Stage 3: Hashing & Bits"]
    S3 --> S4["Stage 4: Trees, Heaps, Tries"]
    S4 --> S5["Stage 5: Graphs & Dijkstra"]
    S5 --> S6["Stage 6: Dynamic Programming"]
    S6 --> S7["Stage 7: Big-Tech Handbook"]

Stage	Focus Domain	Core Concepts & Engineering Outcomes
Stage 1	Asymptotic Big-O Foundations	Big-$O$, Big-$\Omega$, Big-$\Theta$, amortized analysis, call stack memory, Master Theorem for divide-and-conquer recurrences.
Stage 2	Linear Data Structures	Dynamic arrays (geometric doubling), Doubly Linked Lists, Floyd's Cycle Detection, Monotonic Stacks, Ring Buffer Deques.
Stage 3	Hashing & Bitwise Mechanics	Hash functions, Separate Chaining vs Open Addressing, XOR manipulation, bitmasks, Brian Kernighan's population count.
Stage 4	Trees, Heaps & Tries	Binary Search Trees (BST), AVL rotations, Binary Heap array representation (heapify), Prefix Tries for autocompletion.
Stage 5	Graph & Network Algorithms	BFS, DFS, Topological Sort (Kahn's), Dijkstra's with Min-Heap, Bellman-Ford, Kruskal's with Disjoint Set Union (Union-Find).
Stage 6	Dynamic Programming & Greedy	Top-down memoization vs bottom-up tabulation, 0/1 Knapsack, Longest Common Subsequence (LCS), Interval Scheduling.
Stage 7	Big-Tech Interview Playbook	14 Universal LeetCode Patterns (Sliding Window, Two Pointers, Top K), 25 staff interview Q&As, Complexity Matrix Cheat Sheet.

📋 Comprehensive Table of Contents

Stage 1: Asymptotic Analysis & Algorithmic Foundations
Stage 2: Linear Data Structures & Pointer Mechanics
Stage 3: Hash Tables, Collisions & Bitwise Manipulation
Stage 4: Trees, Heaps & Prefix Tries
Stage 5: Graphs & Network Flow Algorithms
Stage 6: Dynamic Programming & Advanced Paradigms
Stage 7: Staff Algorithmic Engineer & Interview Handbook

1. Stage 1: Asymptotic Analysis & Algorithmic Foundations

1.1 Understanding Big-O, Big-Omega, and Big-Theta

Asymptotic analysis evaluates how an algorithm's resource consumption (time or memory) scales as input size $N$ approaches infinity ($N \to \infty$):

flowchart TD
    Asymptotic["Asymptotic Notations"] --> BigO["Big-O (O): Upper Bound (Worst-Case Guarantee)"]
    Asymptotic --> BigTheta["Big-Theta (Θ): Tight Bound (Exact Growth Rate)"]
    Asymptotic --> BigOmega["Big-Omega (Ω): Lower Bound (Best-Case Baseline)"]

Big-$O$ ($O(f(n))$): Mathematical upper bound. $T(n) \le c \cdot f(n)$ for all $n \ge n_0$. Guarantees the algorithm will never perform worse than this bound.
Big-$\Omega$ ($\Omega(f(n))$): Mathematical lower bound. $T(n) \ge c \cdot f(n)$.
Big-$\Theta$ ($\Theta(f(n))$): Tight bound. Exists when upper and lower bounds coincide ($c_1 f(n) \le T(n) \le c_2 f(n)$).

1.2 The Time Complexity Hierarchy

Order of growth from best to worst:

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

Complexity	Common Name	Typical Example	Operations for $N = 10^6$
$O(1)$	Constant	Hash table lookup, array index read.	$1 \text{ operation}$
$O(\log N)$	Logarithmic	Binary search in sorted array.	$\approx 20 \text{ operations}$
$O(N)$	Linear	Single loop, finding max in array.	$1,000,000 \text{ operations}$
$O(N \log N)$	Linearithmic	Merge Sort, QuickSort (average), HeapSort.	$\approx 20,000,000 \text{ operations}$
$O(N^2)$	Quadratic	Nested loops, Bubble Sort, Insertion Sort.	$10^{12} \text{ ops (Stalls CPU!)}$
$O(2^N)$	Exponential	Recursive Fibonacci without memoization.	Impossible ($10^{301,029}$ ops)
$O(N!)$	Factorial	Traveling Salesperson brute force.	Impossible

1.3 Space Complexity: Call Stack Frames vs Heap Allocations

Memory complexity measures both auxiliary variable allocations and stack memory consumed by function recursive calls:

// Memory Complexity Analysis
function sumRecursively(n: number): number {
  // Base case
  if (n <= 0) return 0;
  // Each recursive call pushes a stack frame to memory!
  // Time Complexity: O(N)
  // Space Complexity: O(N) due to N stack frames on call stack!
  return n + sumRecursively(n - 1);
}

1.4 Amortized Analysis (The Accounting Method)

When an operation is occasionally expensive but usually cheap, Amortized Analysis averages the total running time over an entire sequence of $N$ operations.

Classic Example: Dynamic Array push():
- $N-1$ insertions take $O(1)$ time (writing to pre-allocated capacity).
- The $N$-th insertion triggers a resize, copying $N$ items to a new array ($O(N)$ time).
- Total time for $N$ pushes: $N + 2N = 3N$ operations.
- Amortized Cost per Push: $\frac{3N}{N} = \mathbf{O(1)}$.

1.5 The Master Theorem for Divide-and-Conquer Recurrences

For recurrences of the form: $$T(n) = a T\left(\frac{n}{b}\right) + O(n^d)$$ Where $a \ge 1$ (subproblems created), $b > 1$ (subproblem size divisor), and $d \ge 0$ (work done outside recursion):

Case Condition	Asymptotic Result	Real-World Example
Case 1: $d < \log_b a$	$T(n) = O(n^{\log_b a})$	Strassen's Matrix Multiplication ($a=7, b=2$)
Case 2: $d = \log_b a$	$T(n) = O(n^d \log n)$	Merge Sort ($a=2, b=2, d=1 \implies O(N \log N)$)
Case 3: $d > \log_b a$	$T(n) = O(n^d)$	Binary Search ($a=1, b=2, d=0 \implies O(\log N)$)

1.6 The 6-Step Problem-Solving Framework for Big-Tech Interviews

flowchart LR
    S1["1. Clarify & Edge Cases (3 min)"] --> S2["2. Brute Force Baseline (5 min)"]
    S2 --> S3["3. Identify Bottleneck & Pattern (5 min)"]
    S3 --> S4["4. Optimal Solution Code (15 min)"]
    S4 --> S5["5. Dry Run / Step-Through (5 min)"]
    S5 --> S6["6. Asymptotic Analysis (2 min)"]

Interview Stage	Candidate Objectives	Common Red Flags
1. Clarification	Ask about input ranges, empty arrays, duplicates, negative numbers, and memory limits.	Jumping immediately to writing code without understanding edge cases.
2. Brute Force	Articulate naive solution ($O(N^2)$ or $O(2^N)$) to prove problem comprehension.	Freezing or remaining silent while searching for the optimal solution.
3. Pattern Matching	Identify duplicate work, sorting opportunities, monotonic sequences, or hash lookups.	Applying complex algorithms (DP/Segment Trees) where Two Pointers suffices.
4. Clean Coding	Write modular, type-safe, production-quality code with descriptive variable names.	Using single-letter variables (`i, j, k, x, y, z`) or leaving unfinished helper stubs.
5. Dry Run	Trace an example input line-by-line using a variable state table on the whiteboard.	Declaring "I'm done" without manually running a single test case.
6. Complexity	State exact Big-$O$ time and space bounds, including recursion call stack frames.	Guessing complexity or ignoring memory allocated by internal library functions.

2. Stage 2: Linear Data Structures & Pointer Mechanics

2.1 Dynamic Arrays & Geometric Capacity Doubling

Arrays are contiguous blocks of physical memory where element memory address is calculated in $O(1)$ time: $$\text{Address}(i) = \text{BaseAddress} + i \times \text{ElementSize}$$

flowchart TD
    Initial["Array [Capacity: 4, Length: 4]"] -->|Push 5th element triggers resize| Allocate["Allocate New Memory Buffer [Capacity: 8]"]
    Allocate --> Copy["Copy 4 existing elements to new memory"]
    Copy --> Append["Insert 5th element at index 4"]

2.2 Singly & Doubly Linked Lists

Linked Lists store non-contiguous heap nodes linked via pointers:

export class ListNode<T> {
  value: T;
  next: ListNode<T> | null = null;
  prev: ListNode<T> | null = null; // Doubly linked list pointer

  constructor(value: T) {
    this.value = value;
  }
}

Operation	Dynamic Array	Singly Linked List	Doubly Linked List
Access by Index `arr[i]`	$O(1)$	$O(N)$	$O(N)$
Insert / Delete at Head	$O(N)$ (shifts all items)	$O(1)$	$O(1)$
Insert / Delete at Tail	$O(1)$ amortized	$O(1)$ (with tail pointer)	$O(1)$
Insert / Delete at Middle	$O(N)$	$O(1)$ (given pointer)	$O(1)$ (given pointer)

2.3 Floyd's Cycle-Finding Algorithm (Tortoise and Hare)

Detects cycles in a linked list using two pointers moving at different velocities in $O(N)$ time and $O(1)$ space:

flowchart LR
    Node1["1"] --> Node2["2"]
    Node2 --> Node3["3"]
    Node3 --> Node4["4"]
    Node4 --> Node2
    Note["Slow pointer advances 1 step; Fast pointer advances 2 steps.<br/>If cycle exists, fast pointer is guaranteed to lap slow pointer!"]

export function hasCycle<T>(head: ListNode<T> | null): boolean {
  if (!head || !head.next) return false;

  let slow: ListNode<T> | null = head;
  let fast: ListNode<T> | null = head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true; // Cycle detected!
    }
  }

  return false; // Reached end of list without cycle
}

2.4 Monotonic Stacks: Next Greater Element in O(N) Time

A Monotonic Stack maintains elements strictly sorted (either ascending or descending) to solve range-based lookups in linear time:

// Find the Next Greater Element for every item in array
export function nextGreaterElements(nums: number[]): number[] {
  const result: number[] = new Array(nums.length).fill(-1);
  const stack: number[] = []; // Stores indices

  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const poppedIndex = stack.pop()!;
      result[poppedIndex] = nums[i];
    }
    stack.push(i);
  }

  return result;
}

2.5 Circular Buffer (Ring Buffer) Queue Implementation

A fixed-capacity FIFO queue utilizing modulo arithmetic to prevent memory reallocations:

export class RingBufferQueue<T> {
  private buffer: (T | null)[];
  private head: number = 0;
  private tail: number = 0;
  private count: number = 0;
  private readonly capacity: number;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.buffer = new Array(capacity).fill(null);
  }

  enqueue(item: T): boolean {
    if (this.count === this.capacity) return false; // Buffer full
    this.buffer[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity;
    this.count++;
    return true;
  }

  dequeue(): T | null {
    if (this.count === 0) return null; // Buffer empty
    const item = this.buffer[this.head];
    this.buffer[this.head] = null;
    this.head = (this.head + 1) % this.capacity;
    this.count--;
    return item;
  }
}

3. Stage 3: Hash Tables, Collisions & Bitwise Manipulation

3.1 Hash Functions & The Avalanche Effect

A hash function maps arbitrary keys (strings, objects) to fixed integer buckets: $$\text{Bucket Index} = \text{hash}(\text{key}) \pmod{\text{Capacity}}$$

Uniform Distribution: Hash values must disperse evenly across all buckets to minimize collisions.
Avalanche Effect: Flipping a single bit in the input key must change $\approx 50%$ of the output bits randomly.

3.2 Collision Resolution: Separate Chaining vs Open Addressing

flowchart TD
    subgraph SeparateChaining["Separate Chaining"]
        B0["Bucket 0"] --> N1["Node (KeyA)"] --> N2["Node (KeyB)"]
        B1["Bucket 1"] --> N3["Node (KeyC)"]
    end
    subgraph OpenAddressing["Open Addressing (Linear Probing)"]
        Slot0["Slot 0: KeyA"]
        Slot1["Slot 1: KeyB (Collided with 0; probed to 1)"]
        Slot2["Slot 2: KeyC"]
    end

Dimension	Separate Chaining	Open Addressing (Linear / Quadratic Probing)
Data Structure	Array of linked lists (or Red-Black trees in Java).	Flat contiguous array with zero pointers.
Load Factor ($\alpha$)	Can exceed $1.0$ ($\alpha > 1$ allowed).	Must remain $< 0.7$ (triggers resize at 70%).
Cache Locality	Poor (pointer chasing across heap memory).	Superior (reads sequential cache lines in RAM).
Deletion Complexity	Simple (standard linked list removal).	Requires "Tombstone" markers to preserve probe chains.

3.3 Bitwise Primitives & Tricks

// Essential Bitwise Hacks
export class BitHacks {
  // 1. Check if number is odd (O(1))
  static isOdd(n: number): boolean {
    return (n & 1) === 1;
  }

  // 2. Check if number is power of two (O(1))
  static isPowerOfTwo(n: number): boolean {
    return n > 0 && (n & (n - 1)) === 0;
  }

  // 3. Swap two numbers without auxiliary memory
  static xorSwap(a: number, b: number): [number, number] {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    return [a, b];
  }

  // 4. Brian Kernighan's Algorithm: Count number of set bits (1s) in integer
  static countSetBits(n: number): number {
    let count = 0;
    while (n > 0) {
      n = n & (n - 1); // Clears the lowest set bit!
      count++;
    }
    return count;
  }
}

Expression	Operational Effect	Mathematical Guarantee
`n & 1`	Isolates Least Significant Bit	Identifies even/odd in 1 CPU cycle.
`n & (n - 1)`	Clears the lowest set bit	Strips lowest `1` bit; tests powers of two.
`n & -n`	Isolates lowest set bit	Binary two's complement identity; used in Fenwick trees.
`n ^ n`	Result is `0`	XOR cancellation; finds single non-duplicate element.

4. Stage 4: Trees, Heaps & Prefix Tries

4.1 Binary Search Trees (BST) & Traversals

A Binary Search Tree enforces the ordering invariant: for every node $X$, all values in the left subtree are $< X$, and all values in the right subtree are $> X$.

flowchart TD
    Root["8"] --> L1["3"]
    Root --> R1["10"]
    L1 --> L2["1"]
    L1 --> R2["6"]
    R1 --> R3["14"]

The 4 Classical Tree Traversals

In-Order (Left -> Root -> Right): Yields elements in strictly sorted ascending order (1, 3, 6, 8, 10, 14).
Pre-Order (Root -> Left -> Right): Ideal for serializing or copying tree structure (8, 3, 1, 6, 10, 14).
Post-Order (Left -> Right -> Root): Ideal for bottom-up deletions or directory size calculations (1, 6, 3, 14, 10, 8).
Level-Order (BFS): Traverses nodes horizontally layer-by-layer using a queue.

4.2 Binary Heaps & Priority Queues

A Min-Heap is a complete binary tree where every parent node is $\le$ both of its children. Because it is a complete tree, heaps are stored compactly in a flat array without pointers!

flowchart TD
    H1["1 (Index 0)"] --> H2["3 (Index 1)"]
    H1 --> H3["6 (Index 2)"]
    H2 --> H4["5 (Index 3)"]
    H2 --> H5["9 (Index 4)"]
    H3 --> H6["8 (Index 5)"]

Array Index Mapping Formulas (Zero-Based)

Left Child: $\text{left}(i) = 2i + 1$
Right Child: $\text{right}(i) = 2i + 2$
Parent Node: $\text{parent}(i) = \lfloor \frac{i - 1}{2} \rfloor$

export class MinHeap {
  private data: number[] = [];

  push(val: number): void {
    this.data.push(val);
    this.bubbleUp(this.data.length - 1);
  }

  pop(): number | null {
    if (this.data.length === 0) return null;
    const min = this.data[0];
    const end = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = end;
      this.sinkDown(0);
    }
    return min;
  }

  private bubbleUp(index: number): void {
    while (index > 0) {
      const parentIdx = Math.floor((index - 1) / 2);
      if (this.data[index] >= this.data[parentIdx]) break;
      [this.data[index], this.data[parentIdx]] = [this.data[parentIdx], this.data[index]];
      index = parentIdx;
    }
  }

  private sinkDown(index: number): void {
    const len = this.data.length;
    while (true) {
      let smallest = index;
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      if (left < len && this.data[left] < this.data[smallest]) smallest = left;
      if (right < len && this.data[right] < this.data[smallest]) smallest = right;
      if (smallest === index) break;

      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
      index = smallest;
    }
  }
}

4.3 Prefix Tries (Retrieval Trees)

A Trie stores strings character by character, sharing common prefixes to enable $O(L)$ search time where $L$ is word length:

flowchart TD
    Root["(Root)"] --> C["'c'"]
    C --> A["'a'"]
    A --> R["'r' (Word: car)"]
    A --> T["'t' (Word: cat)"]

4.5 Production Prefix Trie (Autocomplete Engine) Implementation

export class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

export class Trie {
  private root: TrieNode = new TrieNode();

  // Inserts a word into the trie in O(L) time
  insert(word: string): void {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char)!;
    }
    current.isEndOfWord = true;
  }

  // Returns true if word is in the trie in O(L) time
  search(word: string): boolean {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) return false;
      current = current.children.get(char)!;
    }
    return current.isEndOfWord;
  }

  // Returns true if there is any word in the trie that starts with the given prefix in O(L)
  startsWith(prefix: string): boolean {
    let current = this.root;
    for (const char of prefix) {
      if (!current.children.has(char)) return false;
      current = current.children.get(char)!;
    }
    return true;
  }
}

Operation	Time Complexity	Auxiliary Space	Engineering Benefit
`insert(word)`	$O(L)$	$O(L)$	Inserts word character by character, sharing common prefixes with existing nodes.
`search(word)`	$O(L)$	$O(1)$	Direct branch traversal; returns true only if last node is flagged `isEndOfWord`.
`startsWith(prefix)`	$O(L)$	$O(1)$	Blazing fast search-as-you-type prefix autocompletion for search engines.

5. Stage 5: Graphs & Network Flow Algorithms

5.1 Graph Representations: Adjacency List

Graphs are collections of Vertices ($V$) and Edges ($E$):

export class Graph {
  private adjacencyList: Map<string, { node: string; weight: number }[]> = new Map();

  addVertex(v: string): void {
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
  }

  addEdge(u: string, v: string, weight: number = 1): void {
    this.addVertex(u);
    this.addVertex(v);
    this.adjacencyList.get(u)!.push({ node: v, weight });
  }

  getNeighbors(v: string) {
    return this.adjacencyList.get(v) || [];
  }
}

5.2 Topological Sort (Kahn's Algorithm - In-Degree BFS)

Topological Sort arranges vertices in a Directed Acyclic Graph (DAG) linearly such that for every directed edge $U \to V$, $U$ appears before $V$ (used for build systems and dependency resolution):

flowchart LR
    A["Compile Core"] --> B["Compile Utils"]
    A --> C["Compile UI"]
    B --> D["Bundle Binary"]
    C --> D

export function topologicalSort(numCourses: number, prerequisites: [number, number][]): number[] {
  const inDegree: number[] = new Array(numCourses).fill(0);
  const adj: Map<number, number[]> = new Map();

  for (const [dest, src] of prerequisites) {
    inDegree[dest]++;
    if (!adj.has(src)) adj.set(src, []);
    adj.get(src)!.push(dest);
  }

  // Enqueue all nodes with in-degree 0 (no prerequisites)
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);

    for (const neighbor of adj.get(node) || []) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  return order.length === numCourses ? order : []; // Cycle detected if not all processed!
}

5.3 Dijkstra's Shortest Path Algorithm

Finds the shortest distance from a source vertex to all other vertices in a weighted graph with non-negative edge weights:

export function dijkstra(
  graph: Map<string, { node: string; weight: number }[]>,
  startNode: string
): Map<string, number> {
  const distances: Map<string, number> = new Map();
  const visited: Set<string> = new Set();
  
  // In production, backed by a Min-Heap Priority Queue (O((V + E) log V))
  distances.set(startNode, 0);

  while (true) {
    let closestNode: string | null = null;
    let shortestDist = Infinity;

    for (const [node, dist] of distances) {
      if (!visited.has(node) && dist < shortestDist) {
        shortestDist = dist;
        closestNode = node;
      }
    }

    if (!closestNode) break;
    visited.add(closestNode);

    for (const edge of graph.get(closestNode) || []) {
      const newDist = shortestDist + edge.weight;
      if (newDist < (distances.get(edge.node) ?? Infinity)) {
        distances.set(edge.node, newDist);
      }
    }
  }

  return distances;
}

5.6 Disjoint Set Union (DSU / Union-Find) with Rank & Path Compression

export class DisjointSetUnion {
  private parent: number[];
  private rank: number[];

  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array(size).fill(0);
  }

  // Find root with recursive Path Compression (O(alpha(N)))
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path flattening!
    }
    return this.parent[x];
  }

  // Union by Rank (O(alpha(N)))
  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) return false; // Cycle detected! Already connected

    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }

    return true;
  }
}

Optimization Technique	Mechanism	Complexity Outcome
Path Compression	Points every traversed node directly to root during `find()`.	Flattens tree depth to near-constant levels.
Union by Rank	Attaches shallower tree under deeper tree root.	Prevents degenerate linked list skew.
Combined Complexity	Both techniques applied simultaneously.	Inverse Ackermann $\alpha(N) < 5$ (Amortized $O(1)$).

6. Stage 6: Dynamic Programming & Advanced Paradigms

6.1 The Core Principles of Dynamic Programming (DP)

Dynamic Programming is an optimization technique that solves complex problems by breaking them into simpler subproblems, applicable when problems exhibit:

Optimal Substructure: The optimal solution to the problem contains within it optimal solutions to subproblems.
Overlapping Subproblems: The same subproblems are solved repeatedly throughout execution.

flowchart TD
    Fib5["fib(5)"] --> Fib4["fib(4)"]
    Fib5 --> Fib3A["fib(3) [Duplicate!]"]
    Fib4 --> Fib3B["fib(3) [Duplicate!]"]
    Fib4 --> Fib2A["fib(2) [Duplicate!]"]
    Note["Without memoization: O(2^N) time.<br/>With memoization: O(N) time & O(N) space!"]

6.2 The 0/1 Knapsack Problem Masterclass

Given $N$ items with values $V[i]$ and weights $W[i]$, maximize total value in a knapsack of maximum capacity $C$:

export function knapsack01(values: number[], weights: number[], capacity: number): number {
  const n = values.length;
  // dp[i][w] = max value using first i items with weight capacity w
  const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const val = values[i - 1];
    const wt = weights[i - 1];

    for (let w = 0; w <= capacity; w++) {
      // Option 1: Do not include item i
      dp[i][w] = dp[i - 1][w];

      // Option 2: Include item i (if it fits)
      if (w >= wt) {
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt] + val);
      }
    }
  }

  return dp[n][capacity];
}

Subproblem Choice	Recurrence Formula	Complexity
Exclude item $i$	`dp[i-1][w]`	$O(1)$ lookup
Include item $i$	`dp[i-1][w - wt] + val`	$O(1)$ calculation
Total Grid Size	$(N + 1) \times (C + 1)$ cells	$O(N \times C)$ Time & Space

6.6 Longest Common Subsequence (LCS) Full Tabulation Grid

export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        // Matching characters: extend diagonal subproblem
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // Mismatched characters: take maximum from left or top cell
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

Cell Condition	Recurrence Transition	Computational Meaning
`text1[i-1] == text2[j-1]`	`dp[i-1][j-1] + 1`	Match found! Subsequence length increments by 1 from diagonal.
`text1[i-1] != text2[j-1]`	`max(dp[i-1][j], dp[i][j-1])`	Characters differ; inherit longest sequence excluding either character.
Base Cases	`dp[0][j] = 0`, `dp[i][0] = 0`	An empty string shares 0 common subsequences with any text.

7. Stage 7: Staff Algorithmic Engineer & Interview Handbook

7.1 The 14 Universal Big-Tech Coding Patterns

flowchart TD
    Patterns["14 LeetCode Patterns"] --> P1["1. Sliding Window (Subarrays, Substrings)"]
    Patterns --> P2["2. Two Pointers (Sorted Arrays, Pairs, Palindromes)"]
    Patterns --> P3["3. Fast & Slow Pointers (Cycle Detection, Middle of List)"]
    Patterns --> P4["4. Merge Intervals (Overlapping Schedules)"]
    Patterns --> P5["5. Cyclic Sort (Missing Numbers in 1 to N)"]
    Patterns --> P6["6. In-Place Reversal of LinkedList"]
    Patterns --> P7["7. Tree BFS / DFS (Level-Order & Path Sums)"]
    Patterns --> P8["8. Two Heaps (Find Median from Data Stream)"]
    Patterns --> P9["9. Subsets / Backtracking (Permutations, Combinations)"]
    Patterns --> P10["10. Modified Binary Search (Rotated Arrays)"]
    Patterns --> P11["11. Top K Elements (Min-Heap / QuickSelect)"]
    Patterns --> P12["12. K-Way Merge (Merge K Sorted Lists)"]
    Patterns --> P13["13. Monotonic Stack (Next Greater / Histogram)"]
    Patterns --> P14["14. Topological Sort (Dependency Resolution)"]

7.2 25 Staff-Level Algorithmic Interview Q&As

Q1: What is the exact difference between QuickSort and MergeSort?

Answer: QuickSort is a divide-and-conquer algorithm that selects a pivot, partitions elements around the pivot in-place ($O(1)$ space), and recursively sorts subarrays. Its average time is $O(N \log N)$, but worst-case time is $O(N^2)$ if the pivot is poorly selected. MergeSort divides the array in half, recursively sorts halves, and merges them using an auxiliary array ($O(N)$ space). MergeSort guarantees $O(N \log N)$ worst-case time and is stable (preserves relative order of equal keys), making it the default for sorting linked lists and objects.

Q2: How does QuickSelect find the K-th smallest element in $O(N)$ average time?

Answer: QuickSelect uses the same partitioning logic as QuickSort. After partitioning around a pivot index $P$:

If $P == K$, the element is found.
If $K < P$, recurse ONLY into the left partition.
If $K > P$, recurse ONLY into the right partition. Because it recurses into only one side, the recurrence is $T(N) = T(N/2) + O(N) = N + N/2 + N/4 + \dots = \mathbf{O(N)}$.

Q3: Why is standard Binary Search vulnerable to integer overflow?

Answer: The classic midpoint formula mid = (low + high) / 2 adds low and high. If both are large positive 32-bit integers (e.g. $1.5 \times 10^9$), their sum exceeds $2^{31}-1$, resulting in integer overflow and a negative number, causing out-of-bounds array access. The safe formula is: mid = low + Math.floor((high - low) / 2).

Q4: How do you invert a Binary Tree in $O(N)$ time and $O(H)$ space?

Answer: Using recursion (DFS): for the current node, swap its left and right child pointers: [node.left, node.right] = [node.right, node.left]. Then recursively call invert on both children. Time complexity is $O(N)$ because every node is visited once; space complexity is $O(H)$ where $H$ is tree height ($O(\log N)$ balanced, $O(N)$ worst-case skewed) due to recursion stack frames.

Q5: Explain the difference between BFS and DFS for finding the shortest path.

Answer: BFS explores nodes layer-by-layer in order of distance from the source. In an unweighted graph, the first time BFS reaches the target node, it is mathematically guaranteed to be the shortest path. DFS explores deep along a single branch before backtracking; it does NOT find the shortest path without exploring every path, which takes exponential time.

Q6: How does Dijkstra's algorithm fail when negative edge weights are present?

Answer: Dijkstra's greedy invariant assumes that once a vertex is popped from the priority queue and marked visited, its shortest distance is finalized and cannot be decreased. A negative edge weight introduces the possibility that a longer path with a negative edge yields a smaller total distance, violating this assumption. To handle negative weights, use the Bellman-Ford algorithm ($O(V \times E)$) or SPFA.

Q7: How does Disjoint Set Union (Union-Find) achieve near-constant $O(\alpha(N))$ time?

Answer: By combining two optimizations:

Path Compression: During find(x), every traversed node updates its parent pointer directly to the root, flattening the tree.
Union by Rank: During union(x, y), the root of the smaller tree is attached under the root of the larger tree. Together, operations run in $O(\alpha(N))$ time, where $\alpha$ is the Inverse Ackermann function ($\alpha(N) < 5$ for all values up to atoms in the universe!).

Q8: What is the Sliding Window pattern and when should you use it?

Answer: Sliding Window maintains a contiguous window defined by two pointers (left and right) over an array or string. It expands the window by incrementing right to include elements, and contracts the window by incrementing left when a condition is violated. Used for contiguous subarray problems: finding maximum sum subarray of size $K$, longest substring with distinct characters, or minimum window substring in $O(N)$ time instead of $O(N^2)$.

Q9: How do you detect and print all cycles in a directed graph?

Answer: Using DFS with a 3-color state tracking array:

WHITE (0): Unvisited node.
GRAY (1): Currently visiting in the current DFS recursion stack.
BLACK (2): Fully visited and processed. If DFS visits a neighbor in the GRAY state, a Back-Edge (cycle) is detected! Reconstruct the cycle by tracing parent pointers from the current node back to the gray ancestor.

Q10: What is an LRU Cache and how do you implement it with $O(1)$ operations?

Answer: An LRU (Least Recently Used) Cache provides $O(1)$ get() and put() operations. It combines:

Hash Map: Maps keys to pointers of nodes in a Doubly Linked List for $O(1)$ lookup.
Doubly Linked List: Maintains chronological access order. Most recently accessed items are moved to the head; when capacity is exceeded, the node at the tail is evicted in $O(1)$ time.

Q11: Explain the difference between Memoization and Tabulation in Dynamic Programming.

Answer:

Memoization (Top-Down): Starts at the original problem and recursively breaks it down. Solves subproblems on-demand and caches results in a hash table or array. Easy to write, but incurs call stack frame overhead.
Tabulation (Bottom-Up): Starts from the smallest base cases and iteratively fills an array or grid in order. Eliminates recursion stack overflow and allows space optimization (e.g. keeping only the last 2 rows).

Q12: How do you solve the Two Sum problem in $O(N)$ time and $O(N)$ space?

Answer: Iterate through the array while maintaining a hash map of complement -> index. For each number num, calculate complement = target - num. If the complement exists in the map, return the pair of indices. Otherwise, insert num -> current_index into the map.

Q13: How do you find the Median of a Data Stream in $O(\log N)$ time per insertion?

Answer: Using the Two Heaps Pattern:

A Max-Heap storing the smaller half of numbers.
A Min-Heap storing the larger half of numbers. Maintain the invariant that the Max-Heap has either equal elements or exactly 1 more element than the Min-Heap. The median is either the root of the Max-Heap (if sizes are odd) or the average of both heap roots (if sizes are even).

Q14: What is the difference between Kahn's Algorithm and DFS for Topological Sorting?

Answer:

Kahn's Algorithm: BFS approach tracking in-degrees. Starts with nodes having 0 incoming edges, enqueues them, decrements neighbors' in-degrees, and detects cycles if processed nodes $< V$.
DFS Approach: Visits nodes recursively and prepends completed nodes to a list after all descendants are visited (reverse post-order). Detects cycles using gray recursion stack tracking.

Q15: What is a Monotonic Queue and how does it solve Sliding Window Maximum in $O(N)$ time?

Answer: A Monotonic Queue (implemented via Deque) stores indices of elements maintained in strictly descending value order. For each new element:

Remove elements from the back of the deque that are smaller than the new element.
Remove indices from the front that fell out of the sliding window.
The front of the deque always holds the maximum value in the current window!

Q16: How do you reverse a Singly Linked List iteratively in $O(N)$ time and $O(1)$ space?

Answer: Using three pointers: prev = null, curr = head, next = null. Inside a while (curr !== null) loop: save next node next = curr.next, flip the pointer curr.next = prev, advance previous prev = curr, advance current curr = next. Return prev as the new head.

Q17: What is the Longest Increasing Subsequence (LIS) problem and how is it solved in $O(N \log N)$?

Answer: The standard DP approach takes $O(N^2)$. The $O(N \log N)$ algorithm maintains a dynamic array tails where tails[i] stores the smallest tail of all increasing subsequences of length $i+1$. For each element, use Binary Search (lower_bound) to find its insertion position in tails. If it is larger than all elements, append it; otherwise overwrite the found position.

Q18: What is Kadane's Algorithm for Maximum Subarray Sum?

Answer: Kadane's algorithm solves maximum subarray sum in $O(N)$ time and $O(1)$ space. Maintain currentSum = 0 and maxSum = -Infinity. For each number: currentSum = Math.max(num, currentSum + num); maxSum = Math.max(maxSum, currentSum).

Q19: Explain the difference between Prims and Kruskals algorithms for Minimum Spanning Trees (MST).

Answer:

Prim's Algorithm: Vertex-based greedy approach. Starts from a single vertex and grows the MST by adding the minimum weight edge that connects an unvisited vertex to the tree (optimal for dense graphs $E \approx V^2$).
Kruskal's Algorithm: Edge-based greedy approach. Sorts all edges globally by weight, iterates through edges, and adds an edge if it does not form a cycle using Disjoint Set Union (optimal for sparse graphs $E \ll V^2$).

Q20: What is a Trie and why is it superior to a Hash Map for dictionary lookups?

Answer: A Hash Map searches words in $O(1)$ average time, but cannot efficiently search prefixes (e.g. find all words starting with "app"). A Trie provides $O(L)$ prefix searches, autocomplete, spell-checking, and alphabetical traversal in memory while compressing shared prefixes.

Q21: How do you detect an anagram in $O(N)$ time and $O(1)$ space?

Answer: Create a fixed 26-element integer frequency array. Iterate through string A, incrementing the count for each character arr[char - 'a']++. Iterate through string B, decrementing the count arr[char - 'a']--. If all counts return to zero, the strings are valid anagrams.

Q22: What is the Dutch National Flag problem and how does 3-way partitioning work?

Answer: Sorts an array containing 0s, 1s, and 2s in-place in a single pass ($O(N)$ time, $O(1)$ space) using three pointers: low, mid, and high. If arr[mid] == 0, swap with low and advance both; if arr[mid] == 1, advance mid; if arr[mid] == 2, swap with high and decrement high.

Q23: What is the difference between Backtracking and standard Recursion?

Answer: Standard recursion solves a problem by calling itself on smaller subproblems. Backtracking is a trial-and-error paradigm that explores candidate paths depth-first, checks if the partial candidate violates problem constraints, and if so, undoes the state mutation (backtracks) to explore other branches, drastically pruning the search space (e.g. N-Queens, Sudoku).

Q24: How does a Segment Tree achieve $O(\log N)$ range queries and updates?

Answer: A Segment Tree is a full binary tree where each node represents an interval of an array and stores pre-aggregated data (e.g. sum, min, max). Querying an arbitrary range $[L, R]$ requires traversing at most 4 nodes per tree level ($O(\log N)$). Updating an element updates its leaf and recalculates parents up to the root in $O(\log N)$ time.

Q25: What is the Two-Pointer technique for palindromes?

Answer: Initialize left = 0 and right = str.length - 1. While left < right: if characters do not match, return false; increment left and decrement right. Returns true in $O(N)$ time and $O(1)$ space.

7.3 The Ultimate Data Structures & Algorithms Complexity Matrix

Data Structure	Access	Search	Insertion	Deletion	Space
Array	$O(1)$	$O(N)$	$O(N)$	$O(N)$	$O(N)$
Dynamic Array	$O(1)$	$O(N)$	$O(1)$ amortized	$O(N)$	$O(N)$
Singly Linked List	$O(N)$	$O(N)$	$O(1)$	$O(1)$	$O(N)$
Doubly Linked List	$O(N)$	$O(N)$	$O(1)$	$O(1)$	$O(N)$
Stack / Queue	$O(N)$	$O(N)$	$O(1)$	$O(1)$	$O(N)$
Hash Table	N/A	$O(1)$ avg / $O(N)$	$O(1)$ avg / $O(N)$	$O(1)$ avg / $O(N)$	$O(N)$
Binary Search Tree	$O(\log N)$	$O(\log N)$	$O(\log N)$	$O(\log N)$	$O(N)$
AVL / Red-Black Tree	$O(\log N)$	$O(\log N)$	$O(\log N)$	$O(\log N)$	$O(N)$
Binary Heap	N/A	$O(N)$	$O(\log N)$	$O(\log N)$ pop min	$O(N)$
Trie	N/A	$O(L)$ word len	$O(L)$ word len	$O(L)$ word len	$O(\Sigma \cdot L \cdot N)$

7.4 Top 20 Canonical Big-Tech Interview Problems & Pattern Map

LeetCode #	Problem Name	Core Pattern Applied	Time Complexity	Space Complexity
#1	Two Sum	Hash Map Complement	$O(N)$	$O(N)$
#15	3Sum	Two Pointers + Sorting	$O(N^2)$	$O(1)$
#11	Container With Most Water	Inward Squeezing Two Pointers	$O(N)$	$O(1)$
#3	Longest Substring Without Repeating Characters	Sliding Window + Hash Map	$O(N)$	$O(\min(N, M))$
#206	Reverse Linked List	Iterative 3-Pointer In-Place Swap	$O(N)$	$O(1)$
#141	Linked List Cycle	Fast & Slow Pointers (Floyd's)	$O(N)$	$O(1)$
#20	Valid Parentheses	LIFO Stack Matching	$O(N)$	$O(N)$
#739	Daily Temperatures	Monotonic Decreasing Stack	$O(N)$	$O(N)$
#102	Binary Tree Level Order Traversal	Queue-based BFS	$O(N)$	$O(N)$
#226	Invert Binary Tree	Recursive DFS	$O(N)$	$O(H)$
#98	Validate Binary Search Tree	In-Order DFS Range Check	$O(N)$	$O(H)$
#200	Number of Islands	Matrix BFS / DFS Flood Fill	$O(M \times N)$	$O(M \times N)$
#207	Course Schedule	Topological Sort (Kahn's / DFS)	$O(V + E)$	$O(V + E)$
#215	Kth Largest Element in an Array	Min-Heap or QuickSelect	$O(N \log K)$	$O(K)$
#295	Find Median from Data Stream	Two Heaps (Max-Heap + Min-Heap)	$O(\log N)$	$O(N)$
#70	Climbing Stairs	1D Dynamic Programming (Fibonacci)	$O(N)$	$O(1)$
#322	Coin Change	Bottom-Up DP (Unbounded Knapsack)	$O(N \times \text{amount})$	$O(\text{amount})$
#300	Longest Increasing Subsequence	Binary Search + DP	$O(N \log N)$	$O(N)$
#1143	Longest Common Subsequence	2D Grid Dynamic Programming	$O(M \times N)$	$O(M \times N)$
#53	Maximum Subarray	Kadane's Greedy / DP Algorithm	$O(N)$	$O(1)$

🤝 Community & Contributing

Contributions are welcome! Please review our CONTRIBUTING.md and CODE_OF_CONDUCT.md guidelines before opening issues or submitting pull requests.

📄 License

This project is open-source software licensed under the MIT License.

Name		Name	Last commit message	Last commit date
public		public
src		src
tests		tests
.gitignore		.gitignore
CODE_OF_CONDUCT.md		CODE_OF_CONDUCT.md
CONTRIBUTING.md		CONTRIBUTING.md
Dockerfile		Dockerfile
LICENSE		LICENSE
README.md		README.md
package.json		package.json

Latest commit

History

Folders and files

Repository files navigation

Learn Data Structures & Algorithms 🧠

🗺️ 7-Stage Pedagogical Roadmap

📋 Comprehensive Table of Contents

1. Stage 1: Asymptotic Analysis & Algorithmic Foundations

1.1 Understanding Big-O, Big-Omega, and Big-Theta

1.2 The Time Complexity Hierarchy

1.3 Space Complexity: Call Stack Frames vs Heap Allocations

1.4 Amortized Analysis (The Accounting Method)

1.5 The Master Theorem for Divide-and-Conquer Recurrences

1.6 The 6-Step Problem-Solving Framework for Big-Tech Interviews

2. Stage 2: Linear Data Structures & Pointer Mechanics

2.1 Dynamic Arrays & Geometric Capacity Doubling

2.2 Singly & Doubly Linked Lists

2.3 Floyd's Cycle-Finding Algorithm (Tortoise and Hare)

2.4 Monotonic Stacks: Next Greater Element in O(N) Time

2.5 Circular Buffer (Ring Buffer) Queue Implementation

3. Stage 3: Hash Tables, Collisions & Bitwise Manipulation

3.1 Hash Functions & The Avalanche Effect

3.2 Collision Resolution: Separate Chaining vs Open Addressing

3.3 Bitwise Primitives & Tricks

4. Stage 4: Trees, Heaps & Prefix Tries

4.1 Binary Search Trees (BST) & Traversals

The 4 Classical Tree Traversals

4.2 Binary Heaps & Priority Queues

Array Index Mapping Formulas (Zero-Based)

4.3 Prefix Tries (Retrieval Trees)

4.5 Production Prefix Trie (Autocomplete Engine) Implementation

5. Stage 5: Graphs & Network Flow Algorithms

5.1 Graph Representations: Adjacency List

5.2 Topological Sort (Kahn's Algorithm - In-Degree BFS)

5.3 Dijkstra's Shortest Path Algorithm

5.6 Disjoint Set Union (DSU / Union-Find) with Rank & Path Compression

6. Stage 6: Dynamic Programming & Advanced Paradigms

6.1 The Core Principles of Dynamic Programming (DP)

6.2 The 0/1 Knapsack Problem Masterclass

6.6 Longest Common Subsequence (LCS) Full Tabulation Grid

7. Stage 7: Staff Algorithmic Engineer & Interview Handbook

7.1 The 14 Universal Big-Tech Coding Patterns

7.2 25 Staff-Level Algorithmic Interview Q&As

Q1: What is the exact difference between QuickSort and MergeSort?

Q2: How does QuickSelect find the K-th smallest element in $O(N)$ average time?

Q3: Why is standard Binary Search vulnerable to integer overflow?

Q4: How do you invert a Binary Tree in $O(N)$ time and $O(H)$ space?

Q5: Explain the difference between BFS and DFS for finding the shortest path.

Q6: How does Dijkstra's algorithm fail when negative edge weights are present?

Q7: How does Disjoint Set Union (Union-Find) achieve near-constant $O(\alpha(N))$ time?

Q8: What is the Sliding Window pattern and when should you use it?

Q9: How do you detect and print all cycles in a directed graph?

Q10: What is an LRU Cache and how do you implement it with $O(1)$ operations?

Q11: Explain the difference between Memoization and Tabulation in Dynamic Programming.

Q12: How do you solve the Two Sum problem in $O(N)$ time and $O(N)$ space?

Q13: How do you find the Median of a Data Stream in $O(\log N)$ time per insertion?

Q14: What is the difference between Kahn's Algorithm and DFS for Topological Sorting?

Q15: What is a Monotonic Queue and how does it solve Sliding Window Maximum in $O(N)$ time?

Q16: How do you reverse a Singly Linked List iteratively in $O(N)$ time and $O(1)$ space?

Q17: What is the Longest Increasing Subsequence (LIS) problem and how is it solved in $O(N \log N)$?

Q18: What is Kadane's Algorithm for Maximum Subarray Sum?

Q19: Explain the difference between Prims and Kruskals algorithms for Minimum Spanning Trees (MST).

Q20: What is a Trie and why is it superior to a Hash Map for dictionary lookups?

Q21: How do you detect an anagram in $O(N)$ time and $O(1)$ space?

Q22: What is the Dutch National Flag problem and how does 3-way partitioning work?

Q23: What is the difference between Backtracking and standard Recursion?

Q24: How does a Segment Tree achieve $O(\log N)$ range queries and updates?

Q25: What is the Two-Pointer technique for palindromes?

7.3 The Ultimate Data Structures & Algorithms Complexity Matrix

7.4 Top 20 Canonical Big-Tech Interview Problems & Pattern Map

🤝 Community & Contributing

📄 License

About

Resources

Code of conduct

Contributing

Stars

Watchers

Forks

Releases