Data Structures in TypeScript

This file has two halves. Part 1 is the built-in toolbox: what Array, Map, Set, the weak collections, plain objects and strings actually cost, how they are represented inside V8, and the specific traps that turn a correct algorithm into a wrong answer (lexicographic sort, Array(n).fill([]) aliasing, SameValueZero keys, __proto__ pollution, surrogate pairs). It ends with the table that matters most in an interview: what JavaScript does not ship, and what you write instead. Part 2 builds those missing structures from scratch in generic, strict TypeScript — dynamic array through Bloom filter — each with intuition, an ASCII diagram, a complexity table, a runnable implementation, pitfalls, and the follow-ups an interviewer actually asks. Every implementation here was executed on Node 22.22.2 / V8 12.4 with assert-based tests; the two pasted test outputs are real. Python equivalents live in Data structures in Python; the algorithms that consume these structures live in Algorithm patterns and Graphs and trees.

Table of contents

Part 1 — the built-ins

• 1. Array
• 2. Map, Set, WeakMap, WeakSet
• 3. Plain objects as maps
• 4. Strings
• 5. What JavaScript does not ship
• 6. Part 1 test run

Part 2 — from scratch

• 7. Dynamic array
• 8. Singly linked list
• 9. Doubly linked list
• 10. Stack and queue
• 11. Deque
• 12. Hash table
• 13. Binary heap
• 14. Binary search tree
• 15. AVL tree, and red-black in overview
• 16. Trie
• 17. Union-Find
• 18. Graph representations
• 19. LRU and LFU caches
• 20. Segment tree and Fenwick tree
• 21. Skip list
• 22. Bloom filter and Count-Min Sketch
• 23. Emulating TreeMap and SortedList
• 24. Part 2 test run
• 25. The decision table

Part 1 — the built-ins

1. Array

1.1 Intuition and representation

A JavaScript Array is an exotic object whose integer-like keys are special-cased. Semantically it is a hash map from stringified indices to values; practically, V8 stores it as a contiguous backing store whenever it can, and falls back to a dictionary when you make it sparse. That single fact — “contiguous until you break it” — explains almost every performance surprise.

JSArray
 ├─ map (hidden class, carries the *elements kind*)
 ├─ properties  -> named props ('foo')
 ├─ elements    -> FixedArray  [ 1, 2, 3, <free>, <free> ]   capacity 5, length 3
 └─ length      -> 3

The elements kind lattice (PACKED_SMI → … → HOLEY_ELEMENTS → DICTIONARY_ELEMENTS) is described in detail in JS core, including the measured cost of a single delete. Do not re-derive it here; the operational rule for data-structure work is:

• Never create holes. new Array(n) without .fill(), delete arr[i], arr[arr.length + 1] = x and arr.length = bigger all demote the array permanently.
• Keep types monomorphic. An array of all small integers is PACKED_SMI with unboxed storage; pushing one NaN, undefined or object widens it forever.
• Transitions are one-way. There is no “repack” operation. Rebuild the array if you must recover.

1.2 The full method table

n is the receiver length, m the argument length, k the result length.

Two spread/iteration facts worth memorising: [...arr] and Array.from(arr) fill holes with undefined (they use the iterator, which visits every index), whereas map/filter/forEach skip holes. So [...[1, , 3]] is [1, undefined, 3] with a real element at index 1, while [1, , 3].map(x => x) still has a hole at index 1.

1.3 Why shift() is the wrong queue primitive

Per spec, shift moves every remaining element down one index and decrements length. That is O(n) per call, so a BFS loop of while (q.length) { const v = q.shift(); … } is O(n²) on the queue length. V8 does have a fast path that can left-trim the backing store instead of moving elements, but it only applies under narrow conditions (packed elements, no copy-on-write, a length range that makes trimming worthwhile), so it is not something you can rely on and it is definitely not the answer to give. The portable answers are: a head index into a plain array, a ring buffer (section 11), or two stacks (section 10).

The head-index version is three lines and is what you should write under time pressure:

const q: number[] = [start];
for (let head = 0; head < q.length; head++) {
  const v = q[head];
  // ...push neighbours onto q
}

The memory cost is that q never shrinks during the traversal — fine for a BFS, wrong for a long-running queue, which is what the ring buffer solves.

1.4 The sort traps

Array.prototype.sort with no comparator converts every element with ToString and compares the strings in UTF-16 code-unit order. This is the single most common interview error.

const nums = [10, 9, 1, 100, 25];
nums.slice().sort();               // [1, 10, 100, 25, 9]   <- lexicographic
nums.slice().sort((a, b) => a - b) // [1, 9, 10, 25, 100]

Three more rules:

• Stability is guaranteed. V8 uses TimSort (since V8 7.0 / Chrome 70), and stability has been required by the spec since ES2019. You can therefore sort by a secondary key first, then a primary key, and get lexicographic-tuple ordering for free. See Sorting for the internals.
• undefined and holes are exiled to the end and your comparator never sees them. They are moved after all defined values regardless of what you return, and holes stay holes at the very end.
• The comparator must be a consistent total order. Returning a boolean ((a, b) => a > b) is a classic bug: true/false coerce to 1/0, so “less than” and “equal” are indistinguishable and the result is arbitrary. Returning NaN (e.g. subtracting strings) is equally broken.

const holey: (number | undefined)[] = [3, undefined, 1, 9, 2];
delete holey[3];
holey.slice().sort((a, b) => (a as number) - (b as number));
// [ 1, 2, 3, undefined, <1 empty item> ]  — comparator called only 4 times

For object sorting, precompute the sort key when it is expensive (a Schwartzian transform), because the comparator runs O(n log n) times:

type Row = { name: string; created: string };
function byCreatedDesc(rows: readonly Row[]): Row[] {
  return rows
    .map(r => ({ r, k: Date.parse(r.created) }))   // n key computations
    .sort((a, b) => b.k - a.k)
    .map(x => x.r);
}

1.5 The aliasing trap: Array(n).fill([])

fill stores the same reference in every slot. This bites people building grids and adjacency lists, and the symptom (a mutation appearing in every row) looks like a logic bug rather than an initialisation bug.

const bad = Array(3).fill([]) as number[][];
bad[0].push(1);
bad[1].length;      // 1  — same array
bad[0] === bad[2];  // true

const good = Array.from({ length: 3 }, () => [] as number[]);
good[0].push(1);
good[1].length;     // 0

The rule: fill for primitives, Array.from with a factory for anything with identity.

1.6 2D arrays and preallocation

function make2D<T>(rows: number, cols: number, fill: T): T[][] {
  return Array.from({ length: rows }, () => new Array<T>(cols).fill(fill));
}

const grid = make2D(2, 3, 0);
grid[1][2] = 7;   // [[0,0,0],[0,0,7]]

new Array<T>(cols).fill(fill) is deliberate: new Array(cols) allocates capacity in one shot, and .fill immediately packs it, so you get a PACKED array with no reallocation. Array.from({length: n}, () => v) is equivalent and slightly slower; [] plus n pushes forces log n reallocations.

For a flat 1D encoding of a 2D grid — the right choice for hot numeric code, because it is one allocation and one cache-friendly buffer:

class Grid {
  private readonly cells: Int32Array;
  constructor(readonly rows: number, readonly cols: number) {
    this.cells = new Int32Array(rows * cols);
  }
  get(r: number, c: number): number { return this.cells[r * this.cols + c]; }
  set(r: number, c: number, v: number): void { this.cells[r * this.cols + c] = v; }
}

Preallocation summary:

1.7 Typed arrays

Typed arrays are a different animal: fixed length, fixed element type, backed by an ArrayBuffer, no holes, no prototype-chain lookups on index access. Use them when you have numbers and you care.

Behaviour you should be able to state:

const i32 = new Int32Array(4);
i32[0] = 2 ** 31;        // wraps silently
i32[0];                  // -2147483648
i32[99] = 5;             // out-of-range write is *dropped*, not an error, not a new property
i32.length;              // 4

new Uint8ClampedArray([300, -5]);   // [255, 0]

[...new Int32Array([10, 9, 100, 1]).sort()];  // [1, 9, 10, 100] — numeric by default

TypedArray.prototype.sort is a different code path from Array.prototype.sort: it defaults to numeric ordering, not lexicographic, and V8 sorts it without the TimSort machinery. That asymmetry is a good “do you actually know this” question.

Views versus copies is the other half:

const base = new Uint8Array([1, 2, 3, 4]);
const view = base.subarray(1, 3);   // shares the buffer
view[0] = 99;                       // base is now [1, 99, 3, 4]
const copy = base.slice(1, 3);      // new buffer
copy[0] = 7;                        // base unchanged

DataView gives you explicit offsets and endianness, which typed arrays do not (they use platform endianness, little-endian everywhere that matters):

const buf = new ArrayBuffer(4);
new DataView(buf).setUint16(0, 0x0102, /* littleEndian */ false);
[...new Uint8Array(buf)];   // [1, 2, 0, 0]

Also worth knowing: SharedArrayBuffer plus Atomics is the only true shared-memory path between a worker and the main thread; everything else is structured-clone message passing. See Node specifics.

Pitfalls

• sort() with no comparator on numbers. Always pass one.
• arr.length is writable, and arr.length = n on a shorter array creates holes rather than undefineds. Array.from({length: n}) gives you real undefineds.
• arr.includes(NaN) is true; arr.indexOf(NaN) is -1. If you use indexOf for a “seen” check on computed numbers, you will miss NaN.
• splice(0, 1) and shift() are both O(n). Do not use either inside a loop over the array.
• delete arr[i] leaves length untouched and permanently demotes the elements kind. Use splice(i, 1) if you want removal, or a tombstone value if you want O(1).
• concat flattens array arguments one level: [1].concat([2, [3]]) is [1, 2, [3]], not [1, [2, [3]]]. push does not flatten.
• reduce on an empty array with no initial value throws TypeError. Always pass the seed.
• Reference equality in indexOf/includes means [{a:1}].includes({a:1}) is false.

Interview follow-ups

Q: Is push O(1)?

A: Amortised O(1). The backing store grows geometrically, so n pushes cost O(n) total copying; any individual push that triggers a reallocation is O(n). See section 7 for the proof.

Q: Why is shift slower than pop?

A: pop only decrements length. shift must renumber every index, which is an O(n) memmove of the backing store — array indices are part of the observable semantics, not just a physical layout.

Q: What does [10, 9, 1].sort() return and why?

A: [1, 10, 9]. With no comparator the spec converts each element with ToString and compares UTF-16 code units, so "10" < "9".

Q: How do you build an n-by-m grid of independent arrays?

A: Array.from({length: n}, () => new Array(m).fill(0)). Array(n).fill([]) stores one shared array reference in all n slots.

Q: When would you reach for a typed array?

A: Fixed-length numeric data where you want no boxing, no holes, predictable memory and optional zero-copy sharing with a worker: parent/rank arrays in Union-Find, pixel buffers, bitsets, DSP.

Q: How do you make an immutable-ish array?

A: Object.freeze for a shallow freeze (writes throw in strict mode), the ES2023 toSorted / toReversed / toSpliced / with methods to derive new arrays without mutation, and readonly T[] in TypeScript to catch mutation at compile time. None of these deep-freeze.

2. Map, Set, WeakMap, WeakSet

2.1 Intuition

Map is a hash table with a guaranteed iteration order. V8 implements it as an OrderedHashTable: a flat array of [key, value, chain] entry records in insertion order, plus a bucket index that hashes into that array. Lookups go through the buckets; iteration walks the entry array. That layout is why insertion order is free, why delete leaves a gap that is only reclaimed at the next rehash, and why Map beats an object for large, churning, non-string-keyed collections.

buckets: [ 2 | -1 | 0 | ... ]        hash(key) -> bucket -> entry index
entries: [ (k0,v0,next) (k1,v1,next) (k2,v2,next) ... ]   <- insertion order

2.2 Complexity

2.3 Keys are compared with SameValueZero

Not ===, not Object.is. SameValueZero is Object.is except that +0 and -0 are the same key.

const m = new Map<unknown, string>();
m.set(NaN, 'nan');
m.get(NaN);            // 'nan'   — NaN is a usable key, unlike with indexOf
m.set(-0, 'zero');
m.get(0);              // 'zero'  — collides
Object.is([...m.keys()][1], 0);   // true — the stored key was normalised to +0

Object keys are compared by identity, which is the whole point and the whole limitation:

const a = { id: 1 }, b = { id: 1 };
new Map([[a, 'x'], [b, 'y']]).size;   // 2

There is no structural-key map in JavaScript. If you need one, canonicalise the key yourself — JSON.stringify with sorted keys, or a tuple joined with a separator that cannot appear in the parts — and accept the stringification cost. (The Record/Tuple proposal that would have fixed this was withdrawn; the composites proposal is the live successor but is not shippable today.)

2.4 Insertion order, precisely

• Insertion order is specified, for both Map and Set.
• Overwriting an existing key (set on a key that exists) does not move it.
• delete then set does move it to the end. This is the entire trick behind the Map-based LRU cache in section 19.

const order = new Map([['a', 1], ['b', 2], ['c', 3]]);
order.delete('b'); order.set('b', 9);
[...order.keys()];      // ['a', 'c', 'b']
order.set('a', 100);
[...order.keys()];      // ['a', 'c', 'b']  — unchanged

Mutation during iteration is well-defined and occasionally useful: entries appended ahead of the cursor are visited, which turns a Set into an implicit worklist — and into an accidental infinite loop if your guard is wrong.

const s = new Set([1]);
const seen: number[] = [];
for (const x of s) { seen.push(x); if (x < 4) s.add(x + 1); }
seen;   // [1, 2, 3, 4]

2.5 Set algebra (ES2025)

All seven methods are in Node 22.

The argument does not have to be a Set — it has to be set-like: an object with a numeric size, a callable has, and a callable keys. A Map qualifies, which is a nice thing to know:

const A = new Set([1, 2, 3]);
[...A.intersection(new Map([[2, 'x'], [7, 'y']]))];   // [2]

Note the asymmetry: these methods return Sets, they are not generic over subclasses’ element types, and they read size/has/keys from the argument before iterating, so a lazily-mutating argument gives you undefined behaviour in practice.

2.6 WeakMap and WeakSet

A WeakMap entry does not keep its key alive. That is the only difference and it drives everything else about the API.

const wm = new WeakMap<object, number>();
wm.set(1 as unknown as object, 1);              // TypeError: Invalid value used as weak map key
wm.set(Symbol('local') as unknown as object, 2); // OK (ES2023)
wm.set(Symbol.for('global') as unknown as object, 3); // TypeError — registered symbols never die

The absence of iteration is not an oversight: exposing it would make GC timing observable. The three uses that justify a WeakMap:

1. Private state keyed by instance — the pre-#private idiom, still useful for adding state to objects you do not own (DOM nodes, third-party instances).
2. Memoisation keyed by an object argument — the cache entry dies with the argument, so no leak.
3. Metadata sidecars — “have I already processed this node”, cycle detection in a deep-clone.

Compare with the leak archetypes in JS core: a Map used as a cache keyed by request objects is leak archetype number one; a WeakMap is the fix. WeakRef and FinalizationRegistry exist for finer-grained control and both should come with a warning that finalizer timing is not guaranteed and never load-bearing.

Pitfalls

• Using an object literal as a Map key and expecting structural lookup. It is identity.
• map.size versus Object.keys(obj).length — the second is O(n) and allocates.
• Forgetting that a Map used as an unbounded cache is a memory leak. Bound it (LRU) or weaken it.
• new Map(obj) does not work — Map’s constructor takes an iterable of pairs. Use new Map(Object.entries(obj)), and remember that turns numeric keys into strings.
• Spreading a huge Map ([...map]) to sort or filter it allocates an array of pair arrays. Iterate instead when you can.
• V8’s Map does not release the entry array on delete; heavy churn (a queue implemented as a Map) keeps the high-water-mark memory until a rehash. Recreate the map periodically if this matters.
• JSON.stringify(new Map(...)) is {}. Serialise via Object.fromEntries or an array of pairs.
• Set deduplicates by SameValueZero, so new Set([{}, {}]) has size 2 and new Set([NaN, NaN]) has size 1.

Interview follow-ups

Q: Map or object — how do you choose?

A: Map for non-string keys, unknown/user-supplied keys, frequent add/delete, when you need size or guaranteed iteration order, or when keys could collide with Object.prototype. Object for fixed, known, string-keyed records (V8 gives them a hidden class and inline-cached property access), and for anything you will JSON.stringify.

Q: What equality does Map use for keys?

A: SameValueZero — like Object.is except -0 and +0 are the same key. So NaN works as a key and -0 is normalised to +0 on insertion.

Q: Why can’t you iterate a WeakMap?

A: Iteration would make garbage-collection timing observable to the program, which the spec refuses to allow. It would also make the whole thing unusable as a security boundary.

Q: Does delete on a Map free memory immediately?

A: It removes the entry logically and drops the strong references to key and value, but V8’s OrderedHashTable keeps the entry array at its current size until a rehash compacts it, so the table itself does not shrink right away.

Q: How do you implement a map with structural keys?

A: Canonicalise to a primitive: a sorted-key JSON.stringify, or join tuple parts with a separator that cannot occur in them. For nested maps, a trie of Maps keyed by each component avoids the stringification cost at the price of more allocations.

Q: Is Set intersection really O(min(|a|, |b|))?

A: Yes — the spec iterates the smaller collection and probes the larger, which is the whole reason it takes a set-like rather than an iterable.

3. Plain objects as maps

3.1 Why this is a trap and not a shortcut

{} inherits from Object.prototype, so it starts out already “containing” a dozen keys. Every in check, every obj[key] read and every naive merge has to reckon with that.

const dict: Record<string, number> = {};
'toString' in dict;                  // true
Object.hasOwn(dict, 'toString');     // false
dict['toString'];                    // function, not undefined

If a user-supplied string can reach your key, use one of:

const bare = Object.create(null) as Record<string, number>;
'toString' in bare;              // false
Object.getPrototypeOf(bare);     // null
bare['constructor'] = 1;         // just a key

Prefer Object.hasOwn(o, k) over Object.prototype.hasOwnProperty.call(o, k) (ES2022) and never over o.hasOwnProperty(k), which itself breaks on a null-prototype object or a hasOwnProperty key.

3.2 Prototype pollution via __proto__

__proto__ is an accessor property defined on Object.prototype. Assigning to it on an ordinary object replaces the prototype instead of creating a key:

const victim: Record<string, unknown> = {};
victim['__proto__'] = { polluted: true };
Object.getPrototypeOf(victim) === Object.prototype;   // false — swapped
Object.hasOwn(victim, '__proto__');                   // false — no own key was created

On a null-prototype object there is no setter to trigger, so it becomes an ordinary own key — which is exactly why Object.create(null) is the recommended shape for untrusted dictionaries:

const safe = Object.create(null) as Record<string, unknown>;
safe['__proto__'] = { polluted: true };
Object.hasOwn(safe, '__proto__');   // true
Object.getPrototypeOf(safe);        // null

The exploit is the combination of JSON.parse and a recursive merge. JSON.parse creates __proto__ as a real own, enumerable data property (it uses CreateDataProperty, bypassing the setter), so for..in sees it — and a hand-rolled merge/extend/set(path, value) then walks straight onto Object.prototype:

function unsafeMerge(t: Record<string, any>, s: Record<string, any>): Record<string, any> {
  for (const k in s) {
    if (s[k] && typeof s[k] === 'object') { t[k] ??= {}; unsafeMerge(t[k], s[k]); }
    else t[k] = s[k];
  }
  return t;
}

const payload = JSON.parse('{"__proto__":{"isAdmin":true}}');
Object.keys(payload);            // ['__proto__']  — a real own key
unsafeMerge({}, payload);
({} as Record<string, unknown>).isAdmin;   // true  <- every object in the process

Defences, in order of preference: merge into Object.create(null); reject or skip the keys __proto__, constructor and prototype; use Object.defineProperty instead of = when writing; validate with a schema before merging; Object.freeze(Object.prototype) as a blunt process-wide backstop. Note that Object.assign and object spread are safe here — they both use CreateDataProperty semantics for own enumerable keys, so {...payload} gives you an own __proto__ key rather than a prototype swap. It is specifically hand-written recursive merges that are dangerous.

3.3 Key coercion and key order

Every own key is a string or a symbol. Anything else is stringified on the way in:

const o: Record<string, string> = {};
o[1 as unknown as string] = 'num';
o['1'];                       // 'num'
Object.keys(o);               // ['1']

const bad: Record<string, string> = {};
bad[{ a: 1 } as unknown as string] = 'x';
Object.keys(bad);             // ['[object Object]']  — all objects collapse to one key

Ordering of own keys (Object.keys, for..in, JSON.stringify, spread) is specified in OrdinaryOwnPropertyKeys:

1. Array-index-like keys — canonical numeric strings for integers in [0, 2^32 - 2] — in ascending numeric order.
2. All other string keys in property-creation order.
3. Symbol keys in creation order.

const ordered = { b: 1, 2: 1, a: 1, 1: 1, '-1': 1, '1.5': 1, '02': 1 };
Object.keys(ordered);   // ['1', '2', 'b', 'a', '-1', '1.5', '02']

Note that '-1', '1.5' and '02' are not canonical array indices, so they stay in insertion order with the other strings. This is a favourite trick question, and it is a real bug source: an object keyed by numeric IDs silently reorders itself, so if order matters, use a Map or an array of pairs.

for..in additionally walks the prototype chain and yields inherited enumerable string keys, which is why you almost always want Object.keys / Object.entries / for..of instead.

Pitfalls

• if (obj[key]) as a membership test: false for 0, '', false, null. Use Object.hasOwn(obj, key).
• if (obj[userInput]) on a plain object can return an inherited function.
• Numeric-looking keys reorder. { '10': a, '9': b } iterates as 9, 10.
• delete obj.k in a hot loop can push V8 out of hidden-class mode into dictionary mode, making all subsequent property access slow. Set to undefined, or use a Map.
• Object.entries allocates an array of two-element arrays. In a hot loop, iterate Object.keys — or better, use a Map.
• Spreading to “clone” is shallow, and drops non-enumerable and symbol-keyed… no: spread does copy own enumerable symbol keys, but it drops non-enumerables, getters (it invokes them) and the prototype. structuredClone deep-clones but rejects functions and DOM nodes.

Interview follow-ups

Q: What is prototype pollution and how do you prevent it?

A: Writing to __proto__ (or constructor.prototype) through an attacker-controlled key path, which mutates Object.prototype and therefore every object in the process. Prevent it by merging into Object.create(null), blocklisting __proto__/constructor/prototype, using defineProperty instead of assignment, or schema-validating input first.

Q: In what order do object keys iterate?

A: Integer-like keys ascending first, then other string keys in insertion order, then symbols in insertion order. for..in also includes inherited enumerable string keys.

Q: Why is Object.keys(o).length worse than map.size?

A: It is O(n) and allocates an array of all keys; size is a stored field read in O(1).

Q: Is object spread vulnerable to __proto__ in a JSON payload?

A: No. Spread and Object.assign define own properties rather than invoking setters, so you get a harmless own __proto__ key. Hand-written recursive merges that use plain assignment are the vulnerable pattern.

Q: When is a plain object faster than a Map?

A: When the key set is small, fixed and known at write time, so V8 gives the object a stable hidden class and monomorphic inline caches on obj.field. As soon as keys are dynamic, Map wins and the object risks dictionary-mode demotion.

4. Strings

4.1 Immutability and V8 representations

Strings are immutable primitives: every “modification” allocates. That is why building a string with += in a loop is fine in V8 (it builds a rope of ConsString nodes in O(1) per concat, flattening lazily on first indexed read) but arr.push(part) then arr.join('') is still the portable advice. The representation table (SeqString, ConsString, SlicedString, internalized) is in JS core. The operational consequences:

• s1 + s2 is O(1) plus a later O(n) flatten, not an immediate O(n) copy.
• str.slice(i, j) is O(1) — a SlicedString view — but it keeps the whole parent string alive. Slicing a 10 MB response body down to a 20-character token can retain 10 MB. Force a copy with (' ' + s).slice(1) or s.split('').join('') if you need to break the reference; in practice, a String(...) round trip through a template does not reliably flatten, so measure.
• Indexed access on a ConsString triggers flattening, so a single s[0] after a long concat chain pays the whole O(n).

const imm = 'abc';
(imm as unknown as Record<number, string>)[0] = 'z';
imm;   // 'abc'  — silently ignored (throws in strict mode for object receivers, not for primitives)

4.2 Code units, code points, graphemes

A JavaScript string is a sequence of UTF-16 code units. length, charCodeAt, charAt, [], slice and every regex index are in code units. Characters above U+FFFF (all emoji, many CJK extensions, historic scripts) are stored as a surrogate pair of two code units.

'a\u{1F600}b'

code units:   [ 0x0061 ] [ 0xD83D 0xDE00 ] [ 0x0062 ]      length = 4
code points:  U+0061      U+1F600           U+0062         [...s].length = 3
graphemes:    a           😀                b              Segmenter -> 3

const emoji = 'a\u{1F600}b';
emoji.length;             // 4   — code units
[...emoji].length;        // 3   — the string iterator yields code points
emoji.codePointAt(1);     // 128512 (0x1F600)
emoji.charCodeAt(1);      // 55357 (0xD83D) — high surrogate
emoji[1] === '\u{1F600}'; // false — half a character
emoji.slice(1, 3);        // '😀' — a full pair, by luck of the indices

The classic bug and its fix:

emoji.split('').reverse().join('');   // 'b\uDE00\uD83Da'  — mojibake
[...emoji].reverse().join('');        // 'b😀a'

Graphemes are a third level. A ZWJ emoji sequence, a flag, or a base letter plus combining marks is one user-perceived character made of many code points. Only Intl.Segmenter gets this right:

const family = '\u{1F468}‍\u{1F469}‍\u{1F467}';   // man-ZWJ-woman-ZWJ-girl
family.length;          // 8 code units
[...family].length;     // 5 code points
const seg = new Intl.Segmenter('en', { granularity: 'grapheme' });
[...seg.segment(family)].length;   // 1

Choose your unit deliberately:

4.3 Normalisation

Equal-looking strings need not be equal strings. é can be one code point (U+00E9, NFC) or two (U+0065 U+0301, NFD).

'é' === 'é';                            // false
'é'.normalize('NFD') === 'é'.normalize('NFD');   // true

Normalise on input (NFC is the web default) if you will ever compare, deduplicate, or use strings as map keys. NFKC/NFKD additionally fold compatibility characters (fi → fi, ① → 1), which is what you want for search indexing and not what you want for round-tripping user data.

4.4 Comparison and collation

<, > and localeCompare-less sort() compare UTF-16 code units. That is not alphabetical order in any human language.

['ä', 'a', 'z'].sort();                                     // ['a', 'z', 'ä']  — 0xE4 > 0x7A
['ä', 'a', 'z'].sort(new Intl.Collator('de').compare);      // ['a', 'ä', 'z']
['ä', 'a', 'z'].sort(new Intl.Collator('sv').compare);      // ['a', 'z', 'ä']  — Swedish: ä is last
['file10', 'file2'].sort(new Intl.Collator('en', { numeric: true }).compare);   // ['file2','file10']

Rules to state in an interview:

• Use Intl.Collator and hoist it out of the comparator. Constructing one per comparison is the performance bug; str.localeCompare(other, locale, opts) constructs a collator internally on each call, so it is fine for a handful of comparisons and wrong inside a sort of 10,000 items.
• sensitivity: 'base' ignores case and accents; 'accent' ignores case only; numeric: true gives natural/human sort; usage: 'search' loosens matching.
• Locale matters for correctness, not just aesthetics: Swedish sorts ä after z, German sorts it with a. There is no locale-independent “correct” order.
• For case-insensitive comparison of identifiers, toLowerCase() is wrong for Turkish (I → ı); use localeCompare with sensitivity: 'base' or Unicode case folding.

4.5 The method cheatsheet

Pitfalls

• split('').reverse().join('') breaks astral characters. Use [...str].
• str.length is not character count. Truncating a UTF-8-limited field by length can split a pair and produce an invalid string.
• Regexes without the u/v flag treat surrogate pairs as two characters: /./ matches half an emoji. /./u matches the code point; \p{...} property escapes require u.
• localeCompare inside a sort comparator on a large array is slow because of repeated collator construction.
• slice retaining the parent string is a real leak shape when you keep small tokens from huge documents.
• '10' < '9' is true. String comparison is not numeric comparison.
• str.replace('a', 'b') replaces only the first occurrence; replaceAll or /a/g.
• += in a loop is fine in V8 but the accumulated ConsString flattens on the first index read, which can look like a mysterious pause.

Interview follow-ups

Q: How do you reverse a string correctly?

A: [...str].reverse().join('') handles surrogate pairs. For full correctness with combining marks and ZWJ sequences you need grapheme segmentation: reverse the array from Intl.Segmenter.

Q: Why is '😀'.length 2?

A: Strings are UTF-16 code-unit sequences, and U+1F600 is above U+FFFF so it is stored as a surrogate pair — two code units.

Q: Is string concatenation O(n) in JavaScript?

A: In V8, a + b builds a ConsString in O(1) and defers the copy; the flatten to a contiguous string happens on the first operation that needs linear memory (indexing, regex). So a concat loop is not quadratic in practice, but push + join is the portable guarantee.

Q: Two strings look identical but === is false. Why?

A: Different Unicode normalisation forms (composed vs decomposed), or invisible characters (zero-width joiner, BOM, right-to-left mark). Compare .normalize('NFC') and inspect code points.

Q: How would you sort user names for a UI?

A: Hoist an Intl.Collator for the user’s locale with { sensitivity: 'base', numeric: true } and pass its compare to sort. Never bare sort().

Q: How do you count “characters” for a tweet-style limit?

A: Decide what the product means. Code units for storage, code points for a rough count, grapheme clusters via Intl.Segmenter for what users perceive, UTF-8 bytes via TextEncoder for wire limits. Twitter-style limits historically counted code points with weighting.

5. What JavaScript does not ship

This is the table to have memorised. JavaScript’s standard library is thin compared to Python’s or Java’s, and interviewers know it — “there’s no heap in JS, so what do you do?” is a real opener.

For contrast, Python ships heapq, bisect, collections.deque, collections.Counter, collections.OrderedDict, collections.defaultdict, functools.lru_cache and array.array in the standard library — which is why the Python file in this set is much shorter on implementations and longer on “know the module”. See Data structures in Python.

How to answer the opener. “JavaScript has no priority queue, so I’ll write one — it’s about 40 lines and I’ll use it for the Dijkstra loop. Do you want me to write it out, or may I assume it and focus on the algorithm?” That sentence demonstrates you know the gap, you know the fix, and you know how to manage interview time. Most interviewers say “assume it”.

6. Part 1 test run

Every assertion in Part 1 is in part1.ts and runs clean on Node 22.22.2:

holey sorted: [ 1, 2, 3, undefined, <1 empty item> ] length 5 | 3 in = true | 4 in = false | cmp calls 4
Float16Array? undefined | Uint8Array.fromBase64? undefined | Atomics? object
Map.getOrInsert? undefined | Iterator.prototype.map? function

ALL PART 1 ASSERTIONS PASSED

Read the middle two lines as a feature-availability check on this runtime:

If you are asked to use one of the bottom three, say “that’s specified but not in Node 22’s V8 yet” and write the two-line polyfill. getOrInsert in particular:

function getOrInsert<K, V>(m: Map<K, V>, k: K, make: () => V): V {
  let v = m.get(k);
  if (v === undefined && !m.has(k)) { v = make(); m.set(k, v); }
  return v as V;
}

Part 2 — from scratch

Everything from here on is generic, strict TypeScript with no dependencies. One shared type alias is used throughout — a comparator in the standard “negative / zero / positive” shape:

type Cmp<T> = (a: T, b: T) => number;
const asc: Cmp<number> = (a, b) => a - b;

Passing a comparator rather than requiring T extends Comparable is the idiomatic TypeScript choice: it works for primitives, tuples and objects, it lets one class serve as both a min-heap and a max-heap, and it keeps the type parameter unconstrained. The alternative — a compareTo method constraint — is more Java than TypeScript and forces you to wrap primitives.

7. Dynamic array

7.1 Intuition

A dynamic array is a fixed-size buffer plus a length, with a rule for what to do when the buffer is full: allocate a bigger one and copy. If the new size is a constant multiple of the old (doubling), the copies are rare enough that the average cost per push is constant. If you grow by a constant amount (+1, +10), they are not, and push becomes O(n) amortised.

push into a full buffer (capacity 4, length 4)

before   [ a b c d ]                    capacity 4
alloc    [ _ _ _ _ _ _ _ _ ]            capacity 8
copy     [ a b c d _ _ _ _ ]            O(n) once
write    [ a b c d e _ _ _ ]            length 5

7.2 The amortised argument

Two standard proofs; know at least one cold.

Aggregate method. Starting from capacity 1, the reallocations happen at lengths 1, 2, 4, 8, …, n. Total elements copied is 1 + 2 + 4 + … + n < 2n. So n pushes cost O(n) total work, hence O(1) each on average.

Potential (banker’s) method. Charge each push 3 units: 1 to write the element, and 2 saved in the “bank” attached to that element. When the buffer of size k fills, the k/2 elements pushed since the last resize each carry 2 saved units — exactly the k units needed to copy all k elements. The bank never goes negative, so the amortised cost per push is the constant 3.

Why shrink at 1/4, not 1/2. If you halved capacity as soon as length dropped below half, an alternating push/pop at the boundary would reallocate on every single operation — O(n) each, forever. Shrinking only at length ≤ capacity/4 and halving leaves the result at length = capacity/2, so Ω(n) further operations are needed before the next resize in either direction. That gap is the hysteresis, and “why 1/4” is a very common follow-up.

7.3 Complexity

7.4 Implementation

class DynamicArray<T> {
  private data: (T | undefined)[];
  private n = 0;
  constructor(capacity = 4) { this.data = new Array<T | undefined>(Math.max(1, capacity)); }
  get length(): number { return this.n; }
  get capacity(): number { return this.data.length; }

  private reallocate(cap: number): void {
    const next = new Array<T | undefined>(cap);
    for (let i = 0; i < this.n; i++) next[i] = this.data[i];
    this.data = next;
  }

  push(v: T): void {
    if (this.n === this.data.length) this.reallocate(this.data.length * 2);
    this.data[this.n++] = v;
  }

  pop(): T | undefined {
    if (this.n === 0) return undefined;
    const v = this.data[--this.n] as T;
    this.data[this.n] = undefined;                       // drop the reference: GC hygiene
    if (this.n > 0 && this.n * 4 <= this.data.length) this.reallocate(this.data.length >> 1);
    return v;
  }

  get(i: number): T {
    if (i < 0 || i >= this.n) throw new RangeError(`index ${i} out of [0,${this.n})`);
    return this.data[i] as T;
  }

  set(i: number, v: T): void {
    if (i < 0 || i >= this.n) throw new RangeError(`index ${i} out of [0,${this.n})`);
    this.data[i] = v;
  }

  insertAt(i: number, v: T): void {
    if (i < 0 || i > this.n) throw new RangeError(`index ${i}`);
    if (this.n === this.data.length) this.reallocate(this.data.length * 2);
    for (let j = this.n; j > i; j--) this.data[j] = this.data[j - 1];
    this.data[i] = v;
    this.n++;
  }

  removeAt(i: number): T {
    const v = this.get(i);
    for (let j = i; j < this.n - 1; j++) this.data[j] = this.data[j + 1];
    this.data[--this.n] = undefined;
    return v;
  }

  *[Symbol.iterator](): IterableIterator<T> { for (let i = 0; i < this.n; i++) yield this.data[i] as T; }
  toArray(): T[] { return [...this]; }
}

Verified behaviour: 100 pushes from capacity 2 land at capacity 128; popping back down to length 3 leaves capacity 8 (not 4), demonstrating the 1/4-shrink hysteresis; get(3) then throws RangeError.

Pitfalls

• Forgetting to null out the popped slot. this.data[this.n] = undefined is not cosmetic: without it, the buffer keeps a strong reference to a logically removed object and you have a slow leak. This is a favourite senior-level detail.
• Shrinking at capacity/2 instead of capacity/4 (thrashing, see above).
• Growing by a constant instead of a factor. capacity + 1 makes n pushes O(n²).
• Using the capacity rather than the length in the iterator, exposing stale slots.
• Off-by-one in insertAt: the valid range is [0, n] inclusive, unlike get.
• Copying with slice/spread inside reallocate — correct, but then you are just wrapping the built-in array and the exercise is pointless. Copy element by element.

Interview follow-ups

Q: Prove push is amortised O(1).

A: With doubling, total elements copied over n pushes is 1 + 2 + 4 + … + n < 2n, so total work is O(n) and per-push average is O(1). Or use the potential method: charge 3 per push, bank 2, spend the bank on the next copy.

Q: Why shrink at 1/4 capacity rather than 1/2?

A: To avoid thrashing. Halving at 1/2 leaves the array full, so an alternating push/pop at the boundary reallocates every operation. Halving at 1/4 leaves it half full, guaranteeing Ω(n) operations before the next resize.

Q: What is the memory overhead?

A: Up to 2× the live data with doubling (just after a resize the buffer is half empty; just before it is full). Growth factor 1.5 trades a bit more copying for less slack, which is why some allocators prefer it — the freed block can be reused by the next allocation.

Q: How does this differ from V8’s Array?

A: Same idea, but V8 also specialises the element representation (PACKED_SMI and friends), keeps length and capacity separate in the FixedArray backing store, can share a copy-on-write backing store between array literals, and can degrade to a dictionary if you make the array sparse.

Q: Would you use a Uint32Array internally?

A: For numeric element types, yes — no boxing, no hole checks, contiguous memory. But you lose genericity, so the generic version has to use a plain array.

8. Singly linked list

8.1 Intuition

A chain of nodes, each holding a value and a pointer to the next. You trade O(1) random access for O(1) insert/remove at a position you already hold. In JavaScript, a linked list is almost never the right production data structure — pointer chasing destroys cache locality and every node is a separate heap allocation — but it is the single most interviewed structure because the pointer manipulation is easy to get wrong under pressure.

head
 │
 v
[1|•]──>[2|•]──>[3|•]──>[4|/]         '/' = null

8.2 Complexity

8.3 The node and the two converters

Every classic problem is easier if you can build and inspect lists in one line.

class SNode<T> {
  next: SNode<T> | null = null;
  constructor(public value: T) {}
}

function fromArray<T>(xs: readonly T[]): SNode<T> | null {
  let head: SNode<T> | null = null, tail: SNode<T> | null = null;
  for (const x of xs) {
    const node = new SNode(x);
    if (tail === null) { head = node; tail = node; } else { tail.next = node; tail = node; }
  }
  return head;
}

function toArray<T>(head: SNode<T> | null): T[] {
  const out: T[] = [];
  for (let cur = head; cur !== null; cur = cur.next) out.push(cur.value);
  return out;
}

8.4 Reverse — iterative and recursive

The iterative three-pointer dance is the one to write. Say the invariant out loud: prev is the head of the already-reversed prefix, cur is the head of the untouched suffix.

prev   cur                       prev        cur
 /     [1]->[2]->[3]      =>     [1]->/      [2]->[3]

function reverseIterative<T>(head: SNode<T> | null): SNode<T> | null {
  let prev: SNode<T> | null = null, cur = head;
  while (cur !== null) {
    const next = cur.next;   // save before you clobber it
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

function reverseRecursive<T>(head: SNode<T> | null): SNode<T> | null {
  if (head === null || head.next === null) return head;   // base: empty or single
  const newHead = reverseRecursive(head.next);
  head.next.next = head;                                  // the tail of the reversed rest points back
  head.next = null;                                       // and this node becomes the new tail
  return newHead;
}

Iterative is O(1) space; recursive is O(n) stack and will blow up around 10⁴–10⁵ nodes in Node. Say that trade-off unprompted.

8.5 Floyd cycle detection

Two pointers, one moving twice as fast. If there is a cycle, the fast one laps the slow one inside it. Once they meet, reset one pointer to the head and advance both one step at a time; they meet at the cycle entrance.

  a = 3 (tail length)      b = 4 (cycle length)
[1]->[2]->[3]->[4]->[5]->[6]->[7]
                ^                |
                +----------------+

The proof: let a be the distance from head to the cycle entry and let the meeting point be m steps into the cycle. When they meet, slow has travelled a + m and fast 2(a + m), and the difference a + m must be a whole number of cycle lengths. So walking a more steps from the meeting point lands back at the entry — and a steps from the head lands there too. Hence the two-pointer restart.

function detectCycle<T>(head: SNode<T> | null): SNode<T> | null {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p = head;
      while (p !== slow) { p = p!.next; slow = slow!.next; }
      return p;                       // cycle entry
    }
  }
  return null;                        // fell off the end: no cycle
}

8.6 The rest of the classics

function mergeTwoSorted<T>(a: SNode<T> | null, b: SNode<T> | null, cmp: Cmp<T>): SNode<T> | null {
  const dummy = new SNode<T>(undefined as unknown as T);   // sentinel kills the "which is head?" branch
  let tail = dummy;
  while (a !== null && b !== null) {
    if (cmp(a.value, b.value) <= 0) { tail.next = a; a = a.next; }   // <= keeps it stable
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;                                      // one is null, append the other whole
  return dummy.next;
}

function middleNode<T>(head: SNode<T> | null): SNode<T> | null {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) { slow = slow!.next; fast = fast.next.next; }
  return slow;                        // even length -> the SECOND middle; swap the loop test for the first
}

function removeNthFromEnd<T>(head: SNode<T> | null, n: number): SNode<T> | null {
  const dummy = new SNode<T>(undefined as unknown as T);
  dummy.next = head;
  let lead: SNode<T> | null = dummy, trail: SNode<T> = dummy;
  for (let i = 0; i < n; i++) {
    if (lead === null) throw new RangeError('n larger than list');
    lead = lead.next;
  }
  while (lead !== null && lead.next !== null) { lead = lead.next; trail = trail.next!; }
  trail.next = trail.next!.next;      // trail is the (n+1)-th from the end
  return dummy.next;                  // dummy is why removing the head needs no special case
}

function isPalindrome<T>(head: SNode<T> | null): boolean {
  if (head === null || head.next === null) return true;
  let slow: SNode<T> = head, fast: SNode<T> | null = head;
  while (fast !== null && fast.next !== null) { slow = slow.next!; fast = fast.next.next; }
  const second = reverseIterative(slow);                  // reverse the back half in place
  let p: SNode<T> | null = head, q: SNode<T> | null = second;
  let ok = true;
  while (q !== null) { if (p!.value !== q.value) { ok = false; break; } p = p!.next; q = q.next; }
  reverseIterative(second);                               // restore the input — interviewers like this
  return ok;
}

isPalindrome is O(n) time and O(1) space, which is the point; the naive version copies to an array. Note that it compares with !==, so it is identity/value equality on T — parameterise with an equality function if T is a record.

8.7 A list class worth writing

class SinglyLinkedList<T> {
  private head: SNode<T> | null = null;
  private tail: SNode<T> | null = null;   // the tail pointer is what makes pushBack O(1)
  private n = 0;
  get size(): number { return this.n; }
  get first(): T | undefined { return this.head?.value; }
  get last(): T | undefined { return this.tail?.value; }

  pushBack(v: T): this {
    const node = new SNode(v);
    if (this.tail === null) { this.head = node; this.tail = node; }
    else { this.tail.next = node; this.tail = node; }
    this.n++;
    return this;
  }

  pushFront(v: T): this {
    const node = new SNode(v);
    node.next = this.head;
    this.head = node;
    if (this.tail === null) this.tail = node;
    this.n++;
    return this;
  }

  popFront(): T | undefined {
    if (this.head === null) return undefined;
    const v = this.head.value;
    this.head = this.head.next;
    if (this.head === null) this.tail = null;   // emptied: keep the invariant
    this.n--;
    return v;
  }

  removeFirst(pred: (v: T) => boolean): boolean {
    let prev: SNode<T> | null = null;
    for (let cur = this.head; cur !== null; prev = cur, cur = cur.next) {
      if (!pred(cur.value)) continue;
      if (prev === null) this.head = cur.next; else prev.next = cur.next;
      if (cur === this.tail) this.tail = prev;
      this.n--;
      return true;
    }
    return false;
  }

  reverse(): this {
    this.tail = this.head;                      // the old head becomes the tail
    this.head = reverseIterative(this.head);
    return this;
  }

  *[Symbol.iterator](): IterableIterator<T> {
    for (let cur = this.head; cur !== null; cur = cur.next) yield cur.value;
  }
}

Pitfalls

• Losing the next pointer before you overwrite it. Every reverse bug is this bug.
• Forgetting to update tail on popFront (when the list empties) and on reverse. The size and head stay right, so tests pass until someone calls pushBack.
• Not using a dummy/sentinel head for problems where the first node can be removed. It turns two cases into one.
• while (fast.next.next) without checking fast.next first: TypeError on even-length lists.
• Recursive reverse on a long list: stack overflow. Node’s default stack is roughly 10⁴ frames.
• Returning head instead of prev from an iterative reverse — you return the new tail.
• Assuming middleNode returns the first middle. For even length this returns the second; if a problem needs the first, stop when fast.next.next is null.

Interview follow-ups

Q: Reverse a list in O(1) space.

A: Three pointers — prev, cur, next — walk once, flipping each next to prev. Return prev.

Q: How does Floyd’s algorithm find the cycle start, not just detect a cycle?

A: After the pointers meet, the distance from the head to the entry equals the distance from the meeting point to the entry (mod cycle length). So reset one pointer to the head and advance both one step at a time; they meet at the entry.

Q: Cycle detection without Floyd?

A: A Set of visited nodes — O(n) time, O(n) space. Floyd’s is O(1) space, which is the only reason it exists. Brent’s algorithm is an alternative with fewer pointer moves.

Q: Singly vs doubly — when is the extra pointer worth it?

A: When you need O(1) removal given a node handle, or O(1) popBack, or backwards iteration. That is exactly the LRU cache, which is why LRU uses a doubly linked list.

Q: Why is a linked list slow in practice despite the O(1) claims?

A: Each node is a separate allocation, so traversal is a chain of cache misses, and each node costs a header plus a pointer. An array of the same data is one contiguous block prefetched by the hardware. The O(1) insert only helps if you already hold the node.

Q: Merge k sorted lists?

A: Either pairwise merge in rounds — O(n log k) — or a min-heap of the k current heads, popping and pushing — also O(n log k) with O(k) extra space. See kWayMerge in section 13.

Q: Detect the intersection node of two lists?

A: Walk both, note the lengths, advance the longer by the difference, then step together until the nodes are identical. Or the pointer-swap trick: when a pointer hits the end, restart it on the other list; they meet at the intersection after at most m + n steps.

9. Doubly linked list

9.1 Intuition

Add a prev pointer and removal becomes O(1) given a node — which is the whole reason the structure exists. Two sentinel nodes (a permanent head and tail that hold no data) remove every null check from the hot paths, so insertBetween and unlink have no branches at all. That is worth doing even in an interview: the code gets shorter, not longer.

       sentinels
  ┌────────────────────────────────────────┐
 [H] <-> [a] <-> [b] <-> [c] <-> [T]
  ^                               ^
  head (no value)                 tail (no value)

9.2 Complexity

9.3 Implementation

class DNode<T> {
  prev: DNode<T> | null = null;
  next: DNode<T> | null = null;
  constructor(public value: T) {}
}

class DoublyLinkedList<T> implements Iterable<T> {
  private readonly head = new DNode<T>(undefined as unknown as T);
  private readonly tail = new DNode<T>(undefined as unknown as T);
  private n = 0;
  constructor(items?: Iterable<T>) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
    if (items) for (const x of items) this.pushBack(x);
  }
  get size(): number { return this.n; }

  private insertBetween(v: T, left: DNode<T>, right: DNode<T>): DNode<T> {
    const node = new DNode(v);
    node.prev = left; node.next = right;
    left.next = node; right.prev = node;
    this.n++;
    return node;                                  // return the handle: callers need it
  }

  pushBack(v: T): DNode<T> { return this.insertBetween(v, this.tail.prev!, this.tail); }
  pushFront(v: T): DNode<T> { return this.insertBetween(v, this.head, this.head.next!); }
  insertBefore(node: DNode<T>, v: T): DNode<T> { return this.insertBetween(v, node.prev!, node); }
  insertAfter(node: DNode<T>, v: T): DNode<T> { return this.insertBetween(v, node, node.next!); }

  unlink(node: DNode<T>): T {
    if (node === this.head || node === this.tail) throw new Error('cannot unlink a sentinel');
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
    node.prev = null; node.next = null;           // isolate it so a stale handle cannot corrupt the list
    this.n--;
    return node.value;
  }

  popBack(): T | undefined { return this.n === 0 ? undefined : this.unlink(this.tail.prev!); }
  popFront(): T | undefined { return this.n === 0 ? undefined : this.unlink(this.head.next!); }
  peekFront(): T | undefined { return this.n === 0 ? undefined : this.head.next!.value; }
  peekBack(): T | undefined { return this.n === 0 ? undefined : this.tail.prev!.value; }

  moveToBack(node: DNode<T>): void {              // no allocation, no size change
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
    const left = this.tail.prev!;
    left.next = node; node.prev = left;
    node.next = this.tail; this.tail.prev = node;
  }

  *[Symbol.iterator](): IterableIterator<T> {
    for (let c = this.head.next!; c !== this.tail; c = c.next!) yield c.value;
  }
  *reversed(): IterableIterator<T> {
    for (let c = this.tail.prev!; c !== this.head; c = c.prev!) yield c.value;
  }
}

The returned DNode<T> handle is the API’s whole value. LRUCacheDLL in section 19 stores those handles in a Map and that is what makes eviction O(1).

Pitfalls

• Exposing DNode publicly without guarding sentinels. A caller who unlinks the tail sentinel corrupts the list silently. Hence the explicit throw.
• Forgetting to null out prev/next on unlink. A stale handle then still stitches into the live list and — worse — keeps the neighbours alive for GC.
• Doing moveToBack on a node that is already the last one. The code above happens to be safe (it re-links to itself correctly because left is recomputed after the splice-out), but the naive ordering — grab left = tail.prev before unlinking — self-links the node and hangs the iterator. Order matters.
• Maintaining size in two places (unlink and each pop) and double-decrementing. Route every removal through unlink.
• Circular DLL with a single sentinel is also fine and slightly more compact; just be consistent.

Interview follow-ups

Q: Why do the sentinels help?

A: Every insertion and removal happens strictly between two existing nodes, so left.next and right.prev always exist. No null checks, no “is this the head?” special case, and an empty list is just H <-> T.

Q: How much memory does a DLL cost versus an array?

A: Per element: one object header, a value slot and two pointers — call it 4–6 words in V8 — versus one slot in a packed array. Plus the allocations are scattered, so traversal misses cache.

Q: When is a DLL genuinely the right choice?

A: When you hold node handles and need O(1) reorder or removal: LRU/LFU caches, intrusive free lists, a text editor’s line buffer, a scheduler’s run queue. Almost never for “a list of things”.

Q: Can you make a DLL iterator safe against concurrent mutation?

A: Capture the next node before yielding, or version-stamp the list and throw on mutation mid-iteration (like Java’s ConcurrentModificationException). The generator above reads c.next after the yield resumes, so unlinking the current node during iteration ends the loop early.

10. Stack and queue

10.1 Stack

LIFO. In JavaScript a plain array is a stack: push/pop are both amortised O(1) at the end. Wrap it only for the API and the type safety.

class Stack<T> {
  private items: T[] = [];
  get size(): number { return this.items.length; }
  get isEmpty(): boolean { return this.items.length === 0; }
  push(v: T): void { this.items.push(v); }
  pop(): T | undefined { return this.items.pop(); }
  peek(): T | undefined { return this.items[this.items.length - 1]; }
  *[Symbol.iterator](): IterableIterator<T> {
    for (let i = this.items.length - 1; i >= 0; i--) yield this.items[i];   // top-down
  }
}

Iterating top-down is a deliberate choice: it matches the mental model, and it is what callers expect when they spread a stack.

10.2 Why Array.shift() is the wrong queue

Repeating the Part 1 point because it is the queue question: shift() renumbers every index, so it is O(n), and a BFS written with it is O(n²) in the queue length. On a 100k-node BFS that is the difference between milliseconds and tens of seconds. Three correct answers:

10.3 Queue via two stacks

Push onto inbox. When you need to dequeue and outbox is empty, pour inbox into outbox — which reverses it, so outbox.pop() yields the oldest element. Each element is moved at most once from inbox to outbox, so the amortised cost is O(1) even though a single dequeue can be O(n).

enqueue 1,2,3       inbox [1 2 3]   outbox []
dequeue             pour ->         outbox [3 2 1]   pop -> 1
enqueue 4           inbox [4]       outbox [3 2]
dequeue                             pop -> 2         (no pour: outbox non-empty)

class QueueTwoStacks<T> {
  private inbox: T[] = [];
  private outbox: T[] = [];
  get size(): number { return this.inbox.length + this.outbox.length; }
  enqueue(v: T): void { this.inbox.push(v); }
  private transfer(): void {
    if (this.outbox.length === 0) while (this.inbox.length) this.outbox.push(this.inbox.pop()!);
  }
  dequeue(): T | undefined { this.transfer(); return this.outbox.pop(); }
  peek(): T | undefined { this.transfer(); return this.outbox[this.outbox.length - 1]; }
}

The critical line is if (this.outbox.length === 0). Pouring on every dequeue — or pouring when the outbox is non-empty — breaks both FIFO order and the amortised bound.

10.4 Queue via a ring buffer

One fixed array, a head index and a count. Physical positions wrap with modulo; the logical order is head, head+1, … mod capacity. O(1) worst case for both ends, no allocation after construction, which is why every real-world bounded queue (audio buffers, network rings, libuv’s internals) is a ring.

capacity 5, head=3, n=4
index:   0    1    2    3    4
       [ c ][ d ][   ][ a ][ b ]
                        ^head
logical order: a b c d

class RingQueue<T> {
  private buf: (T | undefined)[];
  private head = 0;
  private n = 0;
  constructor(private readonly cap: number) {
    if (cap <= 0) throw new RangeError('capacity must be positive');
    this.buf = new Array<T | undefined>(cap);
  }
  get size(): number { return this.n; }
  get isFull(): boolean { return this.n === this.cap; }
  enqueue(v: T): void {
    if (this.isFull) throw new Error('queue is full');    // or overwrite, for a lossy ring
    this.buf[(this.head + this.n) % this.cap] = v;
    this.n++;
  }
  dequeue(): T | undefined {
    if (this.n === 0) return undefined;
    const v = this.buf[this.head] as T;
    this.buf[this.head] = undefined;                      // release the reference
    this.head = (this.head + 1) % this.cap;
    this.n--;
    return v;
  }
  peek(): T | undefined { return this.n === 0 ? undefined : (this.buf[this.head] as T); }
}

Store a count, not a tail index. With head and tail alone, head === tail is ambiguous between empty and full, and the usual fix is to waste one slot. A count removes the ambiguity for free.

If the capacity is a power of two, replace % cap with & (cap - 1) — one instruction instead of a division, and it is what production ring buffers do.

Pitfalls

• shift() in a loop. Again.
• Two-stack queue: transferring when the outbox is not empty, which scrambles the order.
• Ring buffer: using head === tail as the empty test without a count or a wasted slot.
• Ring buffer: negative modulo. (head - 1) % cap is negative in JavaScript for head === 0; use (head - 1 + cap) % cap.
• Not clearing the slot on dequeue — the same GC-hygiene bug as the dynamic array.
• Using a Set as a queue because it iterates in insertion order. It works, but delete on the front is O(1) only amortised and the table never shrinks, so churn leaks.

Interview follow-ups

Q: Implement a queue with two stacks and state the complexity.

A: Enqueue pushes to the inbox: O(1). Dequeue pops the outbox, refilling it from the inbox only when it is empty: O(1) amortised, O(n) worst case. Each element moves between the stacks at most once.

Q: Implement a stack with two queues.

A: Possible but ugly: either push is O(n) (enqueue, then rotate all previous elements behind it) or pop is O(n) (move n-1 elements to the other queue). There is no O(1)/O(1) construction.

Q: Why does the amortised bound hold for the two-stack queue?

A: Potential method: each element carries 1 unit of stored work when it enters the inbox, spent when it is poured into the outbox. Total work over n operations is O(n).

Q: Bounded queue that overwrites the oldest element when full?

A: In enqueue, if full, write at (head + n) % cap and advance head — that is a lossy ring buffer, exactly what a fixed-size log or metrics window wants.

Q: How do you make a ring buffer growable?

A: On overflow, allocate 2× and copy in logical order (for i in 0..n: next[i] = buf[(head+i)%cap]), resetting head to 0. That is the deque in section 11.

Q: How do the built-in queue-ish options compare?

A: There are none. Array gives you a stack for free and a queue only with a head index; Map/Set give insertion order but not cheap front removal. Everything else you write.

11. Deque

11.1 Intuition

A double-ended queue: O(1) push and pop at both ends, plus O(1) indexed access. A growable ring buffer gives you all three. This is the structure JavaScript most conspicuously lacks — sliding-window maximum, monotonic deques, BFS with early exit, and 0-1 BFS all want it — and Python gets it for free from collections.deque.

pushFront wraps backwards; pushBack wraps forwards

capacity 8, head=6, n=4:
  0    1    2    3    4    5    6    7
[ c ][ d ][   ][   ][   ][   ][ a ][ b ]
                                ^head
logical: a b c d      at(0)=a   at(-1)=d

11.2 Complexity

11.3 Implementation

class Deque<T> implements Iterable<T> {
  private buf: (T | undefined)[];
  private head = 0;
  private n = 0;
  constructor(capacity = 8) { this.buf = new Array<T | undefined>(Math.max(1, capacity)); }
  get size(): number { return this.n; }
  get capacity(): number { return this.buf.length; }

  private grow(): void {
    const next = new Array<T | undefined>(this.buf.length * 2);
    for (let i = 0; i < this.n; i++) next[i] = this.buf[(this.head + i) % this.buf.length];
    this.buf = next;
    this.head = 0;                       // unwrap into logical order while copying
  }

  pushBack(v: T): void {
    if (this.n === this.buf.length) this.grow();
    this.buf[(this.head + this.n) % this.buf.length] = v;
    this.n++;
  }

  pushFront(v: T): void {
    if (this.n === this.buf.length) this.grow();
    this.head = (this.head - 1 + this.buf.length) % this.buf.length;   // + length: JS modulo is signed
    this.buf[this.head] = v;
    this.n++;
  }

  popFront(): T | undefined {
    if (this.n === 0) return undefined;
    const v = this.buf[this.head] as T;
    this.buf[this.head] = undefined;
    this.head = (this.head + 1) % this.buf.length;
    this.n--;
    return v;
  }

  popBack(): T | undefined {
    if (this.n === 0) return undefined;
    const i = (this.head + this.n - 1) % this.buf.length;
    const v = this.buf[i] as T;
    this.buf[i] = undefined;
    this.n--;
    return v;
  }

  at(i: number): T | undefined {
    if (i < 0) i += this.n;                                  // negative indices like Array#at
    if (i < 0 || i >= this.n) return undefined;
    return this.buf[(this.head + i) % this.buf.length] as T;
  }

  *[Symbol.iterator](): IterableIterator<T> { for (let i = 0; i < this.n; i++) yield this.at(i) as T; }
}

Verified: 1,002 elements after 1,000 pushFront calls on a deque that started at capacity 2, with at(0) and at(1001) both correct across many wraps and regrowths.

Pitfalls

• Negative modulo. (0 - 1) % 8 is -1 in JavaScript, not 7. Always (x - 1 + len) % len.
• Growing without unwrapping. If you slice-copy the raw buffer you keep the wrap, and every index computation afterwards is wrong. Copy in logical order and reset head = 0.
• Computing the back index as (head + n) % len when popping — that is one past the end. It is (head + n - 1) % len.
• Forgetting that capacity and size are different, and iterating the buffer instead of the logical range.
• Using % on a hot path when the capacity is a power of two: use & (cap - 1).

Interview follow-ups

Q: Why not just use two arrays back to back?

A: You can — a “front” array you pop from and a “back” array you push to, rebalancing when one empties. It is amortised O(1) but has worse constants and no O(1) indexed access.

Q: How does collections.deque in Python differ?

A: CPython uses a doubly linked list of 64-slot blocks, so pushes never copy the whole structure and there is no amortised-O(n) spike — but indexing is O(n) in the middle. The ring buffer trades that for O(1) indexing.

Q: What is the deque used for in interview algorithms?

A: Sliding-window maximum (monotonic deque), 0-1 BFS (push-front for weight-0 edges), palindrome checks from both ends, and “last k items” windows. See Algorithm patterns.

Q: Can you shrink it?

A: Yes — same 1/4 rule as the dynamic array, halving when n * 4 <= capacity. Omitted above because deques usually have a bounded working set; add it if the deque outlives its peak.

12. Hash table

12.1 Intuition

Turn a key into an integer, use it to pick a slot, and deal with the fact that two keys will eventually pick the same slot. Every design decision falls out of that last clause: collision resolution is the whole subject. Two families:

SEPARATE CHAINING                    OPEN ADDRESSING (linear probing)
buckets                              one flat array
 0 -> [k1,v1] -> [k9,v9]              0: (k1,v1)
 1 -> null                            1: (k9,v9)   <- collided with 0, placed next
 2 -> [k4,v4]                         2: (k4,v4)
 3 -> null                            3: empty

Chaining is forgiving: load factor can exceed 1, deletion is trivial, and the worst case degrades gracefully. Open addressing is faster when it fits in cache — one contiguous array, no pointer chasing — but it needs load factor well under 1 and deletion needs tombstones.

12.2 A string hash: FNV-1a

You need a hash function you can write from memory. FNV-1a is five lines and has good avalanche for short strings.

function fnv1a(str: string): number {
  let h = 0x811c9dc5;                        // 2166136261, the FNV offset basis
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);                  // XOR first, then multiply — that is the "1a" variant
    h = Math.imul(h, 0x01000193);            // 16777619, the FNV prime
  }
  return h >>> 0;                            // back to an unsigned 32-bit integer
}

Three JavaScript-specific details that matter:

• Math.imul is mandatory. h * 16777619 overflows into a double and loses the low bits, which destroys the hash. Math.imul performs a true 32-bit integer multiply.
• >>> 0 converts the signed int32 result of the bitwise ops to an unsigned 32-bit value. Without it you can get negative indices.
• charCodeAt gives UTF-16 code units, so surrogate pairs hash as two units. That is fine and consistent; just do not claim it hashes “characters”.

Verified against known FNV-1a 32-bit vectors: fnv1a('a') === 0xe40c292c and fnv1a('foobar') === 0xbf9cf968. Over 5,000 keys of the form user:N into 1,024 buckets the largest bucket held fewer than 20 entries — flat enough (the expected max for a uniform hash is around 12–14).

For a second independent hash — needed for double hashing and Bloom filters — djb2 is the other one to memorise:

function djb2(str: string): number {
  let h = 5381;
  for (let i = 0; i < str.length; i++) h = (Math.imul(h, 33) + str.charCodeAt(i)) | 0;
  return h >>> 0;
}

12.3 Complexity

Let α be the load factor (entries / slots).

Read the probing column: at α = 0.5 the expected probe count for a successful lookup is about 1.5; at α = 0.9 it is about 5.5; at α = 0.99 it is about 50. That superlinear blow-up is why open addressing resizes aggressively and chaining does not.

The O(n) worst case is not theoretical — it is the hash-flooding DoS: an attacker who can predict your hash function sends keys that all land in one bucket, turning every request into an O(n) scan. Real runtimes defend with a per-process random seed (V8 uses a randomised string hash seed) and, in Java’s case, by converting long buckets into red-black trees. If you write your own table for untrusted keys, seed it.

12.4 Separate chaining

class ChainedHashMap<V> {
  private buckets: [string, V][][];
  private n = 0;
  private readonly maxLoad = 0.75;
  constructor(initialCapacity = 8) {
    this.buckets = Array.from({ length: initialCapacity }, () => []);   // NOT Array(n).fill([])
  }
  get size(): number { return this.n; }
  get loadFactor(): number { return this.n / this.buckets.length; }

  private indexOf(key: string, buckets = this.buckets): number {
    return fnv1a(key) & (buckets.length - 1);      // power-of-two capacity -> mask instead of %
  }

  set(key: string, value: V): void {
    const b = this.buckets[this.indexOf(key)];
    for (const e of b) if (e[0] === key) { e[1] = value; return; }     // update in place
    b.push([key, value]);
    if (++this.n / this.buckets.length > this.maxLoad) this.resize(this.buckets.length * 2);
  }

  get(key: string): V | undefined {
    for (const e of this.buckets[this.indexOf(key)]) if (e[0] === key) return e[1];
    return undefined;
  }

  has(key: string): boolean { return this.buckets[this.indexOf(key)].some(e => e[0] === key); }

  delete(key: string): boolean {
    const b = this.buckets[this.indexOf(key)];
    const i = b.findIndex(e => e[0] === key);
    if (i < 0) return false;
    b.splice(i, 1);
    this.n--;
    return true;
  }

  private resize(cap: number): void {
    const next: [string, V][][] = Array.from({ length: cap }, () => []);
    for (const b of this.buckets) for (const e of b) next[this.indexOf(e[0], next)].push(e);
    this.buckets = next;                            // rehash everything: O(n)
  }

  *entries(): IterableIterator<[string, V]> { for (const b of this.buckets) yield* b; }
  longestChain(): number { return Math.max(...this.buckets.map(b => b.length)); }
}

Note Array.from({length: n}, () => []) in both the constructor and resize — Array(n).fill([]) would give every bucket the same array (see section 1.5).

12.5 Open addressing with tombstones

The subtlety is deletion. If you clear a slot to empty, you truncate every probe chain that passed through it and lookups for later keys start returning undefined. A tombstone marks “occupied before, empty now”: probes continue past it, but inserts may reuse it.

insert k1 -> slot 3, k2 -> 3 taken -> slot 4, k3 -> 3,4 taken -> slot 5

delete k2 with a plain clear:      3:(k1) 4:EMPTY 5:(k3)
   get(k3) probes 3, sees 4 empty, gives up  ->  WRONG

delete k2 with a tombstone:        3:(k1) 4:TOMB  5:(k3)
   get(k3) probes 3, skips 4, finds 5        ->  correct

const TOMBSTONE = Symbol('tombstone');

class OpenAddressingMap<V> {
  private keys: (string | undefined | typeof TOMBSTONE)[];
  private vals: (V | undefined)[];
  private n = 0;                             // live entries
  private used = 0;                          // live + tombstones -> this is what drives resizing
  private readonly maxLoad = 0.5;
  constructor(capacity = 8) {
    this.keys = new Array(capacity);
    this.vals = new Array<V | undefined>(capacity);
  }
  get size(): number { return this.n; }

  private probe(key: string): { slot: number; found: boolean } {
    const mask = this.keys.length - 1;
    let i = fnv1a(key) & mask;
    let firstTomb = -1;
    for (;;) {
      const k = this.keys[i];
      if (k === undefined) return { slot: firstTomb >= 0 ? firstTomb : i, found: false };
      if (k === TOMBSTONE) { if (firstTomb < 0) firstTomb = i; }   // remember it, keep probing
      else if (k === key) return { slot: i, found: true };
      i = (i + 1) & mask;                                          // linear probing
    }
  }

  set(key: string, value: V): void {
    if ((this.used + 1) / this.keys.length > this.maxLoad) this.resize(this.keys.length * 2);
    const { slot, found } = this.probe(key);
    if (!found) {
      if (this.keys[slot] === undefined) this.used++;   // reusing a tombstone does not grow `used`
      this.n++;
    }
    this.keys[slot] = key;
    this.vals[slot] = value;
  }

  get(key: string): V | undefined {
    const { slot, found } = this.probe(key);
    return found ? this.vals[slot] : undefined;
  }

  delete(key: string): boolean {
    const { slot, found } = this.probe(key);
    if (!found) return false;
    this.keys[slot] = TOMBSTONE;               // NOT undefined
    this.vals[slot] = undefined;               // but do release the value
    this.n--;
    return true;
  }

  private resize(cap: number): void {
    const oldKeys = this.keys, oldVals = this.vals;
    this.keys = new Array(cap);
    this.vals = new Array<V | undefined>(cap);
    this.n = 0; this.used = 0;
    for (let i = 0; i < oldKeys.length; i++) {
      const k = oldKeys[i];
      if (typeof k === 'string') this.set(k, oldVals[i] as V);   // rehash drops all tombstones
    }
  }

  *entries(): IterableIterator<[string, V]> {
    for (let i = 0; i < this.keys.length; i++) {
      const k = this.keys[i];
      if (typeof k === 'string') yield [k, this.vals[i] as V];
    }
  }
}