Free Handbook · Runs in your browser

Data Structures & Algorithms

Generic stacks, queues, linked lists, trees, heaps and graphs, plus searching, sorting and dynamic programming, built as typed classes.

0 / 105 lessons🔥 0 day streak

ShareX LinkedIn

Module 13 · what you'll be able to do

Pick a data structure from its cost table instead of by habit
Build a generic Stack, Queue, LinkedList, BinarySearchTree and MinHeap that work for any T
Use Map and Set the way a typed codebase actually uses them
Represent a graph with a typed adjacency list and trace BFS and DFS by hand
Write a generic binary search and a generic sort with a typed comparator
Turn a slow recursive solution into a fast one with a typed memo cache

The cost table, and what generics buy you here

Every structure in this module is a generic class: Stack<T>, Queue<T>, LinkedList<T>. The type parameter T means one class definition works for a stack of numbers, a stack of strings, or a stack of a project's own Order type — and the compiler still knows exactly what .pop() returns for each one, instead of everything being any. At runtime none of this exists: generics are erased along with every other type annotation, so a Stack<number> and a Stack<string> are the identical JavaScript class once compiled.

typescriptEdit it. ⌘/Ctrl + Enter runs.

function identity<T>(value: T): T {
  return value
}

class Box<T> {
  #value: T
  constructor(value: T) {
    this.#value = value
  }
  get(): T {
    return this.#value
  }
}

const numberBox = new Box<number>(42)
const stringBox = new Box<string>("hi")
console.log(identity(7), identity("seven"))
console.log(numberBox.get(), stringBox.get())

You should see

7 seven
42 hi

Your turn

Add a Box<T> method map<U>(fn: (value: T) => U): Box<U> that returns a new box holding the transformed value. Notice the method introduces its own type parameter, separate from the class's.

The type parameter never changes these costs — a Stack is exactly as fast as a Stack. Learn this table; the generic syntax around each class is the easy part.
Structure	Access	Search	Insert	Delete
`Array<T>`	O(1)	O(n)	O(1) at end / O(n) at front	O(1) at end / O(n) at front
`Stack<T>`	O(1) top only	O(n)	O(1)	O(1)
`Queue<T>`	O(1) front only	O(n)	O(1)	O(1)
`LinkedList<T>`	O(n)	O(n)	O(1) at a known node	O(1) at a known node
`Map<K, V>` / `Set<T>`	—	O(1) average	O(1) average	O(1) average
`BinarySearchTree<T>`	—	O(log n) balanced, O(n) worst	O(log n) balanced	O(log n) balanced
`MinHeap<T>` (priority queue)	O(1) minimum only	O(n)	O(log n)	O(log n)
Graph (adjacency list)	—	O(V + E) with BFS/DFS	O(1) add an edge	O(E) remove an edge

How this module is organised

Each data-structure lesson builds a generic class, runs it against two different Ts to prove it is not hard-coded to one type, then asks one interview question tied to that structure. All sixty interview questions for the exam are collected in Module 15; these are just the ones the structure itself explains best.

Stack<T>: last in, first out

A stack is a pile: add to the top, take from the top. An array-backed Stack<T> needs only push and pop on a private array — the generic part is entirely in the signatures, so the compiler knows peek() on a Stack<string> returns string | undefined, not any.

typescriptEdit it. ⌘/Ctrl + Enter runs.

class Stack<T> {
  #items: T[] = []

  push(value: T): void {
    this.#items.push(value)
  }

  pop(): T {
    if (this.#items.length === 0) throw new Error("pop from empty stack")
    return this.#items.pop() as T
  }

  peek(): T | undefined {
    return this.#items[this.#items.length - 1]
  }

  get size(): number {
    return this.#items.length
  }
}

const numbers = new Stack<number>()
numbers.push(10)
numbers.push(20)
numbers.push(30)
console.log(numbers.pop(), numbers.size, numbers.peek())

const words = new Stack<string>()
words.push("a")
words.push("b")
console.log(words.pop(), words.pop(), words.size)

You should see

30 2 20
b a 0

Your turn

Give Stack<T> a second generic method, toArray(): T[], that returns the items top-first without mutating the stack.

JuniorWhy does pop() above return T and throw, instead of returning T | undefined the way peek() does?

It is a design choice, not a rule: throwing means every caller can treat pop()'s result as a real T with no null check, which is convenient when an empty pop is truly a bug in the caller. Returning T | undefined is the safer default when an empty stack is an expected case the caller should handle — the type then forces a check at every call site instead of trusting a comment.

What they are really testing: Whether they can justify a type design decision instead of reciting that one option is always correct.

Queue<T>: a head index, not shift()

TypeScript ships no queue type. The trap is building one with Array.prototype.shift(): it removes index 0 and shifts every remaining element down, which is O(n) per call. A Queue<T> instead keeps a head index into the backing array — dequeue just reads items[head++], an O(1) operation, and the array is only compacted occasionally.

typescriptEdit it. ⌘/Ctrl + Enter runs.

class Queue<T> {
  #items: T[] = []
  #head = 0

  enqueue(value: T): void {
    this.#items.push(value)
  }

  dequeue(): T | undefined {
    if (this.#head >= this.#items.length) return undefined
    return this.#items[this.#head++]
  }

  get size(): number {
    return this.#items.length - this.#head
  }
}

const q = new Queue<string>()
q.enqueue("ada")
q.enqueue("bob")
q.enqueue("cy")
console.log(q.dequeue(), q.dequeue(), q.size)
console.log(q.dequeue(), q.dequeue())

You should see

ada bob 1
cy undefined

Your turn

Add compaction: once #head passes half the array's length, slice the consumed front off and reset #head to 0, so a long-lived queue does not grow forever.

Mid-levelWhy is Array.prototype.shift() the wrong choice for a generic Queue<T>, and what does the head-index version give up in exchange for speed?

shift() moves every remaining element one slot left, so dequeuing n items that way is O(n²) total — a BFS over a large graph becomes noticeably slower for no algorithmic reason. The head-index queue trades a small, bounded amount of wasted array space (the already-dequeued front, until compaction runs) for O(1) dequeues; it also never shrinks the backing array on its own, so a caller that enqueues far more than it ever dequeues can grow memory unexpectedly without an explicit compaction step.

What they are really testing: Whether the O(n) versus O(1) distinction is understood as a real cost, not a rule memorised without the mechanism.

LinkedList<T>: nodes and a typed next

A linked list is a chain of nodes, each holding a value and a reference to the next node. The type of that reference is the interesting part: ListNode<T>.next is ListNode<T> | null, so the compiler forces a null check before you walk the chain — the exact mistake that throws Cannot read properties of null in plain JavaScript is a compile error here instead.

typescriptEdit it. ⌘/Ctrl + Enter runs.

class ListNode<T> {
  value: T
  next: ListNode<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

class LinkedList<T> {
  #head: ListNode<T> | null = null
  #tail: ListNode<T> | null = null

  append(value: T): void {
    const node = new ListNode(value)
    if (!this.#head || !this.#tail) {
      this.#head = node
      this.#tail = node
      return
    }
    this.#tail.next = node
    this.#tail = node
  }

  toArray(): T[] {
    const out: T[] = []
    let cur = this.#head
    while (cur) {
      out.push(cur.value)
      cur = cur.next
    }
    return out
  }
}

const numbers = new LinkedList<number>()
numbers.append(1)
numbers.append(2)
numbers.append(3)
console.log(numbers.toArray().join(", "))

const names = new LinkedList<string>()
names.append("ada")
names.append("bob")
console.log(names.toArray().join(" -> "))

You should see

1, 2, 3
ada -> bob

Your turn

Add prepend(value: T): void that inserts at the head in O(1), reusing #head and #tail.

JuniorWhy is ListNode<T>.next typed as ListNode<T> | null instead of just ListNode<T>?

Every list ends somewhere, and the last node has nothing after it — typing next as always present would be a lie the compiler could not catch, and every walk to the end of the list would eventually read a property off undefined. With the union type, strictNullChecks requires a guard (while (cur)) before dereferencing cur.next, so the classic linked-list null bug becomes a compile error instead of a runtime crash.

What they are really testing: Whether they connect the type union directly to the specific runtime bug it prevents, not just recite that null checks are good practice.

Map<K, V> and Set<T>: typed hashing patterns

Map<K, V> and Set<T> are generic in the standard library already — no class to write. The type parameters matter more than they look: new Map<number, number>() means .get() returns number | undefined, not any, so the compiler forces a check before you use the result. Two of the most common interview patterns are built on exactly this.

typescriptEdit it. ⌘/Ctrl + Enter runs.

function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>()
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    const at = seen.get(complement)
    if (at !== undefined) return [at, i]
    seen.set(nums[i], i)
  }
  return null
}

const pair = twoSum([2, 7, 11, 15], 9)
console.log(pair ? pair.join(",") : "none")

function dedupe<T>(items: T[]): T[] {
  return [...new Set(items)]
}

console.log(dedupe([1, 2, 2, 3, 1, 4]).join(", "))
console.log(dedupe(["a", "b", "a", "c"]).join(", "))

You should see

0,1
1, 2, 3, 4
a, b, c

Your turn

Write a generic countBy<T, K>(items: T[], keyOf: (item: T) => K): Map<K, number> that counts items by a derived key — the typed version of the counting idiom.

Mid-levelWhy does seen.get(complement) above have to be compared with !== undefined instead of just checking if (seen.get(complement))?

The values stored are array indexes, and index 0 is falsy in JavaScript — if (seen.get(complement)) would skip a correct match at index 0, a real bug that only shows up for one specific input. Checking !== undefined (or seen.has(complement)) tests presence, not truthiness, which is what the V | undefined return type of Map.get is actually telling you to do.

What they are really testing: A classic falsy-zero trap dressed up as a type question — whether they read what Map.get truly returns instead of assuming truthy means present.

BinarySearchTree<T>: a generic comparator

A binary search tree keeps everything left of a node smaller and everything right bigger, which halves the search space each step. Making it generic means the class cannot use < directly — TypeScript has no idea how to order an arbitrary T — so BinarySearchTree<T> takes a compare: (a: T, b: T) => number function, the same contract Array.prototype.sort uses.

typescriptEdit it. ⌘/Ctrl + Enter runs.

class TreeNode<T> {
  value: T
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

class BinarySearchTree<T> {
  #root: TreeNode<T> | null = null
  #compare: (a: T, b: T) => number

  constructor(compare: (a: T, b: T) => number) {
    this.#compare = compare
  }

  insert(value: T): void {
    this.#root = this.#insertAt(this.#root, value)
  }

  #insertAt(node: TreeNode<T> | null, value: T): TreeNode<T> {
    if (!node) return new TreeNode(value)
    if (this.#compare(value, node.value) < 0) node.left = this.#insertAt(node.left, value)
    else node.right = this.#insertAt(node.right, value)
    return node
  }

  contains(value: T): boolean {
    let node = this.#root
    while (node) {
      const cmp = this.#compare(value, node.value)
      if (cmp === 0) return true
      node = cmp < 0 ? node.left : node.right
    }
    return false
  }
}

const numbers = new BinarySearchTree<number>((a, b) => a - b)
for (const v of [8, 3, 10, 1, 6, 14, 4]) numbers.insert(v)
console.log(numbers.contains(6), numbers.contains(6.5))

const names = new BinarySearchTree<string>((a, b) => a.localeCompare(b))
for (const n of ["mango", "apple", "peach"]) names.insert(n)
console.log(names.contains("apple"), names.contains("banana"))

class TreeNode<T> {
  value: T
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

class BinarySearchTree<T> {
  #root: TreeNode<T> | null = null
  #compare: (a: T, b: T) => number

constructor(compare: (a: T, b: T) => number) {
    this.#compare = compare
  }

insert(value: T): void {
    this.#root = this.#insertAt(this.#root, value)
  }

#insertAt(node: TreeNode<T> | null, value: T): TreeNode<T> {
    if (!node) return new TreeNode(value)
    if (this.#compare(value, node.value) < 0) node.left = this.#insertAt(node.left, value)
    else node.right = this.#insertAt(node.right, value)
    return node
  }

contains(value: T): boolean {
    let node = this.#root
    while (node) {
      const cmp = this.#compare(value, node.value)
      if (cmp === 0) return true
      node = cmp < 0 ? node.left : node.right
    }
    return false
  }
}

const numbers = new BinarySearchTree<number>((a, b) => a - b)
for (const v of [8, 3, 10, 1, 6, 14, 4]) numbers.insert(v)
console.log(numbers.contains(6), numbers.contains(6.5))

const names = new BinarySearchTree<string>((a, b) => a.localeCompare(b))
for (const n of ["mango", "apple", "peach"]) names.insert(n)
console.log(names.contains("apple"), names.contains("banana"))

You should see

true false
true false

Your turn

Add min(): T | undefined (keep following .left) to BinarySearchTree<T>. It works unchanged for both the number tree and the string tree above — that is the point of the comparator.

The comparator is the whole trick

Nothing about insert or contains mentions numbers or strings — every ordering decision goes through #compare. That is what makes one class generic instead of writing NumberTree and StringTree separately, and it is exactly how Array.prototype.sort, MinHeap<T> below, and most sorting libraries stay generic too.

Mid-levelWhy does BinarySearchTree<T> need a comparator function instead of just using < and > inside the class?

TypeScript generics have no built-in notion of ordering for an arbitrary type T — value < node.value only type-checks for types < is actually defined for, like number and string, and even then string comparison is by code unit, not necessarily what you want (locale-aware sorting, for example). A comparator moves that decision to the caller, who does know how their T should be ordered, the same pattern Array.prototype.sort and every generic sorting function use.

What they are really testing: Whether they understand generics constrain shape, not behaviour — T being comparable is not something the type system can assume for free.

MinHeap<T>: an array-backed priority queue

A heap is a tree stored flat in an array with one promise: index 0 is always the smallest item, by whatever comparator you give it. That makes it a priority queue — "give me the most urgent thing next" — in O(log n) per push or pop instead of resorting everything. TypeScript has no built-in heap either, so MinHeap<T> takes a comparator exactly like the BST above.

typescriptEdit it. ⌘/Ctrl + Enter runs.

class MinHeap<T> {
  #items: T[] = []
  #compare: (a: T, b: T) => number

  constructor(compare: (a: T, b: T) => number) {
    this.#compare = compare
  }

  get size(): number {
    return this.#items.length
  }

  push(value: T): void {
    const items = this.#items
    items.push(value)
    let i = items.length - 1
    while (i > 0) {
      const parent = (i - 1) >> 1
      if (this.#compare(items[i], items[parent]) >= 0) break
      ;[items[i], items[parent]] = [items[parent], items[i]]
      i = parent
    }
  }

  pop(): T | undefined {
    const items = this.#items
    if (items.length === 0) return undefined
    const top = items[0]
    const last = items.pop() as T
    if (items.length > 0) {
      items[0] = last
      let i = 0
      for (;;) {
        const left = 2 * i + 1
        const right = left + 1
        let smallest = i
        if (left < items.length && this.#compare(items[left], items[smallest]) < 0) smallest = left
        if (right < items.length && this.#compare(items[right], items[smallest]) < 0) smallest = right
        if (smallest === i) break
        ;[items[i], items[smallest]] = [items[smallest], items[i]]
        i = smallest
      }
    }
    return top
  }
}

const numbers = new MinHeap<number>((a, b) => a - b)
for (const n of [5, 1, 8, 3, 2]) numbers.push(n)
const popped: number[] = []
while (numbers.size > 0) popped.push(numbers.pop() as number)
console.log(popped.join(", "))

interface Task {
  name: string
  priority: number
}
const tasks = new MinHeap<Task>((a, b) => a.priority - b.priority)
tasks.push({ name: "write tests", priority: 3 })
tasks.push({ name: "fix prod", priority: 1 })
tasks.push({ name: "review PR", priority: 2 })
const order: string[] = []
while (tasks.size > 0) {
  const next = tasks.pop()
  if (next) order.push(next.name)
}
console.log(order.join(" -> "))

class MinHeap<T> {
  #items: T[] = []
  #compare: (a: T, b: T) => number

constructor(compare: (a: T, b: T) => number) {
    this.#compare = compare
  }

get size(): number {
    return this.#items.length
  }

push(value: T): void {
    const items = this.#items
    items.push(value)
    let i = items.length - 1
    while (i > 0) {
      const parent = (i - 1) >> 1
      if (this.#compare(items[i], items[parent]) >= 0) break
      ;[items[i], items[parent]] = [items[parent], items[i]]
      i = parent
    }
  }

pop(): T | undefined {
    const items = this.#items
    if (items.length === 0) return undefined
    const top = items[0]
    const last = items.pop() as T
    if (items.length > 0) {
      items[0] = last
      let i = 0
      for (;;) {
        const left = 2 * i + 1
        const right = left + 1
        let smallest = i
        if (left < items.length && this.#compare(items[left], items[smallest]) < 0) smallest = left
        if (right < items.length && this.#compare(items[right], items[smallest]) < 0) smallest = right
        if (smallest === i) break
        ;[items[i], items[smallest]] = [items[smallest], items[i]]
        i = smallest
      }
    }
    return top
  }
}

const numbers = new MinHeap<number>((a, b) => a - b)
for (const n of [5, 1, 8, 3, 2]) numbers.push(n)
const popped: number[] = []
while (numbers.size > 0) popped.push(numbers.pop() as number)
console.log(popped.join(", "))

interface Task {
  name: string
  priority: number
}
const tasks = new MinHeap<Task>((a, b) => a.priority - b.priority)
tasks.push({ name: "write tests", priority: 3 })
tasks.push({ name: "fix prod", priority: 1 })
tasks.push({ name: "review PR", priority: 2 })
const order: string[] = []
while (tasks.size > 0) {
  const next = tasks.pop()
  if (next) order.push(next.name)
}
console.log(order.join(" -> "))

You should see

1, 2, 3, 5, 8
fix prod -> review PR -> write tests

Your turn

Use MinHeap<T> to write topK(nums: number[], k: number): number[]: keep a heap of size k, evicting the smallest whenever it grows past k.

SeniorThe Task heap above pops in ascending priority order. How would you type and build a max-priority version without duplicating MinHeap<T>?

Do not write a second class — the comparator already fully controls ordering, so a max-heap is just a MinHeap<T> constructed with a reversed comparator: new MinHeap<Task>((a, b) => b.priority - a.priority). This is the same reason the BST and the sort function earlier both take a comparator instead of hard-coding an operator — generic code parameterised over behaviour, not just over T, avoids most of these near-duplicate classes.

What they are really testing: Whether they reach for composition (flip the comparator) over duplication as the default instinct — a real signal for how someone will structure a larger codebase.

Graphs: a typed adjacency list, BFS and DFS

A graph is nodes joined by edges — cities and roads, modules and imports, tasks and their dependencies. The universal representation is an adjacency list: here, Record<string, string[]>, a plain object where each key maps to its neighbours. BFS (a queue) explores by distance — shortest path in an unweighted graph. DFS (a stack or recursion) explores by depth — reachability, components, ordering.

typescriptEdit it. ⌘/Ctrl + Enter runs.

type Graph = Record<string, string[]>

const graph: Graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D"],
}

function bfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>([start])
  const queue: string[] = [start]
  const order: string[] = []
  let head = 0
  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor)
      }
    }
  }
  return order
}

function dfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>()
  const stack: string[] = [start]
  const order: string[] = []
  while (stack.length > 0) {
    const node = stack.pop() as string
    if (visited.has(node)) continue
    visited.add(node)
    order.push(node)
    const neighbors = [...graph[node]].reverse()
    stack.push(...neighbors)
  }
  return order
}

console.log(bfs(graph, "A").join(" -> "))
console.log(dfs(graph, "A").join(" -> "))

type Graph = Record<string, string[]>

const graph: Graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D"],
}

function bfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>([start])
  const queue: string[] = [start]
  const order: string[] = []
  let head = 0
  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor)
      }
    }
  }
  return order
}

function dfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>()
  const stack: string[] = [start]
  const order: string[] = []
  while (stack.length > 0) {
    const node = stack.pop() as string
    if (visited.has(node)) continue
    visited.add(node)
    order.push(node)
    const neighbors = [...graph[node]].reverse()
    stack.push(...neighbors)
  }
  return order
}

console.log(bfs(graph, "A").join(" -> "))
console.log(dfs(graph, "A").join(" -> "))

You should see

A -> B -> C -> D -> E
A -> B -> D -> C -> E

Your turn

Type a shortestPath(graph: Graph, start: string, goal: string): string[] | null using BFS and a Map<string, string | null> of parents, the way the JavaScript handbook's version does.

VisualizeBFS from A: the queue is the frontierStep 1 / 9

1const visited = new Set(["A"])
2const queue = ["A"]
3let head = 0
4while (head < queue.length) {
5  const node = queue[head++]
6  order.push(node)
7  for (const neighbor of graph[node])
8    if (!visited.has(neighbor)) { visited.add(neighbor); queue.push(neighbor) }
9}

Line 1

visited starts with just the source node.

Variables now

`visited`	`{A}`
`queue`	`[A]`

All 9 steps as a table

Step	Line	What happened	Variables now
1	1	visited starts with just the source node.	`visited = {A}` `queue = [A]`
2	3	head is the front-of-queue pointer. Dequeuing never calls shift() — it just moves this index.	`head = 0`
3	5	Take A off the front; head moves to 1.	`node = A` `head = 1`
4	6	Record A as visited-in-order.	`order = [A]`
5	8	A’s neighbours are B and C — both new, so mark and enqueue both.	`visited = {A, B, C}` `queue = [A, B, C]`
6	5	Take B (head 2). Its neighbours: A already seen, D is new — enqueue D.	`node = B` `head = 2` `queue = [A, B, C, D]`
7	5	Take C (head 3). Its neighbours A and D are both already seen — nothing new.	`node = C` `head = 3` `order = [A, B, C]`
8	5	Take D (head 4). E is new — enqueue it.	`node = D` `head = 4` `queue = [A, B, C, D, E]`
9	5	Take E (head 5). No new neighbours. head now equals queue.length — the loop ends.	`node = E` `head = 5` `order = [A, B, C, D, E]`

Mid-levelWhy is the graph above typed as Record<string, string[]> instead of Map<string, string[]>, and when would you prefer the Map version?

A Record is convenient to write as an object literal, prints nicely, and works with Object.keys/for...in — good for a small, fixed graph baked into code. A Map<string, string[]> is the better choice once nodes are added and removed at runtime, since Record carries prototype keys and JSON-only semantics, and Map guarantees insertion order and O(1) has/delete without those edge cases.

What they are really testing: Whether they know both representations exist for the same shape and can name a concrete reason to prefer one, not just that Map is generally newer.

A generic binary search, and a generic sort

Binary search only works on sorted data — look at the middle, discard the half the target cannot be in. Written generically, it needs a comparator for the same reason BinarySearchTree<T> did: < is not defined for an arbitrary T. A generic sort takes the same shape, so both fit the pattern (items: T[], compare: (a: T, b: T) => number) that Array.prototype.sort itself uses.

typescriptEdit it. ⌘/Ctrl + Enter runs.

function binarySearch<T>(items: T[], target: T, compare: (a: T, b: T) => number): number {
  let lo = 0
  let hi = items.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    const cmp = compare(items[mid], target)
    if (cmp === 0) return mid
    if (cmp < 0) lo = mid + 1
    else hi = mid - 1
  }
  return -1
}

const numCompare = (a: number, b: number) => a - b
const sorted = [1, 3, 5, 7, 9, 11, 13]
console.log(binarySearch(sorted, 9, numCompare), binarySearch(sorted, 4, numCompare))

function quickSort<T>(items: T[], compare: (a: T, b: T) => number): T[] {
  if (items.length <= 1) return items
  const [pivot, ...rest] = items
  const less = rest.filter(x => compare(x, pivot) < 0)
  const equal = [pivot]
  const greater = rest.filter(x => compare(x, pivot) >= 0)
  return [...quickSort(less, compare), ...equal, ...quickSort(greater, compare)]
}

console.log(quickSort([5, 2, 9, 1, 5, 6], numCompare).join(", "))

const words = ["banana", "apple", "cherry"]
console.log(quickSort(words, (a, b) => a.localeCompare(b)).join(", "))

function binarySearch<T>(items: T[], target: T, compare: (a: T, b: T) => number): number {
  let lo = 0
  let hi = items.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    const cmp = compare(items[mid], target)
    if (cmp === 0) return mid
    if (cmp < 0) lo = mid + 1
    else hi = mid - 1
  }
  return -1
}

const numCompare = (a: number, b: number) => a - b
const sorted = [1, 3, 5, 7, 9, 11, 13]
console.log(binarySearch(sorted, 9, numCompare), binarySearch(sorted, 4, numCompare))

function quickSort<T>(items: T[], compare: (a: T, b: T) => number): T[] {
  if (items.length <= 1) return items
  const [pivot, ...rest] = items
  const less = rest.filter(x => compare(x, pivot) < 0)
  const equal = [pivot]
  const greater = rest.filter(x => compare(x, pivot) >= 0)
  return [...quickSort(less, compare), ...equal, ...quickSort(greater, compare)]
}

console.log(quickSort([5, 2, 9, 1, 5, 6], numCompare).join(", "))

const words = ["banana", "apple", "cherry"]
console.log(quickSort(words, (a, b) => a.localeCompare(b)).join(", "))

You should see

4 -1
1, 2, 5, 5, 6, 9
apple, banana, cherry

Your turn

Write lowerBound<T>(items: T[], target: T, compare: (a: T, b: T) => number): number: the first index where compare(items[i], target) >= 0, using the exclusive-hi style of binary search. Useful for insertion points.

Mid-levelBoth binarySearch and quickSort above take a compare: (a: T, b: T) => number parameter. What would go wrong if they instead took a generic constraint like <T extends number> to allow direct < comparisons?

Constraining T to number would work for numbers, but it throws away the entire point of writing the function generically — it could no longer sort strings, objects by a field, or anything that needs locale-aware or multi-key comparison, forcing a second near-identical function for every other orderable type. The comparator keeps the algorithm itself (the loop, the recursion) generic over any T, while pushing the one type-specific decision — how to order two values — out to the caller, who is the only one who actually knows.

What they are really testing: Whether they can articulate why a comparator is the more general design, not just that it happens to be what the standard library does.

Dynamic programming: a typed memo cache

Dynamic programming is one idea: if you will need the answer to a sub-problem more than once, save it. Start from the obviously-correct recursive solution, notice it recomputes the same calls, and add a Map<number, number> cache keyed by the argument — memoisation. Fibonacci is the smallest example; the shape (a cache typed by the sub-problem's key) is the same for coin change, edit distance and every DP problem after it.

typescriptEdit it. ⌘/Ctrl + Enter runs.

function fibNaive(n: number): number {
  return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2)
}

const cache = new Map<number, number>()
function fibMemo(n: number): number {
  if (n < 2) return n
  const cached = cache.get(n)
  if (cached !== undefined) return cached
  const result = fibMemo(n - 1) + fibMemo(n - 2)
  cache.set(n, result)
  return result
}

console.log(fibNaive(10), fibMemo(10))
console.log(fibMemo(40))
console.log(cache.size)

You should see

55 55
102334155
39

Your turn

Write a generic memoize<T>(fn: (n: number) => T): (n: number) => T that wraps any single-number-argument function in its own Map<number, T> cache, then use it in place of the hand-written fibMemo.

How to recognise a DP problem

The words minimum / maximum / how many ways / longest / is it possible, an input that shrinks by one step at a time, and a choice at each step. Type the cache as Map<Key, Result> for whatever the sub-problem's key actually is — a number for Fibonacci or coin change, a string like `${i},${j}` for a two-index problem such as longest common subsequence.

Mid-levelWhy is fibMemo's cache typed as Map<number, number> specifically, rather than reused for a differently-shaped DP problem later in the same file?

The cache's key and value types are part of the contract for this specific sub-problem — Fibonacci's sub-problems are identified by a single number and produce a number, but a two-dimensional problem like edit distance needs a key that encodes two indices, so its cache would be typed Map<string, number> with a composite key like `${i},${j}`, or a nested Map<number, Map<number, number>>. Reusing one cache across problems would either not compile (wrong key/value types) or, worse, silently return a cached answer for the wrong sub-problem if the key shapes ever coincided.

What they are really testing: Whether they think about the cache key as part of the problem's type, not just “add a Map” as a memorised trick.

← Module 12TypeScript + Tools Module 14 →Problem Solving

Finish the TypeScript handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.