Algorithms You Write

// debounce: run after the input goes quiet for `wait` ms. one timer, reset on every call
function debounce(fn, wait) {
  let timer = null, lastArgs
  const run = () => { timer = null; fn(...lastArgs) }
  const d = (...args) => { lastArgs = args; clearTimeout(timer); timer = setTimeout(run, wait) }   // O(1) per call; one pending timer
  d.cancel = () => { clearTimeout(timer); timer = null }
  d.flush = () => { if (timer) { clearTimeout(timer); run() } }
  return d
}
// cost model: the closure holds lastArgs until it fires (retention of the last payload). cancel on unmount.

// throttle: run at most once per `wait` ms, with the trailing call delivered. a timestamp and one timer
function throttle(fn, wait) {
  let last = 0, timer = null, lastArgs
  return (...args) => {
    lastArgs = args; const now = Date.now(); const remaining = wait - (now - last)
    if (remaining <= 0) { clearTimeout(timer); timer = null; last = now; fn(...args) }           // leading edge
    else if (!timer) timer = setTimeout(() => { last = Date.now(); timer = null; fn(...lastArgs) }, remaining)  // trailing edge
  }
}
// rAF throttle for visual work: coalesce to one call per frame; the browser course part 6 has why
function rafThrottle(fn) { let id = null, a; return (...args) => { a = args; if (id === null) id = requestAnimationFrame(() => { id = null; fn(...a) }) } }
// which: debounce for "when they stop" (search-as-you-type, resize end, autosave); throttle for "while they do it" (scroll position, drag, progress)

// search over 50,000 records, three tiers of effort
// 1. linear filter: O(n × query) per keystroke. fine to ~10k short records; debounce it
const hits = records.filter(r => r.name.toLowerCase().includes(q))

// 2. inverted index: token → Set of record ids. build O(total tokens); query O(hits) per token, intersected
const index = new Map()                                   // 'ade' → Set{12, 977, …}
for (const r of records) for (const t of tokenize(r.name)) (index.get(t) ?? index.set(t, new Set()).get(t)).add(r.id)
const hits = intersect(tokenize(q).map(t => index.get(t) ?? new Set()))   // smallest set first

// 3. prefix search: a trie over tokens, or a sorted token array with two binary searches for the range [q, q + '￿')
const tokens = allTokens.sort()                           // once
const lo = lowerBound(tokens, q), hi = lowerBound(tokens, q + '￿')   // O(log n) each; tokens[lo..hi) share the prefix

// ranking: score = Σ (field weight × match quality): exact > prefix > substring > fuzzy; recency and popularity as tie-breakers
// fuzzy (part 9): bitap for short patterns, edit distance ≤ 2 via a precomputed deletion index (SymSpell) for speed
// libraries: MiniSearch, FlexSearch, Fuse.js (fuzzy, slower), Lunr. all build one of the above

// sorting at UI scale: Array.prototype.sort is TimSort (stable, O(n log n), adaptive: near-sorted input is ~O(n))
rows.sort((a, b) => a.price - b.price)                          // 100k rows: ~15 ms. 1k rows: ~0.1 ms
// the comparator runs n log n times: ~1.7M calls for 100k. keep it allocation-free and monomorphic:
rows.sort((a, b) => a.name.localeCompare(b.name))              // localeCompare per call: ~10× slower than a numeric compare
const collator = new Intl.Collator('en', { sensitivity: 'base' })
rows.sort((a, b) => collator.compare(a.name, b.name))          // one collator; ~3× faster than localeCompare per call
// precompute the sort key once when it is expensive (a normalised string, a parsed date), then compare keys:
const keyed = rows.map(r => [normalise(r.name), r]); keyed.sort((a, b) => a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0)
// multi-column: compare the first field, then the next on ties. stable sort means: sort by the secondary first, then the primary also works
// when NOT to sort: on every keystroke over 100k (sort once, filter the sorted array: filter preserves order); when only top-k is shown (a heap)
// toSorted() returns a copy (ES2023); sort() is in place and returns the same array (a mutation React will not see)

// graph traversal in a UI: dependencies (build graphs, form field dependencies, derived state), layout (trees), routing
// adjacency as Map<node, Set<node>>; BFS with a queue (shortest path in hops), DFS with a stack or recursion (reachability, ordering)
function topoSort(deps) {                                  // Kahn's algorithm: O(V + E). detects cycles
  const indeg = new Map(), order = []
  for (const [n, outs] of deps) { indeg.set(n, indeg.get(n) ?? 0); for (const m of outs) indeg.set(m, (indeg.get(m) ?? 0) + 1) }
  const q = [...indeg].filter(([, d]) => d === 0).map(([n]) => n)
  while (q.length) { const n = q.shift(); order.push(n); for (const m of deps.get(n) ?? []) { indeg.set(m, indeg.get(m) - 1); if (indeg.get(m) === 0) q.push(m) } }
  if (order.length !== indeg.size) throw new Error('cycle')
  return order
}
// where: computed/derived state (recompute in topological order so each node sees fresh inputs: signals do this incrementally),
// module graphs (part 8's tree shaking is reachability from entries), component trees (DFS = render order), undo graphs
// q.shift() is O(n) on arrays; for large graphs use an index pointer (let head = 0; q[head++]) to keep BFS O(V + E)