Language

TypeScript for interviews

Idioms, collections, ListNode/TreeNode, and the heap the templates actually run. Node 24.

The site’s templates are TypeScript and run as JavaScript numbers. Node on CI is 24. Each fence below is one script of erasable TypeScript: node --experimental-strip-types can run it.

number is a float64. Integers are exact through 2**53 - 1 (Number.MAX_SAFE_INTEGER). Bitwise operators see only an int32. That part lives on the bit-manipulation pattern page.

Division and remainder

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

check(Math.trunc(-3 / 2) === -1);
check(Math.floor(-3 / 2) === -2);
check(-3 % 2 === -1);
check(2 ** 53 === 2 ** 53 + 1);
check(Number.isSafeInteger(2 ** 53 - 1));
check(!Number.isSafeInteger(2 ** 53));

Math.trunc goes toward zero. Math.floor goes toward negative infinity, which is what Python’s // does. The remainder takes the sign of the dividend. There is no integer-division operator. >> is an arithmetic shift on an int32, so it is the wrong tool for dividing a negative or a value past 2**31 - 1.

Strings

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

const s = "ab,cd";
check(s[0] === "a" && s.at(-1) === "d");
check(s.slice(1, 4) === "b,c");
check([...s].reverse().join("") === "dc,ba");
check(s.split(",")[0] === "ab" && s.split(",")[1] === "cd");
check(["ab", "cd"].join(" ") === "ab cd");
check(s.replace("ab", "xy") === "xy,cd");
check(s.startsWith("ab") && s.endsWith("cd"));
check(s.indexOf("z") === -1);
check(s.includes("cd"));
check("A".charCodeAt(0) === 65 && String.fromCharCode(65) === "A");
check("ada".repeat(2) === "adaada");

s[i] is undefined past the end. s.at(-1) is the last character. indexOf returns -1 when the substring is missing. split with no separator splits on every UTF-16 code unit. Strings are immutable; replace returns a new string and replaces the first match unless you pass a global regex.

A template literal interpolates with ${expr}.

Arrays

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

const lexical = [10, 2, 1].sort();
check(same(lexical, [1, 10, 2]));
const numeric = [10, 2, 1].sort((a, b) => a - b);
check(same(numeric, [1, 2, 10]));

const row = [0, 0];
const shared = [row, row];
shared[0]![0] = 1;
check(shared[1]![0] === 1);

const rows = Array.from({ length: 2 }, () => [0, 0]);
rows[0]![0] = 1;
check(rows[1]![0] === 0);

const nums = [1, 2, 3];
nums.push(4);
check(nums.pop() === 4);
check(nums.shift() === 1);
check(nums.slice(0, 1)[0] === 2);

sort with no comparator orders by the string form, so 10 lands before 2. Pass (a, b) => a - b for ascending numbers. Modern engines keep equal elements in their original order.

Array.from({ length: n }, () => []) builds a fresh inner array per row. fill with one array object stores that same object in every slot.

push and pop are the stack ends. shift and unshift move every later element. The queue-deque template keeps indexes in an array and calls shift on the front.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];
  const res: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0]! <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]!]! <= nums[i]!) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]!]!);
  }
  return res;
}

check(same(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7]));

nums[i]! tells the type checker the index is present. It does not check at runtime. The ! in the templates sits after a length test or a write that just filled that slot.

const fixes the binding. The array or object it points at can still change.

Comparison and missing values

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

check(0 == false);
check(!(0 === false));
check((0 || 5) === 5);
check((0 ?? 5) === 0);
check(("" || "default") === "default");
check(("" ?? "default") === "");
check((null as number | null)?.toFixed === undefined);
check([1, 2, 3].at(9) === undefined);

const bag: Record<string, number> = {};
bag[1] = 4;
check(Object.keys(bag)[0] === "1");

=== compares without coercion. == coerces, so 0 == false holds. || treats 0 and "" as missing. ?? replaces only null and undefined.

A plain object’s keys are strings. Map keeps 1 and "1" apart.

?. short-circuits on null or undefined. An out-of-range index is undefined, not an exception.

Map, Set, and two-sum

This is the shape of the hashing template.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]!;
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i]!, i);
  }
  throw new Error("no solution");
}

check(same(twoSum([2, 7, 11, 15], 9), [0, 1]));

const uniq = new Set([1, 1, 2]);
check(uniq.size === 2 && uniq.has(2));
uniq.add(3);
uniq.delete(1);
check(!uniq.has(1) && uniq.has(3));

Map.get returns undefined when the key is missing. has is the membership test. Set has no index; iterate with for...of. Insertion order is preserved.

Loops and control flow

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}
function same(a: readonly number[], b: readonly number[]): boolean {
  return a.length === b.length && a.every((v, i) => v === b[i]);
}

const seen: number[] = [];
for (const [i, value] of ["a", "b"].entries()) seen.push(i);
check(same(seen, [0, 1]));

const keys: string[] = [];
for (const k in { a: 1, b: 2 }) keys.push(k);
check(keys[0] === "a" && keys[1] === "b");

let found = -1;
for (const value of [1, 3, 4]) {
  if (value % 2 === 0) {
    found = value;
    break;
  }
}
check(found === 4);

const doubled = [1, 2, 3].map((x) => x * 2);
check(same(doubled, [2, 4, 6]));
check([1, 2, 3].filter((x) => x % 2 === 1).length === 2);
check([1, 2, 3].reduce((a, b) => a + b, 0) === 6);

for...of walks values. for...in walks enumerable keys, including inherited ones on a custom prototype, so prefer Object.keys or Map when the object is data. entries() is the index-plus-value form.

map / filter / reduce allocate. A for loop keeps that cost visible when the inner body is the algorithm.

Ternary is cond ? a : b. switch compares with ===.

Functions

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

function add(a: number, b = 0): number {
  return a + b;
}
check(add(1) === 1 && add(1, 2) === 3);

const times = (n: number) => (x: number) => x * n;
check(times(3)(4) === 12);

function rest(first: number, ...more: number[]): number {
  return first + more.reduce((a, b) => a + b, 0);
}
check(rest(1, 2, 3) === 6);

const fns = [];
for (var i = 0; i < 3; i++) fns.push(() => i);
check(fns[0]!() === 3 && fns[1]!() === 3);

const bound: number[] = [];
for (let j = 0; j < 3; j++) bound.push(j);
check(bound[0] === 0 && bound[2] === 2);

A default is evaluated at the call. There is no shared mutable default the way a Python [] default is shared.

var is function-scoped; a closure over a for (var …) loop sees the final value. let and const are block-scoped. Arrow functions inherit this; a function method has its own.

Classes and this

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class Counter {
  private n: number;
  constructor(n = 0) {
    this.n = n;
  }
  inc(): number {
    return ++this.n;
  }
  get value(): number {
    return this.n;
  }
}

const c = new Counter();
check(c.inc() === 1 && c.value === 1);

class NamedCounter extends Counter {
  readonly name: string;
  constructor(name: string) {
    super(0);
    this.name = name;
  }
}
check(new NamedCounter("ticks").name === "ticks");

extends needs super(...) before this. A class field arrow inc = () => ++this.n would bind this to the instance; a prototype method does not. Parameter properties (constructor(private n = 0)) are valid TypeScript but Node’s strip-types loader does not accept them.

Destructuring

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

let a = 1, b = 2;
[a, b] = [b, a];
check(a === 2 && b === 1);

const [head, ...tail] = [1, 2, 3];
check(head === 1 && tail[0] === 2 && tail[1] === 3);

const point = { x: 3, y: 4 };
const { x, y: yy } = point;
check(x === 3 && yy === 4);

function pair([left, right]: [number, number]): number {
  return left + right;
}
check(pair([2, 5]) === 7);

Swap two bindings with [a, b] = [b, a]. Rest on an array is the leftover elements. Rename a field with y: yy. Nested patterns work on parameters too.

Math and BigInt

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

check(Math.max(1, 4, 2) === 4);
check(Math.min(...[1, 4, 2]) === 1);
check(Math.abs(-3) === 3);
check(Math.hypot(3, 4) === 5);
check(Number.isInteger(3) && !Number.isInteger(3.1));
check(Number.parseInt("08", 10) === 8);
check(1e9 + 7 === 1_000_000_007);

const wide = 2n ** 53n + 1n;
check(wide + 1n === 2n ** 53n + 2n);
check(BigInt(Number.MAX_SAFE_INTEGER) === 2n ** 53n - 1n);

Math.max with no arguments is -Infinity. Spread a non-empty array. parseInt without a radix treats a leading 0 as octal in some hosts; pass 10.

BigInt is a separate type. Mix it with number and the engine throws. Bitwise on number is still int32; use BigInt when the shift has to keep bits past 31.

Heap

The standard library has no heap. The top-K template sorts a k-sized array on every push. A binary heap is the structure that push and pop belong to. This one is a min-heap. Push the negated value for a max-heap, inside the safe integer range.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class MinHeap {
  private a: number[] = [];

  push(x: number): void {
    this.a.push(x);
    this.up(this.a.length - 1);
  }

  pop(): number {
    const a = this.a;
    if (a.length === 0) throw new Error("empty");
    const top = a[0]!;
    const last = a.pop()!;
    if (a.length > 0) {
      a[0] = last;
      this.down(0);
    }
    return top;
  }

  peek(): number {
    if (this.a.length === 0) throw new Error("empty");
    return this.a[0]!;
  }

  get size(): number {
    return this.a.length;
  }

  private up(i: number): void {
    const a = this.a;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p]! <= a[i]!) break;
      [a[p], a[i]] = [a[i]!, a[p]!];
      i = p;
    }
  }

  private down(i: number): void {
    const a = this.a;
    for (;;) {
      let smallest = i;
      const l = i * 2 + 1;
      const r = l + 1;
      if (l < a.length && a[l]! < a[smallest]!) smallest = l;
      if (r < a.length && a[r]! < a[smallest]!) smallest = r;
      if (smallest === i) break;
      [a[smallest], a[i]] = [a[i]!, a[smallest]!];
      i = smallest;
    }
  }
}

const heap = new MinHeap();
for (const x of [3, 1, 4, 2]) heap.push(x);
check(heap.pop() === 1 && heap.pop() === 2 && heap.pop() === 3 && heap.peek() === 4);

function findKthLargest(nums: number[], k: number): number {
  const h = new MinHeap();
  for (const x of nums) {
    h.push(x);
    if (h.size > k) h.pop();
  }
  return h.peek();
}

check(findKthLargest([3, 2, 1, 5, 6, 4], 2) === 5);

Binary search

The binary-search template halves with lo + ((hi - lo) >> 1). Both ends are non-negative indexes, so the shift stays inside the positive int32 range.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

function binarySearch(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}

check(binarySearch([1, 3, 3, 7], 3) === 1);
check(binarySearch([1, 3, 3, 7], 4) === -1);
check(binarySearch([], 1) === -1);

Linked lists

The linked-list template is this node plus reverse and a dummy-head merge.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

function toArray(head: ListNode | null): number[] {
  const out: number[] = [];
  while (head) {
    out.push(head.val);
    head = head.next;
  }
  return out;
}

const a = new ListNode(1, new ListNode(2, new ListNode(3)));
check(toArray(reverseList(a)).join(",") === "3,2,1");

Walk with while (cur). A dummy head keeps the merge loop from special-casing the first node. null is the empty list.

Trees

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(level);
  }
  return res;
}

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4)));
check(maxDepth(root) === 3);
check(levelOrder(root).map((row) => row.join(",")).join("|") === "1|2,3|4");

Recursion on left and right is the DFS template. Level-order snapshots q.length so the current level stays isolated from the children just pushed.

Graphs

The graph-DFS template builds number[][] adjacency. Grid flood fill is a stack of [r, c] cells.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

function countComponents(n: number, edges: [number, number][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a]!.push(b);
    adj[b]!.push(a);
  }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let v = 0; v < n; v++) {
    if (!visited[v]) {
      dfs(v);
      count++;
    }
  }
  return count;

  function dfs(v: number) {
    visited[v] = true;
    for (const u of adj[v]!) if (!visited[u]) dfs(u);
  }
}

check(countComponents(4, [[0, 1], [2, 3]]) === 2);

function floodFill(
  image: number[][], sr: number, sc: number, newColor: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === newColor) return image;
  const rows = image.length, cols = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= rows || c >= cols || image[r]![c] !== orig) continue;
    image[r]![c] = newColor;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

const filled = floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2);
check(filled[0]!.join(",") === "2,2,2" && filled[2]!.join(",") === "2,0,1");

orig === newColor is the early return that stops an infinite rewrite of the same color.

Union-Find

Path compression plus union by rank. union returns whether the two nodes were in different components.

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class UnionFind {
  parent: number[];
  rank: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]!);
    return this.parent[x]!;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra]! < this.rank[rb]!) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]!++;
    this.components--;
    return true;
  }
}

const uf = new UnionFind(4);
check(uf.union(0, 1) && uf.union(2, 3));
check(!uf.union(0, 1));
check(uf.components === 2);

Trie

function check(ok: boolean): void {
  if (!ok) throw new Error("check failed");
}

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
class Trie {
  root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isWord = true;
  }
  search(word: string): boolean {
    const node = this.walk(word);
    return Boolean(node?.isWord);
  }
  startsWith(prefix: string): boolean {
    return this.walk(prefix) != null;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | null = this.root;
    for (const ch of s) {
      if (!node!.children.has(ch)) return null;
      node = node!.children.get(ch)!;
    }
    return node;
  }
}

const t = new Trie();
t.insert("apple");
check(t.search("apple") && !t.search("app"));
check(t.startsWith("app"));

search needs isWord. startsWith only needs the walk to survive.