Cheat sheets

The file to keep open. Everything here appears elsewhere in the guide with explanation; this is the lookup version. Grouped so you can find things by what you are trying to do rather than by topic.

Table of contents

• 1. Complexity at a glance
• 2. Python quick reference
• 3. TypeScript and JavaScript quick reference
• 4. Side-by-side: the same thing in both languages
• 5. Algorithm templates
• 6. Data structure choice
• 7. The trap list
• 8. Interview phrasebook

1. Complexity at a glance

Growth and what fits in one second

Node’s tight numeric loop is ~30x faster than CPython’s. That gap is why the same O(n^2) solution passes in JS and times out in Python.

Reading the constraint

graph TD
    Start["Constraint on n?"] --> Q1{"n ≤ 12"}
    Q1 -->|yes| R1["O(n!)<br/>permutations / brute force"]
    Q1 -->|no| Q2{"n ≤ 20"}
    Q2 -->|yes| R2["O(2^n)<br/>bitmask over subsets"]
    Q2 -->|no| Q3{"n ≤ 500"}
    Q3 -->|yes| R3["O(n^2) or O(n^3)<br/>nested loops, DP"]
    Q3 -->|no| Q4{"n ≤ 1e5"}
    Q4 -->|yes| R4["O(n log n)<br/>sort, heap, divide-and-conquer"]
    Q4 -->|no| Q5{"n ≤ 1e6"}
    Q5 -->|yes| R5["O(n)<br/>single linear pass"]
    Q5 -->|no| R6["O(log n) or O(1)<br/>binary search, preprocessing"]

Recursion limits (measured)

Rule: if n can exceed 1,000 (Python) or 10,000 (Node), write it iteratively.

The doubling test

Double n and look at the ratio. log2(ratio) is the empirical exponent.

2. Python quick reference

Built-in complexity

The imports

from collections import deque, defaultdict, Counter, OrderedDict, ChainMap, namedtuple
from heapq import heappush, heappop, heapify, heappushpop, heapreplace, nlargest, nsmallest, merge
from bisect import bisect_left, bisect_right, insort
from itertools import (accumulate, pairwise, groupby, product, permutations, combinations,
                       chain, islice, tee, cycle, count, zip_longest, starmap)
from functools import cache, lru_cache, reduce, partial, cmp_to_key, cached_property, singledispatch
from dataclasses import dataclass, field, replace
from typing import Optional, Literal, Protocol, TypeVar, Self, TypedDict, NamedTuple
import math, sys, re, operator

The idioms

# containers
grid = [[0]*n for _ in range(m)]              # NOT [[0]*n]*m — that aliases
graph = defaultdict(list)
counts = Counter(items)
seen = set()

# queues and heaps
q = deque([start]); q.append(x); q.popleft()
window = deque(maxlen=k)                       # bounded: appending drops from the front
heappush(h, (priority, next(counter), item))   # counter breaks ties so item is never compared
heappush(h, -value)                            # max-heap by negation (3.14 adds heappush_max)

# sorting
xs.sort(key=lambda r: (-r.score, r.name))      # desc then asc
xs.sort(key=operator.itemgetter(1))            # ~30% faster than the lambda: stays in C
xs.sort(key=cmp_to_key(cmp))                   # last resort

# bisect: five answers from two functions
i = bisect_left(a, x)                          # lower bound / ceil index / rank
j = bisect_right(a, x)                         # upper bound
count = j - i                                  # occurrences of x
floor_idx = bisect_left(a, x) - 1

# strings
''.join(parts)                                 # the reliable linear builder
s.startswith(('a', 'b'))                       # accepts a tuple
s.split()                                      # splits on whitespace runs AND strips
'{:.2f}'.format(x); f'{x:.2f}'; f'{x=}'        # f-string debug form (3.8+)
s.translate(str.maketrans(a, b))               # fast char substitution

# iteration
for i, v in enumerate(xs, start=1): ...
for a, b in zip(xs, ys, strict=True): ...      # strict= is 3.10+
for a, b in pairwise(xs): ...                  # adjacent pairs, 3.10+
for x in reversed(xs): ...
list(accumulate(xs))                           # prefix sums
list(accumulate(xs, initial=0))                # with the 0 prefix — usually what DP wants

# numbers
divmod(a, b); a // b; -7 // 2 == -4            # floor division, NOT truncation
math.isqrt(n); math.comb(n, k); math.gcd(*xs); math.prod(xs)
float('inf'); float('-inf')
n.bit_length(); n.bit_count()                  # bit_count is 3.10+
int('ff', 16); bin(5); hex(255); f'{5:08b}'

# unpacking
first, *rest = xs
a, b = b, a                                    # whole RHS evaluated first
*_, last = xs
d = {**d1, **d2}; d = d1 | d2                  # 3.9+

# comprehensions
{k: v for k, v in pairs if v}
[y for x in xs for y in x]                     # flatten (loops read left to right)
next((x for x in xs if pred(x)), None)         # first match or None
any(pred(x) for x in xs); all(...)             # short-circuit

# memoization
@cache
def dp(i, j): ...                              # arguments must be hashable

Modern Python by version

3. TypeScript and JavaScript quick reference

Built-in complexity

The idioms

// containers
const grid = Array.from({ length: m }, () => new Array<number>(n).fill(0));   // packed, no aliasing
const seen = new Set<string>();
const counts = new Map<string, number>();
counts.set(k, (counts.get(k) ?? 0) + 1);
const groups = Object.groupBy(items, x => x.kind);        // ES2024
const byTeam = Map.groupBy(items, x => x.teamId);         // any key type

// queue: NEVER shift()
const q = [start]; for (let head = 0; head < q.length; head++) { const v = q[head]!; /* ... */ }

// sorting
xs.sort((a, b) => a - b);                                  // numbers — the default is lexicographic!
xs.sort((a, b) => b.score - a.score || a.name.localeCompare(b.name));   // multi-key via ||
const coll = new Intl.Collator('es', { numeric: true }); xs.sort(coll.compare);
const sorted = xs.toSorted((a, b) => a - b);               // non-mutating

// strings
[...str]                                                   // code POINTS (handles emoji)
str.length                                                 // code UNITS
str.at(-1); str.replaceAll(a, b); str.padStart(2, '0')

// iteration
for (const [i, v] of xs.entries()) {}
for (const k of map.keys()) {}
xs.flatMap(f); xs.flat(Infinity); xs.at(-1); xs.findLast(p);
xs.reduce((acc, v) => acc + v, 0);
naturals().map(f).filter(p).take(5).toArray();             // lazy iterator helpers (ES2026)

// numbers and bits
Math.trunc(-7 / 2) === -3;  Math.floor(-7 / 2) === -4;     // JS / truncates toward zero via trunc
(a + b) >>> 1                                              // unsigned mid
32 - Math.clz32(n)                                         // bit length
Math.imul(a, b)                                            // 32-bit multiply
x >>> 0                                                    // force unsigned — matters for hashing
Number.isInteger, Number.MAX_SAFE_INTEGER, Number.EPSILON
BigInt(n); 10n ** 30n

// objects
Object.hasOwn(o, k); Object.create(null);                   // dictionary with no prototype
Object.fromEntries(map); Object.entries(o);
const { a = 1, b: { c } = {}, ...rest } = obj;
obj?.a?.[0]?.(); opts.retries ??= 3;

// async
await Promise.all([a(), b()]);                             // parallel
for (const x of xs) await f(x);                            // sequential — usually not what you want
await Promise.allSettled(ps);                              // never rejects
AbortSignal.timeout(1000); AbortSignal.any([s1, s2]);
using conn = open();                                       // Symbol.dispose (ES2026)

TypeScript type quick reference

// narrowing
if (typeof x === 'string') {}
if (x instanceof Date) {}
if ('kind' in x) {}
if (x != null) {}                                          // != catches null AND undefined
function isT(x: unknown): x is T { ... }                   // type guard
function assertT(x: unknown): asserts x is T { ... }        // assertion function
default: { const _e: never = x; }                          // exhaustiveness

// utilities
Partial<T> Required<T> Readonly<T> Record<K,V> Pick<T,K> Omit<T,K>
Exclude<T,U> Extract<T,U> NonNullable<T> Awaited<T> NoInfer<T>
Parameters<F> ReturnType<F> ConstructorParameters<C> InstanceType<C>
Uppercase<S> Lowercase<S> Capitalize<S> Uncapitalize<S>

// the ones you write yourself
type Prettify<T> = { [K in keyof T]: T[K] } & {};
type DeepPartial<T> = T extends object ? { [K in keyof T]?: DeepPartial<T[K]> } : T;
type Mutable<T> = { -readonly [K in keyof T]: T[K] };
type UnionToIntersection<U> = (U extends any ? (x: U) => void : never) extends (x: infer I) => void ? I : never;
type IsNever<T> = [T] extends [never] ? true : false;
type IsAny<T> = 0 extends (1 & T) ? true : false;

// the three ways to attach a type
const a: Config = v;              // annotation — widens to Config
const b = v satisfies Config;     // check, keep the narrow inferred type   <- usually what you want
const c = v as Config;            // assertion — can lie

// key facts
// - method-shorthand params are BIVARIANT; function-property params are CONTRAVARIANT
// - arrays are covariant (unsound); use readonly T[] when you only read
// - conditional types distribute over naked type params; wrap in [T] to stop it
// - interface can merge and reports extends conflicts eagerly; type & defers to never

Modern JS/TS by version

Node 22 availability (feature-detected): iterator helpers, Set methods, Object.groupBy, Array.fromAsync, Symbol.dispose, toSorted family — yes. Promise.try, RegExp.escape, Error.isError, Float16Array, Math.sumPrecise, Temporal, Map.getOrInsert — no.

4. Side-by-side: the same thing in both languages

5. Algorithm templates

Binary search — two templates, and everything derives from them

# exact match, inclusive bounds
lo, hi = 0, len(a) - 1
while lo <= hi:
    m = lo + (hi - lo) // 2
    if a[m] == t: return m
    if a[m] < t: lo = m + 1
    else: hi = m - 1
return -1

# boundary / first-true, exclusive upper bound  <- default to this one
lo, hi = 0, len(a)
while lo < hi:
    m = (lo + hi) // 2
    if a[m] < t: lo = m + 1      # `<` -> lower_bound;  `<=` -> upper_bound
    else: hi = m
return lo

# binary search the ANSWER (monotone predicate)
lo, hi = min_possible, max_possible
while lo < hi:
    m = lo + (hi - lo) // 2
    if feasible(m): hi = m
    else: lo = m + 1
return lo

Sliding window

left = 0
for right, v in enumerate(a):
    add(v)
    while invalid():                 # for LONGEST: shrink while invalid, record AFTER
        remove(a[left]); left += 1
    best = max(best, right - left + 1)

left = 0
for right, v in enumerate(a):
    add(v)
    while valid():                   # for SHORTEST: shrink while valid, record INSIDE
        best = min(best, right - left + 1)
        remove(a[left]); left += 1

Monotonic stack

st = []
for i, v in enumerate(a):
    while st and a[st[-1]] < v:      # `<` -> next greater;  `>` -> next smaller
        j = st.pop()
        answer[j] = ...              # the POP is when you learn j's answer
    st.append(i)

BFS / DFS / topological sort

# BFS with levels
q = deque([start]); seen = {start}; dist = {start: 0}
while q:
    v = q.popleft()
    for n in adj[v]:
        if n not in seen:
            seen.add(n); dist[n] = dist[v] + 1; q.append(n)

# BFS by explicit levels (for "minutes elapsed" style answers)
while q:
    for _ in range(len(q)):
        v = q.popleft(); ...
    steps += 1

# iterative DFS
st = [start]; seen = set()
while st:
    v = st.pop()
    if v in seen: continue
    seen.add(v)
    st.extend(n for n in adj[v] if n not in seen)

# Kahn topological sort
indeg = [0]*n
for u, v in edges: adj[u].append(v); indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0); order = []
while q:
    v = q.popleft(); order.append(v)
    for nx in adj[v]:
        indeg[nx] -= 1
        if indeg[nx] == 0: q.append(nx)
return order if len(order) == n else None    # None -> cycle

Dijkstra

dist = {s: 0}; pq = [(0, s)]
while pq:
    d, v = heappop(pq)
    if d > dist.get(v, inf): continue        # stale entry
    for n, w in adj[v].items():
        nd = d + w
        if nd < dist.get(n, inf):
            dist[n] = nd; heappush(pq, (nd, n))

Union-Find

parent = list(range(n)); size = [1]*n
def find(x):
    while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
    return x
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False                # already connected -> a cycle
    if size[ra] < size[rb]: ra, rb = rb, ra
    parent[rb] = ra; size[ra] += size[rb]
    return True

Backtracking

def go(state):
    if is_solution(state): res.append(snapshot(state)); return
    if cannot_lead_anywhere(state): return       # PRUNE — this is where the speed is
    for choice in choices(state):
        if i > start and choice == prev: continue    # skip duplicate SIBLINGS
        apply(choice)
        go(state)
        undo(choice)

DP

# top-down: write the brute force, then add one decorator
@cache
def dp(i, j):
    if base_case: return base_value
    return best(dp(i-1, j), dp(i, j-1) + cost)

# 0/1 knapsack: capacity loop BACKWARD
for w, v in items:
    for c in range(cap, w-1, -1): dp[c] = max(dp[c], dp[c-w] + v)

# unbounded: capacity loop FORWARD
for c in range(1, cap+1):
    for w, v in items:
        if w <= c: dp[c] = max(dp[c], dp[c-w] + v)

# count COMBINATIONS: item loop outside.  count PERMUTATIONS: target loop outside.

Tree recursion

def go(node):
    if not node: return identity
    left, right = go(node.left), go(node.right)
    best[0] = max(best[0], combine_through(node, left, right))   # global answer
    return report_upward(node, left, right)                       # what the parent can use

6. Data structure choice

7. The trap list

Everything here has been measured or compiler-verified elsewhere in this guide.

Both languages

• Nested loop where the inner pointer never resets is O(n), not O(n^2). Count total iterations.
• x in list inside a loop is the most common accidental O(n^2). Hoist to a set — measured 250x at n=4000.
• Recursion over n > 1,000 (Python) or n > 10,000 (Node) overflows. Go iterative.
• Slicing/spreading inside a loop adds a hidden O(n) factor. Pass indices.
• Validating a BST against immediate children only. Use in-order or (lo, hi) bounds.
• Dijkstra with a negative edge is silently wrong, not an error.
• Floyd-Warshall needs k as the outermost loop.
• 0/1 knapsack needs the capacity loop backward.
• Prefix-sum counting needs the seen[0] = 1 seed.
• Dedup in backtracking uses i > start, not i > 0.
• Marking BFS visited on dequeue instead of enqueue makes the queue O(E).

Python-specific

• list.pop(0) / insert(0, x) is O(n) — measured 145x slower than deque at n=32k.
• [[0]*n]*m aliases one inner list.
• s += x in a loop is linear only when s is a local with refcount 1. ''.join always.
• bisect.insort is O(n) — building a sorted list with it is O(n^2).
• Mutable default arguments are created once, at definition.
• defaultdict creates the key when you read it. Use .get() to peek.
• Bare except: swallows KeyboardInterrupt, SystemExit, CancelledError.
• @lru_cache on a method keeps every self alive forever.
• return inside finally discards the exception and the original return value.
• -7 // 2 == -4 (floors), not -3.
• Counter subtraction clamps at 0; use .subtract() for negatives.
• itertools.groupby groups only consecutive equal keys — sort first.
• Mutating a list while iterating it forward silently skips elements.

JavaScript / TypeScript-specific

• [10, 9, 1].sort() is [1, 10, 9] — the default comparator is lexicographic.
• arr.shift() is O(n). Use a head cursor.
• delete arr[i] creates a hole and permanently deoptimizes the array (measured 40% slower).
• new Array(n) without .fill() is holey from birth.
• Array(n).fill([]) shares one inner array.
• await inside forEach does nothing — forEach ignores the returned promise.
• for await over an array of promises is sequential; Promise.all is parallel.
• parseInt('08') is fine now, but parseInt(x, 10) is still the habit; Number(x) for full strings.
• typeof null === 'object'; NaN !== NaN; 0.1 + 0.2 !== 0.3.
• str.length counts UTF-16 code units — '😀'.length === 2. Use [...str].
• Bitwise operators coerce to 32-bit signed. x >>> 0 for unsigned; missing it caused real false negatives in the Bloom filter in this guide.
• Object.keys returns integer-like keys first, in ascending numeric order.
• An object used as a dictionary with churning keys goes into slow dictionary mode — use Map.
• Method-shorthand parameters are bivariant; declare callbacks as properties for contravariant checking.
• Arrays are covariant in TypeScript — readonly T[] when you only read.
• Omit is not homomorphic: Omit on a tuple gives you an object.

8. Interview phrasebook

Sentences that carry signal. Say the underlined idea, not the word.

Opening

• “Before I code — what’s the size of n, can the input have duplicates or negatives, and am I allowed to mutate it?”
• “Let me restate: given X, return Y, and the constraint is Z. Is that right?”

Choosing an approach

• “The brute force is O(n^2) because it recomputes the sum for every window. The redundancy is the overlap, so a sliding window removes it.”
• “This is contiguous plus a monotone constraint, so sliding window. If the values could be negative the window stops being monotone and I’d switch to prefix sums with a hash map.”
• “I’m using a heap rather than a sort because I only need the extremum, not the order.”
• “I’m using a Map rather than an object because the keys are dynamic.”
• “n <= 20 in the constraints, so I’m reading that as bitmask over subsets.”

Complexity

• “n is the number of nodes and m the number of edges. Time O(n + m), space O(n) for the queue.”
• “Each element is pushed and popped at most once, so the total work in the while loop is O(n) even though it’s nested.”
• “That’s Theta(n log n) and it’s tight — the sort dominates and I can’t avoid needing the order.”
• “The n log n is only from sorting. If the input arrived sorted this would be linear.”
• “Amortized O(1), not worst-case O(1) — one insert can still trigger an O(n) resize, which matters if you have a latency budget.”

Trade-offs

• “Two options: quickselect is O(n) expected but mutates the input; a size-k heap is O(n log k) and works on a stream. Which matters more here?”
• “I’d ship the O(n^2) version if n is under a few thousand — it’s half the code and much easier to get right.”
• “This is O(1) expected. The worst case is O(n) with adversarial keys, which is a real DoS vector, and the mitigation is a randomized hash seed.”

When stuck

• “Let me try a small example by hand and see what the answer should be.”
• “I know how to do this in O(n^2). Let me get that correct first and then optimize.”
• “What I need is ‘the nearest larger element to the right’ — that’s a monotonic stack.”
• “I’m not sure this greedy is safe. Let me look for a counterexample.” (Then find one, or argue the exchange.)

Answering “can you do better?”

• “Not asymptotically — any comparison-based approach is Omega(n log n) by the decision-tree argument. But if the keys are bounded integers, counting sort makes it O(n + k).”
• “Yes: the repeated max is the bottleneck, and a monotonic deque makes it O(1) amortized instead of O(k).”
• “Only with different assumptions — O(1) if I can preprocess, or O(log n) if I keep it sorted as it arrives.”

Closing

• “Edge cases I’d test: empty input, one element, all equal, all distinct, and the maximum n.”
• “If this were production code I’d add [X], and the thing most likely to break is [Y].”

Next: Study plan and flashcards, or back to the index.