61DSA Fundamentals (deep teach)

61.1 Complexity — the alphabet

61.2 Arrays & Strings

• Contiguous memory; O(1) index access; O(n) insert/delete in middle
• Dynamic arrays (JS Array, Python list) — amortised O(1) push, resize doubles capacity
• Strings are usually immutable in JS — every "modification" creates a new string
• Two-pointer — sorted array tricks (pair sum, palindrome)
• Sliding window — substring/subarray with constraints
• Prefix sum — range queries in O(1) after O(n) preprocessing

// Prefix sum
function prefix(nums: number[]): number[] {
  const p = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) p[i + 1] = p[i] + nums[i];
  return p;
}
// rangeSum(l, r) = p[r+1] - p[l]

61.3 Hashmaps & Sets

• Average O(1) insert/lookup; worst case O(n) with adversarial keys
• Use Set when you only need membership; Map when you need a value per key
• JS Map preserves insertion order; {} coerces keys to string
• Hash collisions in practice are extremely rare for non-adversarial workloads

61.4 Stacks & Queues

JS arrays approximate all four — push/pop for stack, push/shift for queue (but shift is O(n)!). For real queue use a linked list or a JS class.

61.5 Linked Lists

class Node { val: number; next: Node | null = null; constructor(v: number) { this.val = v; } }

// Insert at head — O(1)
function prepend(head: Node | null, v: number): Node {
  const n = new Node(v); n.next = head; return n;
}

// Reverse iteratively — O(n) time, O(1) space
function reverse(head: Node | null): Node | null {
  let prev: Node | null = null, curr = head;
  while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
  return prev;
}

When to use a linked list: O(1) insert/delete at known positions; no random access required. Most real code uses arrays — linked lists are interview territory.

61.6 Trees

Tree traversals

• Inorder (left, root, right) — gives sorted order on a BST
• Preorder (root, left, right) — useful for cloning
• Postorder (left, right, root) — useful for deleting
• BFS / level-order — queue-based, useful for "shortest path"

// DFS preorder
function preorder(n: TreeNode | null, out: number[] = []): number[] {
  if (!n) return out;
  out.push(n.val);
  preorder(n.left, out);
  preorder(n.right, out);
  return out;
}

// BFS
function bfs(root: TreeNode | null): number[] {
  const out: number[] = [], q: TreeNode[] = root ? [root] : [];
  while (q.length) {
    const n = q.shift()!;
    out.push(n.val);
    if (n.left) q.push(n.left);
    if (n.right) q.push(n.right);
  }
  return out;
}

61.7 Graphs

A graph = nodes + edges. Directed or undirected, weighted or not, cyclic or acyclic.

Representations

• Adjacency list — Map<node, node[]>. Best for sparse graphs.
• Adjacency matrix — 2D array; O(1) edge check, O(n²) space.

Algorithms

61.8 Sorting

61.9 Recursion & DP

Recursion basics

• Base case (when to stop)
• Recursive case (smaller subproblem)
• Combine results
• Watch the call stack — JS doesn't tail-call optimise

Memoisation (top-down DP)

// Fibonacci with memo
const memo = new Map<number, number>();
function fib(n: number): number {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n)!;
  const r = fib(n - 1) + fib(n - 2);
  memo.set(n, r);
  return r;
}
// O(n) with memo vs O(2^n) without

Tabulation (bottom-up DP)

function fib2(n: number): number {
  if (n < 2) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
// O(n) time, O(1) space

61.10 When to use which

61.11 Advanced data structures (dev-level)

Fenwick tree (Binary Indexed Tree)

O(log n) prefix sums with point updates. Compact array implementation.

class Fenwick {
  private bit: number[];
  constructor(n: number) { this.bit = new Array(n + 1).fill(0); }
  update(i: number, delta: number) {
    for (i++; i < this.bit.length; i += i & -i) this.bit[i] += delta;
  }
  query(i: number): number {           // prefix sum [0..i]
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.bit[i];
    return s;
  }
}

Segment tree

Range queries (sum/min/max) + range updates with lazy propagation. O(log n) per op.

Union-Find (Disjoint Set Union)

class DSU {
  parent: number[]; rank: number[];
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);  // path compression
    return this.parent[x];
  }
  union(x: number, y: number): boolean {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;
    if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
    else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
    else { this.parent[ry] = rx; this.rank[rx]++; }
    return true;
  }
}
// Nearly O(1) per op with both optimisations

Trie + Aho-Corasick

class Trie {
  children = new Map<string, Trie>();
  end = false;
  insert(word: string) {
    let n: Trie = this;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, new Trie());
      n = n.children.get(c)!;
    }
    n.end = true;
  }
  search(word: string): boolean {
    let n: Trie = this;
    for (const c of word) {
      if (!n.children.has(c)) return false;
      n = n.children.get(c)!;
    }
    return n.end;
  }
}
// Aho-Corasick = Trie + failure links → multi-pattern search in O(text + patterns + matches)

Bloom filter

Probabilistic membership: false positives possible, false negatives impossible. Tiny memory. K hash functions set K bits per insert; lookup checks all K bits.

Skip list

Probabilistic alternative to balanced trees. Multiple levels of forward pointers. Average O(log n) ops. Used in Redis sorted sets, LevelDB.

LRU cache (O(1) all ops)

Hashmap + doubly-linked list. Map keys → list nodes. Move to head on access; evict tail on overflow. (See dev ebook m41 for full implementation.)

61.12 Graph algorithms (advanced)

61.13 Dynamic programming patterns (complete catalogue)

61.14 Bit manipulation

x & (x - 1)        // clears lowest set bit (Brian Kernighan)
x & -x             // isolates lowest set bit
x | (1 << k)       // set bit k
x & ~(1 << k)      // clear bit k
x ^ (1 << k)       // toggle bit k
(x >> k) & 1       // read bit k
Number.isInteger(Math.log2(x))  // is x a power of 2

// Count set bits (popcount)
function popcount(x: number): number {
  let c = 0;
  while (x) { x &= x - 1; c++; }
  return c;
}

// Swap without temp
a ^= b; b ^= a; a ^= b;

61.15 Math you'll use

• Modular arithmetic — large number ops mod prime; (a + b) % m, (a * b) % m, Fermat's little theorem for inverse
• GCD (Euclidean): gcd(a,b) = b == 0 ? a : gcd(b, a % b)
• Sieve of Eratosthenes — primes up to N in O(N log log N)
• Combinatorics — nCr precomputation via Pascal's triangle
• Geometry — line intersection, convex hull (Graham scan)
• Reservoir sampling — pick K from a stream of unknown length, uniform probability

61.16 SDET-flavoured DSA scenarios (interview-real)

1. Test selection algorithm — given a diff (set of changed files) + a coverage map (test → files covered), select minimum tests covering all changed files (set cover, greedy approximation)
2. Flake detection — given a stream of test results (pass/fail per run), detect tests with failure rate > X% in sliding window of N (sliding window + counter)
3. Dependency graph — given a Jenkins job DAG, find longest path (critical path), detect cycles (topological sort)
4. Test ordering — schedule tests to minimise total wall-clock time across K parallel workers (LPT scheduling, NP-hard, greedy approx)
5. Log-search — find requests matching a pattern in a 100 GB log file; can't load to memory (streaming + grep + parallel)
6. Rate limiter — design a sliding-window counter (sorted set in Redis, or per-shard counters with aggregation)