CS Foundations cheat sheet

• Pipeline: parse, bytecode (Ignition), then optional machine-code tiers (Sparkplug, Maglev, TurboFan).
• A JIT compiles hot code while the program runs, guessing types. A broken guess is a deopt: back to the interpreter.
• Keep types and object shapes stable in hot code. Profile before you worry.
• Local test: the same loop took 388 ms with the JIT and 2454 ms with --jitless.

Stack

One frame per active call: arguments, locals, return place

Heap

Objects, arrays, closures. Variables hold references to them

Stack overflow

RangeError: about 12,500 frames (1 arg), 5,000 (6 args) locally

Pass by value

For objects the value is a reference (call by sharing)

Garbage collection

Frees what is unreachable from roots. A forgotten cache still leaks

Typed array

Flat bytes outside the JS heap. Several views can share one buffer

Watch out: V8 has no tail call optimisation. A correct recursive DFS on 100,000 nodes can still crash. Use an explicit stack.

Tip: Remember the ratios, not the digits. Each level down is roughly 10 to 100 times slower.

• Memory loads in 64-byte cache lines, so one Float64Array read brings 8 neighbours.
• Spatial locality: use neighbours. Temporal locality: reuse a value soon.
• 4096 x 4096 matrix: 37 ms row by row, 314 ms column by column. A 512 KB matrix showed only 1.2x.
• Random access cost about 11 times sequential. One field of 2 million records: 4.5 ms struct of arrays, 21 ms array of objects.

for (let r = 0; r < n; r++)
  for (let c = 0; c < n; c++)
    sum += m[r * n + c];

• 0.1 + 0.2 is 0.30000000000000004: 1/10 is a repeating fraction in binary.
• Integers are exact up to 2**53 - 1. Gaps between doubles grow with the size.
• Number.EPSILON is 2^-52, valid near 1 only.

const near = (a, b, eps = 1e-9) =>
  Math.abs(a - b) <=
  eps * Math.max(1, Math.abs(a),
                 Math.abs(b));

NaN

Never equals itself. Use Number.isNaN(x)

0 and -0

0 === -0 but Object.is(0, -0) is false

(1.005).toFixed(2)

"1.00": stored as 1.00499999999999989

Math.floor((0.1+0.7)*10)

7, not 8. Use Math.round

Float addition

Not associative: order changes last digits

sort((a, b) => a - b)

Breaks on NaN: the comparator returns NaN

Tip: Money: integer cents, round once on the way in, give the remainder to a part when splitting. BigInt for huge values. IDs past 2^53 travel as strings.

• "😀".length is 2 (surrogate pair). [...s] goes by code point, Intl.Segmenter by grapheme.
• UTF-8 uses 1 to 4 bytes: 0xxxxxxx, 110xxxxx 10xxxxxx, and so on. ASCII is unchanged.

s.normalize("NFC")

Compare and store text in this form

NFKC

Loose match only: fi to fi, ① to 1. Loses data

new Intl.Collator(loc)

Sort for users. Default sort() uses code units

TextDecoder fatal: true

Throw on bad bytes instead of silent U+FFFD

s.isWellFormed()

False when a lone surrogate exists

Watch out: Mojibake (café) is a wrong decode: fix the declared encoding. Truncate on grapheme boundaries, never mid-pair. split("").reverse() breaks emoji.

• Bitwise operators use 32-bit signed ints: 1 << 32 is 1, 1 << 31 is negative, >>> 0 makes unsigned.
• >> keeps the sign, >>> fills with zeros. -1 >>> 1 is 2147483647.
• Two's complement: -x === ~x + 1. Signed 8-bit range is -128 to 127.

Watch out: Odd test: x % 2 === 1 fails for -7. Use x % 2 !== 0 or (x & 1) === 1. Wrap bitwise ops in parentheses.

• C(n, k) = C(n-1, k-1) + C(n-1, k). MISSISSIPPI: 11! / (4! 4! 2!) = 34,650.
• Inclusion-exclusion, or count the opposite. Divisible by 2, 3 or 5 up to 1000: 734.
• Birthday: a collision comes near sqrt(d). 23 people about 50.7%; a 32-bit hash about 77,000 items.
• Expected value adds even without independence. Coupon collector for 6 faces: 14.7 rolls.
• 99% sensitive, 5% false positives, 1% base rate: a positive is real only about 16.7%.

for (let i = a.length - 1; i > 0; i--) {
  const j = Math.floor(
    Math.random() * (i + 1));
  [a[i], a[j]] = [a[j], a[i]];
}

• sort(() => Math.random() - 0.5) is biased: the comparator is inconsistent.
• Reservoir sampling (stream, one pass): keep the first k, then replace slot j when j < k. For k = 1 replace with chance 1/i.

Tip: "It is NP-hard" starts the answer. Next: input size, easy variant (2-colouring?), then exact, DP, approximation or heuristic.

function fail(p) {
  const f = [0];
  for (let i = 1, k = 0; i < p.length;
       i++) {
    while (k > 0 && p[i] !== p[k])
      k = f[k - 1];
    if (p[i] === p[k]) k++;
    f[i] = k;
  }
  return f;
}

Watch out: Rabin-Karp must verify on equal hashes (aa and ht collide mod 101). Indexes count UTF-16 units, not letters.