Bigger Tool, Bigger Hunt

Graph — BFS, DFS, Topological Sort, Union-Find

Not simple family-tree anymore. Graph — cave with many path, some path go back, some cross each other. Node connect to any other node, not just one parent-child.

// BFS — level by level using Queue
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

// Topological Sort — order that respect dependency
function topoSort(graph, nodes) {
  const visited = new Set(), stack = [];
  function dfs(node) {
    visited.add(node);
    for (const n of graph[node] || []) if (!visited.has(n)) dfs(n);
    stack.push(node); // push after all children done
  }
  for (const n of nodes) if (!visited.has(n)) dfs(n);
  return stack.reverse();
}

// Union-Find — track connected group, detect cycle in undirected graph
class UnionFind {
  constructor(n) { this.parent = Array.from({length:n}, (_, i) => i); }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); // path compression
    return this.parent[x];
  }
  union(a, b) { this.parent[this.find(a)] = this.find(b); }
}

Dynamic Programming — Fibonacci to Knapsack

Recursion waste time re-solve same small problem again and again. DP remember answer first time (memo), never solve same small problem twice. Big speed gain.

// Fibonacci — bottom-up tabulation (start easy)
function fibDP(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

// 0/1 Knapsack — grow to hard
function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({length:n+1}, () => new Array(capacity+1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(
          dp[i-1][w],                                   // skip item
          values[i-1] + dp[i-1][w - weights[i-1]]   // take item
        );
      } else {
        dp[i][w] = dp[i-1][w];  // too heavy, must skip
      }
    }
  }
  return dp[n][capacity];
}

Heap

Pile of stone, but special rule — biggest (or smallest) stone always sit on top, easy grab. Not fully sorted, just top always correct.

// Min-Heap core operation (array-based)
class MinHeap {
  constructor() { this.heap = []; }
  peek() { return this.heap[0]; }
  push(val) {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = Math.floor((i-1)/2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }
  // pop() would "bubble down" the last element to restore heap order — similar idea reversed
}

Trie (Prefix Tree)

Tree built from letter, not number. Each path from root spell out word. Share common prefix — "cat" and "car" share "ca" branch.

class TrieNode {
  constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd;
  }
}

Greedy

Hunter grab best-looking stone right now, never look back, never change mind. Fast, but only work if "best now" always lead to "best overall."

// Activity Selection — max number of non-overlapping meeting
function maxActivities(activities) {
  // sort by end time — greedy rule: always pick earliest-finishing next
  activities.sort((a, b) => a.end - b.end);
  let count = 1, lastEnd = activities[0].end;
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      count++;
      lastEnd = activities[i].end;
    }
  }
  return count;
}

Big-O Review

Stop. Look back all tool learned. Big-O — how hunt-time grow when pile of stone grow bigger. This week: no new tool, just sharpen eye for speed.

Load Balancer

Too many hunter come to one small cave-entrance, jam happen. Load Balancer stand at front door, send each hunter to different entrance, spread the crowd even.

Caching

Instead walk far storage-cave every time, keep copy of popular stone near front door (cache). Much faster grab, but must remember to update if real stone change.

Database Index

Without index, database must walk every single row to find answer — like search whole cave stone-by-stone. Index — like table-of-content at cave entrance, jump straight to right shelf.

Vertical vs Horizontal Scale

Cave getting crowded — two choice. Make one cave bigger (vertical), or build more cave side by side (horizontal).