Data Structures & Algorithms

const names = Array.from({ length: 200_000 }, (_, i) => "user" + i)
const lookup = new Set(names)              // same data, different structure

const timed = fn => { const t = Date.now(); fn(); return Date.now() - t }

// Is "user199999" in the data? An array checks every item; a Set jumps straight there.
const arrayMs = timed(() => { for (let i = 0; i < 200; i++) names.includes("user199999") })
const setMs = timed(() => { for (let i = 0; i < 200; i++) lookup.has("user199999") })
console.log("array search:", arrayMs > setMs * 5 ? "much slower than the Set" : "about the same (try a bigger list)")
console.log("set search:", setMs < 50 ? "instant" : "slow?")

const timed = fn => { const t = Date.now(); fn(); return Date.now() - t }
const n = 50_000
const pushMs = timed(() => { const a = []; for (let i = 0; i < n; i++) a.push(i) })
const unshiftMs = timed(() => { const a = []; for (let i = 0; i < n; i++) a.unshift(i) })
console.log("push 50k at the END:", pushMs < unshiftMs ? "fast" : "?")
console.log("unshift 50k at the FRONT:", unshiftMs > pushMs * 3 ? "much slower — every item shuffles right" : "similar?")

// The skills that matter most: index, slice, and knowing what mutates
const nums = [10, 20, 30, 40, 50]
console.log(nums[0], nums.at(-1), nums.slice(1, 3), nums.toReversed())
nums.push(60); nums.pop(); nums[2] = 99
console.log(nums)

// Two-dimensional array: an array of arrays (a grid)
const grid = Array.from({ length: 2 }, () => Array(3).fill(0))   // 2 rows × 3 columns
grid[0][1] = 7
console.log(grid)

// Holes and sparse arrays — avoid them
const sparse = []
sparse[5] = 1
console.log(sparse.length, sparse)

// A toy hash map in 20 lines — so it stops being magic
class TinyMap {
  constructor(slots = 8) { this.buckets = Array.from({ length: slots }, () => []) }   // each slot holds [key, value] pairs
  #hash(key) {
    let h = 0
    for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0
    return h % this.buckets.length                 // key → slot number
  }
  set(key, value) {
    const bucket = this.buckets[this.#hash(key)]
    const hit = bucket.find(pair => pair[0] === key)
    if (hit) hit[1] = value; else bucket.push([key, value])
    return this
  }
  get(key) {
    return this.buckets[this.#hash(key)].find(pair => pair[0] === key)?.[1]   // only ONE bucket is searched
  }
}
const m = new TinyMap()
m.set("ada", 36).set("bob", 28).set("ada", 37)
console.log(m.get("ada"), m.get("bob"), m.get("zed"))

// The real thing — and the idioms you use every day
const counts = new Map()
for (const word of "a b a c b a".split(" ")) counts.set(word, (counts.get(word) ?? 0) + 1)   // counting idiom
console.log(counts)

const groups = new Map()
for (const [name, team] of [["ada", "data"], ["bob", "infra"], ["cy", "data"]]) {
  if (!groups.has(team)) groups.set(team, [])       // grouping idiom
  groups.get(team).push(name)
}
console.log(groups)
console.log(Object.groupBy(["ada", "bob", "cy"], n => n.length))   // ES2024 shortcut (integer-like keys print in ascending order)

// Sets: membership, dedupe, and the algebra
const seen = new Set(["ada", "bob"])
console.log(seen.has("ada"), seen.has("zed"), [...new Set([3, 1, 3, 2, 1])])
const a = new Set([1, 2, 3]), b = new Set([2, 3, 4])
console.log([...a].filter(x => b.has(x)), [...new Set([...a, ...b])], [...a].filter(x => !b.has(x)))

// Objects as keys: identity, not contents
const byPoint = new Map()
byPoint.set([0, 1], "start")
console.log(byPoint.get([0, 1]), byPoint.get("0,1"))

class Stack {
  #items = []
  push(x) { this.#items.push(x); return this }
  pop() { if (!this.#items.length) throw new RangeError("pop from empty stack"); return this.#items.pop() }
  peek() { return this.#items.at(-1) }
  get size() { return this.#items.length }
}
const s = new Stack().push(1).push(2).push(3)
console.log(s.pop(), s.pop(), s.size, s.peek())

// Use 1: reverse anything
function reverse(text) {
  const stack = [...text], out = []
  while (stack.length) out.push(stack.pop())
  return out.join("")
}
console.log(reverse("stack"))

// Use 2: match brackets — the interview classic
function balanced(expr) {
  const pairs = { ")": "(", "]": "[", "}": "{" }
  const stack = []
  for (const ch of expr) {
    if ("([{".includes(ch)) stack.push(ch)
    else if (ch in pairs && stack.pop() !== pairs[ch]) return false
  }
  return stack.length === 0
}
console.log(balanced("{[()]}"), balanced("([)]"), balanced("(("))

// Use 3: evaluate postfix ("3 4 + 2 *" means (3 + 4) * 2)
function evalPostfix(tokens) {
  const stack = []
  for (const t of tokens.split(" ")) {
    if (/^\d+$/.test(t)) stack.push(Number(t))
    else { const b = stack.pop(), a = stack.pop(); stack.push({ "+": a + b, "-": a - b, "*": a * b }[t]) }
  }
  return stack[0]
}
console.log(evalPostfix("3 4 + 2 *"))

// Use 4: undo
const history = []
let text = ""
const type = s => { history.push(text); text += s }
const undo = () => { text = history.pop() ?? text }
type("hel"); type("lo"); undo()
console.log(text)

// A real queue: head index, compact occasionally
class Queue {
  #items = []
  #head = 0
  enqueue(x) { this.#items.push(x); return this }
  dequeue() {
    if (this.isEmpty()) return undefined
    const x = this.#items[this.#head++]
    if (this.#head > 1024 && this.#head * 2 > this.#items.length) {   // reclaim space now and then
      this.#items = this.#items.slice(this.#head); this.#head = 0
    }
    return x
  }
  peek() { return this.#items[this.#head] }
  isEmpty() { return this.#head >= this.#items.length }
  get size() { return this.#items.length - this.#head }
}
const q = new Queue().enqueue("ada").enqueue("bob").enqueue("cy")
console.log(q.dequeue(), q.dequeue(), q.size, q.peek())

// A queue-based simulation: round-robin scheduler
function roundRobin(tasks, quantum) {
  const q = new Queue()
  for (const t of tasks) q.enqueue(t)              // [name, remaining]
  const order = []
  while (!q.isEmpty()) {
    const [name, left] = q.dequeue()
    if (left - quantum > 0) q.enqueue([name, left - quantum])   // back of the line
    else order.push(name)                                        // finished
  }
  return order
}
console.log(roundRobin([["A", 5], ["B", 2], ["C", 4]], 2))

// A sliding window of the last k items (a bounded queue)
const last3 = []
for (const x of [1, 2, 3, 4, 5, 6]) { last3.push(x); if (last3.length > 3) last3.shift() }   // tiny, shift is fine
console.log(last3)

class Node {
  constructor(value, next = null) { this.value = value; this.next = next }   // next: another Node, or null at the end
}
class LinkedList {
  head = null
  pushFront(value) { this.head = new Node(value, this.head); return this }   // O(1)
  append(value) {                                                            // O(n) without a tail pointer
    const node = new Node(value)
    if (!this.head) { this.head = node; return this }
    let cur = this.head
    while (cur.next) cur = cur.next                  // walk to the last node
    cur.next = node
    return this
  }
  remove(value) {                                    // unlink the first match
    let prev = null, cur = this.head
    while (cur && cur.value !== value) { prev = cur; cur = cur.next }
    if (!cur) return false
    if (!prev) this.head = cur.next                  // removing the head
    else prev.next = cur.next                        // skip over cur
    return true
  }
  *[Symbol.iterator]() { for (let cur = this.head; cur; cur = cur.next) yield cur.value }
  toString() { return [...this, "null"].join(" -> ") }
}

const ll = new LinkedList().pushFront(3).pushFront(2).pushFront(1).append(4)
console.log(String(ll))
console.log(ll.remove(2), ll.remove(99), String(ll))

// The interview classic: reverse in place, three pointers
function reverse(ll) {
  let prev = null, cur = ll.head
  while (cur) {
    const next = cur.next       // remember where we were going
    cur.next = prev             // flip the arrow
    prev = cur; cur = next      // step forward
  }
  ll.head = prev
}
reverse(ll)
console.log(String(ll))

// Two pointers: find the middle without counting
function middle(ll) {
  let slow = ll.head, fast = ll.head
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next }
  return slow?.value
}
console.log(middle(ll))

function factorial(n) {
  if (n <= 1) return 1                 // base case
  return n * factorial(n - 1)          // step: trust the smaller call
}
console.log(factorial(5))

// Make the stack visible
function factorialLoud(n, depth = 0) {
  const pad = "  ".repeat(depth)
  console.log(`${pad}factorial(${n})`)
  if (n <= 1) { console.log(`${pad}→ 1`); return 1 }
  const result = n * factorialLoud(n - 1, depth + 1)
  console.log(`${pad}→ ${result}`)
  return result
}
factorialLoud(4)

// Recursion on a structure: sum a nested array of any depth
const deepSum = x => Array.isArray(x) ? x.reduce((s, item) => s + deepSum(item), 0) : x
console.log(deepSum([1, [2, [3, 4]], 5]))

// Every recursion is also a loop with an explicit stack
function deepSumIter(x) {
  let total = 0
  const stack = [x]
  while (stack.length) {
    const item = stack.pop()
    if (Array.isArray(item)) stack.push(...item)
    else total += item
  }
  return total
}
console.log(deepSumIter([1, [2, [3, 4]], 5]))

// Fast power in O(log n): halve the exponent
function power(base, exp) {
  if (exp === 0) return 1
  const half = power(base, Math.floor(exp / 2))
  return exp % 2 === 0 ? half * half : half * half * base
}
console.log(power(2, 10), power(3, 5))

class TreeNode {
  constructor(value) { this.value = value; this.left = null; this.right = null }
}
function insert(root, value) {
  if (!root) return new TreeNode(value)                        // found the empty spot
  if (value < root.value) root.left = insert(root.left, value)
  else root.right = insert(root.right, value)
  return root
}
function contains(root, value) {
  while (root) {
    if (value === root.value) return true
    root = value < root.value ? root.left : root.right         // halve the search
  }
  return false
}

let root = null
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) root = insert(root, v)
console.log(contains(root, 7), contains(root, 5))

// The three traversals — in-order gives you the values SORTED
const inorder   = n => n ? [...inorder(n.left), n.value, ...inorder(n.right)] : []
const preorder  = n => n ? [n.value, ...preorder(n.left), ...preorder(n.right)] : []
const postorder = n => n ? [...postorder(n.left), ...postorder(n.right), n.value] : []
console.log(inorder(root))
console.log(preorder(root))
console.log(postorder(root))

const height = n => n ? 1 + Math.max(height(n.left), height(n.right)) : 0
console.log(height(root))

// Level-order (BFS) — needs a queue, prints the tree row by row
function levelOrder(root) {
  const rows = []
  let level = [root]
  while (level.length) {
    rows.push(level.map(n => n.value))
    level = level.flatMap(n => [n.left, n.right].filter(Boolean))
  }
  return rows
}
console.log(levelOrder(root))

// The same recursion on a JSON-like tree: the DOM, a file system, a menu
const fs = { name: "root", children: [{ name: "a", children: [] }, { name: "b", children: [{ name: "c", children: [] }] }] }
const paths = (node, prefix = "") => [`${prefix}/${node.name}`, ...node.children.flatMap(c => paths(c, `${prefix}/${node.name}`))]
console.log(paths(fs))

class MinHeap {
  #a = []
  constructor(key = x => x) { this.#key = key }
  #key
  get size() { return this.#a.length }
  peek() { return this.#a[0] }
  push(x) {
    const a = this.#a
    a.push(x)
    let i = a.length - 1
    while (i > 0) {                                   // sift up: swap with parent while smaller
      const p = (i - 1) >> 1
      if (this.#key(a[i]) >= this.#key(a[p])) break
      ;[a[i], a[p]] = [a[p], a[i]]; i = p
    }
    return this
  }
  pop() {
    const a = this.#a
    if (!a.length) return undefined
    const top = a[0], last = a.pop()
    if (a.length) {
      a[0] = last
      let i = 0
      for (;;) {                                      // sift down: swap with the smaller child
        const l = 2 * i + 1, r = l + 1
        let m = i
        if (l < a.length && this.#key(a[l]) < this.#key(a[m])) m = l
        if (r < a.length && this.#key(a[r]) < this.#key(a[m])) m = r
        if (m === i) break
        ;[a[i], a[m]] = [a[m], a[i]]; i = m
      }
    }
    return top
  }
}

const h = new MinHeap()
for (const x of [5, 1, 8, 3, 2]) h.push(x)
console.log(h.peek(), h.size)
console.log(Array.from({ length: 5 }, () => h.pop()))     // popping repeatedly IS sorted

// Top-k without sorting everything: keep a heap of size k
function topK(nums, k) {
  const heap = new MinHeap()
  for (const n of nums) { heap.push(n); if (heap.size > k) heap.pop() }   // evict the smallest
  const out = []; while (heap.size) out.push(heap.pop())
  return out.reverse()
}
console.log(topK([72, 95, 88, 61, 99, 84, 90], 3))

// Priority queue of tasks: smallest priority first
const tasks = new MinHeap(t => t.priority)
tasks.push({ priority: 3, name: "write tests" }).push({ priority: 1, name: "fix prod" }).push({ priority: 2, name: "review PR" })
while (tasks.size) console.log(tasks.pop().name)

// Max-heap: negate the key
const mx = new MinHeap(x => -x)
for (const x of [4, 9, 2]) mx.push(x)
console.log(mx.pop())

// Merge k sorted arrays with a heap of (value, which array, index)
function mergeSorted(arrays) {
  const heap = new MinHeap(e => e[0])
  arrays.forEach((arr, i) => { if (arr.length) heap.push([arr[0], i, 0]) })
  const out = []
  while (heap.size) {
    const [v, i, j] = heap.pop()
    out.push(v)
    if (j + 1 < arrays[i].length) heap.push([arrays[i][j + 1], i, j + 1])
  }
  return out
}
console.log(mergeSorted([[1, 4, 9], [2, 3], [5, 6, 7]]))

// Undirected graph as an adjacency list
const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D"],
  F: [],            // isolated
}

function bfs(graph, start) {
  // Visit by distance. The queue holds the frontier; visited stops cycles.
  const order = [], visited = new Set([start]), queue = [start]
  let head = 0
  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)
    for (const nb of graph[node]) if (!visited.has(nb)) { visited.add(nb); queue.push(nb) }
  }
  return order
}
console.log("bfs ", bfs(graph, "A"))

function dfs(graph, start) {
  // Same shape with a stack instead of a queue — goes deep first
  const order = [], visited = new Set(), stack = [start]
  while (stack.length) {
    const node = stack.pop()
    if (visited.has(node)) continue
    visited.add(node)
    order.push(node)
    stack.push(...[...graph[node]].reverse())
  }
  return order
}
console.log("dfs ", dfs(graph, "A"))

function shortestPath(graph, start, goal) {
  // BFS, remembering how we reached each node
  const parent = new Map([[start, null]]), queue = [start]
  let head = 0
  while (head < queue.length) {
    const node = queue[head++]
    if (node === goal) {
      const path = []
      for (let n = node; n !== null; n = parent.get(n)) path.push(n)
      return path.reverse()
    }
    for (const nb of graph[node]) if (!parent.has(nb)) { parent.set(nb, node); queue.push(nb) }
  }
  return null
}
console.log(shortestPath(graph, "A", "E"), shortestPath(graph, "A", "F"))

function components(graph) {
  const seen = new Set(), groups = []
  for (const node of Object.keys(graph)) {
    if (seen.has(node)) continue
    const group = bfs(graph, node)
    group.forEach(n => seen.add(n))
    groups.push(group.sort())
  }
  return groups
}
console.log(components(graph))

// Directed graph + DFS = topological order (do tasks in dependency order)
const deps = { build: ["test"], lint: ["test"], test: ["deploy"], deploy: [] }
function topo(g) {
  const seen = new Set(), out = []
  const visit = n => {
    if (seen.has(n)) return
    seen.add(n)
    for (const m of g[n]) visit(m)
    out.push(n)                   // added AFTER everything it points to
  }
  for (const n of Object.keys(g)) visit(n)
  return out.reverse()
}
console.log(topo(deps))

function linearSearch(items, target) {
  for (let i = 0; i < items.length; i++) if (items[i] === target) return i
  return -1
}
function binarySearch(items, target) {
  let lo = 0, hi = items.length - 1, steps = 0
  while (lo <= hi) {
    steps++
    const mid = (lo + hi) >> 1
    if (items[mid] === target) return [mid, steps]
    if (items[mid] < target) lo = mid + 1        // target is in the right half
    else hi = mid - 1                            // target is in the left half
  }
  return [-1, steps]
}

const data = Array.from({ length: 1_000_000 }, (_, i) => i * 2)     // a million even numbers, sorted
console.log(linearSearch(data, 1_999_998))       // checks a million items
console.log(binarySearch(data, 1_999_998))       // 20 steps
console.log(binarySearch(data, 7))               // not there (odd)

// Lower bound: first index where items[i] >= target (insertion point)
function lowerBound(items, target) {
  let lo = 0, hi = items.length
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (items[mid] < target) lo = mid + 1; else hi = mid
  }
  return lo
}
console.log(lowerBound([1, 3, 5, 7], 5), lowerBound([1, 3, 5, 7], 4), lowerBound([1, 3, 5, 7], 99))

// Binary search on the ANSWER: smallest capacity that ships all packages in D days
const daysNeeded = (weights, cap) => weights.reduce(([days, load], w) => load + w > cap ? [days + 1, w] : [days, load + w], [1, 0])[0]
function minCapacity(weights, D) {
  let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0)
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (daysNeeded(weights, mid) <= D) hi = mid       // feasible — try smaller
    else lo = mid + 1
  }
  return lo
}
console.log(minCapacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))

function bubbleSort(input) {
  // O(n²): keep swapping neighbours until a full pass makes no swap
  const a = [...input]
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false
    for (let i = 0; i < end; i++) {
      if (a[i] > a[i + 1]) { [a[i], a[i + 1]] = [a[i + 1], a[i]]; swapped = true }
    }
    if (!swapped) break
  }
  return a
}
console.log(bubbleSort([5, 2, 9, 1, 5, 6]))

function mergeSort(a) {
  // O(n log n): split in half, sort each half, merge two sorted arrays
  if (a.length <= 1) return a
  const mid = a.length >> 1
  const left = mergeSort(a.slice(0, mid)), right = mergeSort(a.slice(mid))
  const merged = []
  let i = 0, j = 0
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) merged.push(left[i++])       // <= keeps it stable
    else merged.push(right[j++])
  }
  return [...merged, ...left.slice(i), ...right.slice(j)]
}
console.log(mergeSort([5, 2, 9, 1, 5, 6]))

// Timing: n = 2000
const data = Array.from({ length: 2000 }, () => Math.floor(Math.random() * 1e6))
const timed = fn => { const t = Date.now(); fn(); return Date.now() - t }
const bubbleMs = timed(() => bubbleSort(data)), mergeMs = timed(() => mergeSort(data)), builtinMs = timed(() => data.toSorted((x, y) => x - y))
console.log("bubbleSort:", bubbleMs > mergeMs * 3 ? "much slower than mergeSort" : "similar? (try n = 5000)")
console.log("mergeSort vs toSorted:", builtinMs <= mergeMs ? "the built-in wins — it is native code" : "close")

// What you actually write at work: a comparator, and stability
const people = [["ada", 36], ["bob", 28], ["cy", 36], ["dee", 28]]
console.log(people.toSorted((a, b) => a[1] - b[1]))                          // stable: ada before cy, bob before dee
console.log(people.toSorted((a, b) => b[1] - a[1] || a[0].localeCompare(b[0])))   // age desc, then name asc
const words = ["banana", "Apple", "cherry"]
console.log(words.toSorted(), words.toSorted((a, b) => a.localeCompare(b)))

let calls = 0
function fibNaive(n) {
  calls++
  return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2)
}
console.log(fibNaive(20), "took", calls, "calls")      // exponential — fib(20) alone is 21,891 calls

// Step 1: memoise — same code, a Map
const memo = new Map()
function fibMemo(n) {
  if (n < 2) return n
  if (!memo.has(n)) memo.set(n, fibMemo(n - 1) + fibMemo(n - 2))
  return memo.get(n)
}
console.log(fibMemo(90))

// A generic memoize wrapper (from Module 04) does the same for any function of one key
const memoize = fn => { const c = new Map(); return n => c.has(n) ? c.get(n) : (c.set(n, fn(n)), c.get(n)) }

// Step 2: bottom-up table — no recursion, O(n) time, O(1) space
function fibTable(n) {
  let a = 0, b = 1
  for (let i = 0; i < n; i++) [a, b] = [b, a + b]
  return a
}
console.log(fibTable(90))

// The same three steps on a real problem: climbing stairs, 1 or 2 steps at a time
const ways = memoize(n => n <= 1 ? 1 : ways(n - 1) + ways(n - 2))
console.log(ways(10), ways(40))

// Coin change (fewest coins) — a 1-D table where table[a] = best for amount a
function minCoins(coins, amount) {
  const best = [0, ...Array(amount).fill(Infinity)]
  for (let a = 1; a <= amount; a++)
    for (const c of coins) if (c <= a) best[a] = Math.min(best[a], best[a - c] + 1)
  return best[amount] === Infinity ? -1 : best[amount]
}
console.log(minCoins([1, 5, 10, 25], 63), minCoins([2], 3))

// Longest common subsequence — the 2-D table shape (diff tools, DNA alignment)
function lcs(a, b) {
  const t = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(0))
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      t[i][j] = a[i - 1] === b[j - 1] ? t[i - 1][j - 1] + 1 : Math.max(t[i - 1][j], t[i][j - 1])
  return t[a.length][b.length]
}
console.log(lcs("ABCBDAB", "BDCABA"))

// Kadane: max subarray sum — DP with a one-cell table
const maxSubarray = nums => nums.reduce(([best, here], x) => { here = Math.max(x, here + x); return [Math.max(best, here), here] }, [-Infinity, 0])[0]
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))