Polyfills and JavaScript Utility Implementation Questions
Rebuilding standard JavaScript behavior and common utility libraries from scratch, the machine-coding interview genre where a candidate re-creates a familiar API to prove they understand its mechanics. Covers a minimal Promise built from first principles (chaining, asynchronous handlers, single settlement, thenable adoption, error flow) and Promise.allSettled-style combinators; polyfills for browser APIs such as IntersectionObserver, and a keyed virtual DOM diff; utilities such as debounce (leading and trailing, cancel, flush), throttle, and React hooks that debounce a value or a callback with stable identity and no stale closures; deep clone (cycles, shared references, Dates, RegExps), shallow and deep equality (typed arrays, Maps and Sets, NaN and -0), nested object helpers (safe path get, flatten and unflatten, deep merge), curry with placeholders and partial application, and memoize with cache keys and WeakMap-based caches; and small infrastructure such as event emitters (on, off, once, emit, context binding, listener leaks). Emphasizes edge cases, correct this binding, argument handling, spec fidelity, and complexity. Using these built-ins as a language feature, the event loop and async/await semantics, DOM traversal and event propagation, functional programming as a paradigm, and generic algorithm puzzles are covered elsewhere.
Implement curry(fn) so the returned function accepts arguments across several calls until the original arity is satisfied. Extend it so callers can leave a gap in the argument list and fill it in later, and make sure this is preserved if the final call is a method call.
Sample Answer
Direct answer
Currying turns a function that takes several arguments at once into one that can take them across several calls. curry(fn) returns a function that stores the arguments it has seen so far and, as soon as it has as many as fn declares, calls fn with them. That count is the function's arity: the number of parameters it declares, read from fn.length. A placeholder is a special value that means "leave this position empty for now" (the code below uses a Symbol, a value that is never equal to anything else, and calls it _). The returned function fills the leftmost empty positions first, so add3(_, 2)(1)(3) works. this is preserved by calling the original function with fn.apply(receiver, args), where the receiver is the object written before the dot in a method call: in counter.addBase(1, 2) the receiver is counter, and it becomes this inside addBase.
Design decisions
- When is the function ready? When at least
arityarguments have been supplied and none of the firstaritypositions still holds the placeholder. A trailing placeholder beyondaritydoes not block the call. - How do later arguments land? Scan the stored list from the left. Each new argument fills the next empty slot. When no empty slot is left, the remaining arguments are appended. Passing the placeholder again leaves the slot empty, which is how
add3(_, _, 3)(_, 2)(1)fills slot 2, then slot 1, then slot 0. - No shared mutable state. Every call copies the stored list (
held.slice()), so a saved partial such asconst one = add3(1)can be reused without one caller's arguments leaking into another's. - Which
this? The call that completes the list is the one that runsfn, so its receiver wins:other.finish(2)runsfnwiththis === other. When the last call has no receiver (const f = counter.addBase(1); f(2)), the nearest earlier receiver is reused, socounter.addBase(1)(2)still seescounter. The returned function must be a regularfunction, not an arrow, because an arrow function ignores the receiver of the call. The same holds forfnitself: an arrowfncannot seethis. The fallback testthis === undefinedalso depends on strict mode: in an ES module or a class body a plain call has no receiver, but in a sloppy-mode script a plain call getsglobalThisasthis, the fallback never fires, andcounter.addBase(1)(2)loses its receiver. Put'use strict';at the top of such a script. - Variadic and default-parameter functions. A variadic function accepts any number of arguments through a rest parameter (
...n).fn.lengthcounts only the parameters before the first default and excludes a rest parameter (MDN,Function.length), so(...n) => ...has length 0 and would be called on the very first call. The optional second argumentarityfixes this. - Extra arguments beyond the arity are passed through to
fn, the same as callingfndirectly.
Worked example
The listing is one file. The first half is curry; the second half, under the harness comment, is a set of checks that throw on failure, followed by a negative control (a deliberately broken curry that shows the method-call checks can fail).
import assert from 'node:assert/strict';
const _ = Symbol('curry.placeholder');
function curry(fn, arity = fn.length) {
function collect(held, receiver) {
return function (...incoming) {
// Prefer the receiver of this call; fall back to the latest earlier receiver.
const self = this === undefined ? receiver : this;
const slots = held.slice();
let i = 0;
for (let s = 0; s < slots.length && i < incoming.length; s++) {
if (slots[s] === _) slots[s] = incoming[i++];
}
while (i < incoming.length) slots.push(incoming[i++]);
const ready =
slots.length >= arity && slots.slice(0, arity).every((v) => v !== _);
return ready ? fn.apply(self, slots) : collect(slots, self);
};
}
return collect([], undefined);
}
curry.placeholder = _;
// --- harness: every check throws on failure ---
const add3 = curry((a, b, c) => `${a}-${b}-${c}`);
assert.equal(add3(1)(2)(3), '1-2-3');
assert.equal(add3(1, 2)(3), '1-2-3');
assert.equal(add3(1)(2, 3), '1-2-3');
assert.equal(add3(_, 2)(1)(3), '1-2-3');
assert.equal(add3(_, _, 3)(1)(2), '1-2-3');
assert.equal(add3(_, _, 3)(_, 2)(1), '1-2-3');
assert.equal(add3(1, 2, 3, 4), '1-2-3'); // extra args are passed through to fn
// a partial is reusable: it never mutates the saved arguments
const one = add3(1);
assert.equal(one(2, 3), '1-2-3');
assert.equal(one(5, 6), '1-5-6');
// explicit arity for variadic / default-parameter functions
const sum = curry((...n) => n.reduce((x, y) => x + y, 0), 3);
assert.equal(sum(1)(2)(3), 6);
// this: the call that completes the argument list supplies the receiver
const counter = {
base: 100,
addBase: curry(function (a, b) { return this.base + a + b; }),
};
assert.equal(counter.addBase(1, 2), 103); // one call, method call
assert.equal(counter.addBase(1)(2), 103); // receiver captured at the first call
const other = { base: 200, finish: counter.addBase(1) };
assert.equal(other.finish(2), 203); // final call is the method call on `other`
console.log(add3(_, 2)(1)(3));
console.log(counter.addBase(1, 2), counter.addBase(1)(2), other.finish(2));
// negative control: a curry that ignores `this` fails the same checks
const naive = (fn) => {
const go = (held) => (...a) => {
const all = [...held, ...a];
return all.length >= fn.length ? fn(...all) : go(all);
};
return go([]);
};
const broken = { base: 100, addBase: naive(function (a, b) { return this?.base + a + b; }) };
console.log(broken.addBase(1, 2));
Run in a node:22 container, it prints:
1-2-3
103 103 203
NaN
Every assert in the file throws if it fails, so a silent run means all of them held. The last line comes from the negative control. naive is a curry that calls fn(...all) instead of fn.apply(self, slots). It proves the this checks are meaningful: without apply, the function runs with this undefined, this?.base is undefined, and undefined + 1 + 2 is NaN instead of 103.
Slot filling, step by step
The call add3(_, _, 3)(_, 2)(1) keeps a list of held slots. Each call fills the leftmost empty slots with its arguments in order; passing _ fills a slot with "still empty".
| Call | Arguments | Held slots afterwards |
|---|---|---|
add3(_, _, 3) | _, _, 3 | [_, _, 3]: two slots empty, so not ready |
(_, 2) | _, 2 | slot 0 is the first empty slot and receives _ (stays empty); slot 1 is the next empty slot and receives 2: [_, 2, 3] |
(1) | 1 | slot 0 is the first empty slot and receives 1: [1, 2, 3]. All three slots are filled, so fn runs and returns '1-2-3' |
Complexity
Each call copies the stored list and scans it once, so it costs O(k) for k stored arguments. Collecting n arguments one at a time costs O(n²) in total, which is irrelevant for the single-digit arities currying is used with. Space is O(n) per live partial. The final fn.apply costs whatever fn costs.
Edge cases and pitfalls
| Case | Behaviour |
|---|---|
curry(f)() with no arguments | Returns a new partial with the same state, never calls fn unless arity is 0 |
fn.length === 0 (rest or all-default parameters) | fn runs on the first call. Pass arity explicitly |
| A real argument that equals the placeholder | Impossible by construction, since the placeholder is a private Symbol exposed as curry.placeholder |
Passing undefined | A real value that fills a slot. Only the placeholder leaves a gap |
Arrow function as fn | this is the surrounding scope's, whatever receiver is supplied |
The common mistake is returning an arrow function from the wrapper (loses the receiver) or pushing into one shared args array (the second use of add3(1) sees the first use's leftovers).
Running the code
Save the listing as curry.mjs (the .mjs extension lets Node read the import line as an ES module) and run it with Node 22, which needs no packages:
node curry.mjs
Write your own version of Promise.allSettled for an environment that lacks it. It accepts an iterable of promises or plain values and resolves with one outcome per input in input order. Say how you would treat an empty input.
Sample Answer
Direct answer
allSettled returns a promise that waits for every input to finish, whether it succeeds or fails, and then fulfils with an array of outcome objects in the same order as the inputs. It never rejects because of an input. Each outcome is { status: 'fulfilled', value } or { status: 'rejected', reason }. Wrap each input in Promise.resolve so plain values and thenables (objects with a .then method) are handled, store each outcome at its input's index, and count down until every slot is filled. An empty input fulfils immediately with [], because there is nothing to wait for and the countdown would otherwise never reach zero.
Implementation
import assert from 'node:assert/strict';
function allSettled(iterable) {
return new Promise((resolve, reject) => {
let items;
try { items = [...iterable]; } catch (err) { reject(err); return; } // non-iterable input rejects, as the native method does
const results = new Array(items.length);
let pending = items.length;
if (pending === 0) { resolve(results); return; } // empty input: fulfil with [] right away
items.forEach((item, i) => {
Promise.resolve(item).then(
(value) => { results[i] = { status: 'fulfilled', value }; if (--pending === 0) resolve(results); },
(reason) => { results[i] = { status: 'rejected', reason }; if (--pending === 0) resolve(results); }
);
});
});
}
// a buggy version that stores results in completion order, to prove the checks can fail
function allSettledWrongOrder(iterable) {
return new Promise((resolve) => {
const items = [...iterable]; const out = [];
if (!items.length) return resolve(out);
items.forEach((item) => Promise.resolve(item).then(
(value) => { out.push({ status: 'fulfilled', value }); if (out.length === items.length) resolve(out); },
(reason) => { out.push({ status: 'rejected', reason }); if (out.length === items.length) resolve(out); }));
});
}
const delay = (ms, v, fail) => new Promise((res, rej) => setTimeout(() => (fail ? rej(v) : res(v)), ms));
const thenable = { then(ok) { ok('from thenable'); } };
const rejectingThenable = { then(_ok, no) { no('nope'); } };
const cases = {
'mixed, slow first': () => [delay(30, 'slow'), 7, delay(10, 'boom', true), thenable],
'empty array': () => [],
'string is iterable': () => 'ab',
'set': () => new Set([1, Promise.resolve(2)]),
'generator': () => (function* () { yield delay(5, 'g1'); yield Promise.reject(new Error('g2')); })(),
'falsy values and reasons': () => [undefined, null, 0, '', NaN, Promise.reject(undefined), Promise.reject(null), rejectingThenable],
};
// a result that never arrives or an unexpected rejection becomes a FAIL line, not a hang or a crash
const settleWithin = (p, ms = 500) => {
let timer;
const limit = new Promise((_, rej) => { timer = setTimeout(() => rej(new Error('never settled')), ms); });
return Promise.race([p, limit]).finally(() => clearTimeout(timer));
};
async function check(name, impl) {
const failures = [];
for (const [label, make] of Object.entries(cases)) {
try {
const [mine, native] = await Promise.all([settleWithin(impl(make())), Promise.allSettled(make())]);
assert.deepStrictEqual(mine, native);
} catch (e) { failures.push(label + (e?.message === 'never settled' ? ' (never settled)' : '')); }
}
for (const bad of [5, undefined, {}]) {
const m = await settleWithin(impl(bad)).then(() => 'resolved', (e) => e.constructor.name);
const n = await Promise.allSettled(bad).then(() => 'resolved', (e) => e.constructor.name);
if (m !== n) failures.push(`non-iterable ${String(bad)}: ${m} vs ${n}`);
}
console.log(name.padEnd(22), failures.length ? 'FAIL -> ' + failures.join('; ') : 'PASS');
}
await check('allSettled', allSettled);
await check('allSettledWrongOrder', allSettledWrongOrder);
console.log(JSON.stringify(await allSettled([delay(30, 'slow'), 7, delay(10, 'boom', true)])));
console.log(JSON.stringify(await allSettled([])));
Run in a node:22 container (Node v22), it prints:
allSettled PASS
allSettledWrongOrder FAIL -> mixed, slow first; generator
[{"status":"fulfilled","value":"slow"},{"status":"fulfilled","value":7},{"status":"rejected","reason":"boom"}]
[]
The first two lines come from the check harness. In it, delay(ms, v, fail) builds a promise that settles after a timer, thenable and rejectingThenable are plain objects with a then method, and cases is a table of input factories (a function per case, so each implementation gets fresh promises). For each case it awaits both implementations at once and compares them with assert.deepStrictEqual, which treats two Error objects with the same name and message as equal and also checks that values such as undefined, null, 0, '' and NaN come back unchanged. It compares the polyfill's output with the built-in Promise.allSettled on six inputs (a mix where the slow promise is first, an empty array, a string, a Set, a generator, and a list of falsy values and falsy rejection reasons) and on three non-iterable inputs (5, undefined, {}), which must reject with the same error type as the built-in. settleWithin races each polyfill call against a 500 ms limit and every case sits in a try, so an implementation that never settles or that rejects prints a FAIL line naming the case (for example FAIL -> empty array (never settled) when the empty-input check is removed) and does not hang or crash the script. The second implementation deliberately stores results in completion order; the harness fails it on the slow-first case and on the generator, which shows the order check can fail. The last two lines show the real outputs: the slow promise stays first in the array although it settles last, and [] for the empty input.
How it works
A trace on three inputs makes the countdown concrete: [delay(30, 'slow'), 7, delay(10, 'boom', true)]. The array has length 3, so pending starts at 3 and results has three empty slots. The plain 7 is wrapped by Promise.resolve and its callback runs first, in a microtask: results[1] becomes { status: 'fulfilled', value: 7 } and pending drops to 2. After 10 ms the third input rejects: results[2] becomes { status: 'rejected', reason: 'boom' } and pending is 1. After 30 ms the first input fulfils: results[0] is filled, pending reaches 0 and the outer promise resolves with the array, in input order.
- Collect the input.
[...iterable]accepts anything iterable (an object that can be walked withfor...ofor spread: arrays, strings, Sets, generators) and throws aTypeErrorfor non-iterables. Because that throw happens inside thenew Promiseexecutor, it becomes a rejection of the returned promise, so a bad argument produces a rejected promise and not a synchronous exception. (The explicittry/catchmakes that visible; the executor would convert the throw into a rejection on its own.) - Normalise each item with
Promise.resolve(item). A real promise passes through unchanged, a plain value becomes an already-fulfilled promise, and a thenable is adopted. - Record by index, not by arrival. The callbacks write to
results[i], whereiis the item's position in the input. Completion order is irrelevant. This is what the broken variant gets wrong withpush. - Handle both outcomes in one
.then(onFulfilled, onRejected)call. Both callbacks resolve the outer promise only when the countdown (pending) reaches zero. Passing the rejection handler as the second argument ofthenmeans a rejected input is turned into data, so there is no unhandled rejection and the outer promise never rejects. - Empty input.
pendingstarts at 0, no callback will ever run, so the code resolves right away with[].
Running the code
Save the listing as all-settled.mjs (the .mjs extension lets Node read import and top-level await as an ES module) and run it with Node 22, which needs no packages:
node all-settled.mjs
Complexity and edge cases
- Time is O(n) work to attach handlers, plus whatever the inputs take; the result completes when the slowest input does. Space is O(n) for the results array.
- Rejection reasons can be anything, including
undefined. Because the code stores an object per outcome,{ status: 'rejected', reason: undefined }is distinguishable from a fulfilledundefined, which a bare array of values could not do. - Timing of the callbacks.
.thencallbacks always run asynchronously (as microtasks: small jobs the engine runs right after the current code finishes and before any timer), even for already-settled inputs, so the outer promise settles asynchronously for an empty input as well: the promise is already fulfilled but its.thenhandlers still run later. - Subclasses. The built-in calls
this.resolveso thatMySubclass.allSettledreturns an instance of the subclass. A subclass is a class built withclass MyPromise extends Promise; a simple polyfill that uses the globalPromisedoes not; mention it if asked, and it is rarely needed. - Feature detection. Install it only when it is missing:
if (!Promise.allSettled) Promise.allSettled = allSettled;. Replacing a native implementation gains nothing and loses details such as subclass support. - Contrast with the neighbours.
Promise.allrejects on the first rejection,Promise.anyfulfils on the first fulfilment, andPromise.racesettles with the first outcome of either kind.allSettledis the one to use when partial failure is a normal result, for example loading several independent dashboard widgets and showing an error card for each one that failed.
Implement a minimal virtual DOM diff in vanilla JavaScript. Given two simplified virtual trees whose children may carry keys, produce the list of DOM operations needed to update the real DOM, minimizing moves in reordered lists. Text nodes are plain strings.
Sample Answer
Direct answer
A virtual DOM (VDOM) is a plain JavaScript description of the page: { tag, key, props, children } objects, with text as strings. Diffing compares the previous description with the next one and emits a short list of changes (insert, remove, move, set text, set or remove an attribute, replace), and a separate step applies that list to the real DOM. The comparison walks both trees together: nodes of the same kind are updated in place; nodes of a different kind are replaced. For children, nodes are matched by key when they have one (otherwise by position), unmatched old children are removed, unmatched new ones are inserted, and the matched ones that are out of order are moved. To minimise moves, keep the longest group of matched children that is already in the right relative order (a longest increasing subsequence, LIS, of their old positions) and move only the others.
Implementation
Operations name existing nodes by their child-index path in the OLD tree (old:0.2 is the third child of the root element) and new nodes by their path in the new tree (new:0.3). Because an old path never changes while the patch is applied, earlier moves cannot invalidate later references. An insert or move says which sibling it goes in front of (before), the way the DOM method insertBefore works.
import assert from 'node:assert/strict';
import { JSDOM } from 'jsdom';
// h('li', { key: 'a', class: 'x' }, 'text', h(...)) -> { tag, key, props, children }; text nodes are plain strings
const h = (tag, props = {}, ...children) => {
const { key, ...rest } = props;
return { tag, key, props: rest, children };
};
const identity = (child, i) => (typeof child === 'string' || child.key === undefined ? `#${i}` : `k:${child.key}`);
// longest increasing subsequence of a number array; returns the set of POSITIONS in arr that are kept
function lisPositions(arr) {
const tails = [], prev = new Array(arr.length).fill(-1);
arr.forEach((v, i) => {
let lo = 0, hi = tails.length;
while (lo < hi) { const mid = (lo + hi) >> 1; if (arr[tails[mid]] < v) lo = mid + 1; else hi = mid; }
if (lo > 0) prev[i] = tails[lo - 1];
tails[lo] = i;
});
const keep = new Set();
for (let i = tails[tails.length - 1]; i !== undefined && i !== -1; i = prev[i]) keep.add(i);
return keep;
}
// Ops address an EXISTING node as "old:<path>" (its child-index path in the old tree) and a NEW node as "new:<path>".
function diff(oldTree, newTree, pickStable = lisPositions) {
const ops = [];
const oldRef = (p) => 'old:' + p.join('.');
const newRef = (p) => 'new:' + p.join('.');
function diffNode(o, n, oPath, nPath) {
const sameKind = typeof o === 'string' ? typeof n === 'string' : typeof n !== 'string' && o.tag === n.tag;
if (!sameKind) { ops.push({ op: 'replace', ref: oldRef(oPath), newRef: newRef(nPath), node: n }); return; }
if (typeof o === 'string') { if (o !== n) ops.push({ op: 'setText', ref: oldRef(oPath), text: n }); return; }
for (const k of Object.keys(o.props)) if (!(k in n.props)) ops.push({ op: 'removeAttr', ref: oldRef(oPath), name: k });
for (const [k, v] of Object.entries(n.props)) if (o.props[k] !== v) ops.push({ op: 'setAttr', ref: oldRef(oPath), name: k, value: v });
diffChildren(o.children, n.children, oPath, nPath);
}
function diffChildren(oKids, nKids, oPath, nPath) {
const oldIndexOf = new Map();
oKids.forEach((c, i) => {
const id = identity(c, i);
if (oldIndexOf.has(id)) throw new Error('duplicate key ' + id);
oldIndexOf.set(id, i);
});
const nIds = nKids.map(identity);
const nIdSet = new Set(nIds);
if (nIdSet.size !== nIds.length) throw new Error('duplicate key among new children');
oKids.forEach((c, i) => { if (!nIdSet.has(identity(c, i))) ops.push({ op: 'remove', ref: oldRef([...oPath, i]) }); });
// for each new child: the index of its match among the old children, or -1 when it is new
const match = nIds.map((id) => (oldIndexOf.has(id) ? oldIndexOf.get(id) : -1));
const matchedPositions = match.map((m, i) => (m === -1 ? -1 : i)).filter((i) => i !== -1);
const stable = pickStable(matchedPositions.map((i) => match[i]));
const stableNew = new Set([...stable].map((j) => matchedPositions[j])); // new indices that never move
const parent = oldRef(oPath);
for (let i = nKids.length - 1; i >= 0; i--) { // right to left: the next sibling is already in its final place
const before = i + 1 < nKids.length ? (match[i + 1] === -1 ? newRef([...nPath, i + 1]) : oldRef([...oPath, match[i + 1]])) : null;
if (match[i] === -1) ops.push({ op: 'insert', parent, before, ref: newRef([...nPath, i]), node: nKids[i] });
else if (!stableNew.has(i)) ops.push({ op: 'move', ref: oldRef([...oPath, match[i]]), parent, before });
}
nKids.forEach((c, i) => { if (match[i] !== -1) diffNode(oKids[match[i]], c, [...oPath, match[i]], [...nPath, i]); });
}
diffNode(oldTree, newTree, [0], [0]); // both trees are wrapped as the single child 0 of a container
return ops;
}
// ---- applier: runs the ops on a real DOM (jsdom) ----
function render(doc, v) {
if (typeof v === 'string') return doc.createTextNode(v);
const el = doc.createElement(v.tag);
for (const [k, val] of Object.entries(v.props)) el.setAttribute(k, val);
v.children.forEach((c) => el.appendChild(render(doc, c)));
return el;
}
function applyOps(container, oldTree, ops) {
const doc = container.ownerDocument, refs = new Map();
(function index(node, path) { refs.set('old:' + path.join('.'), node); [...node.childNodes].forEach((c, i) => index(c, [...path, i])); })(container.firstChild, [0]);
for (const o of ops) {
const at = (r) => (r === null ? null : refs.get(r));
switch (o.op) {
case 'remove': at(o.ref).remove(); break;
case 'insert': { const n = render(doc, o.node); refs.set(o.ref, n); at(o.parent).insertBefore(n, at(o.before)); break; }
case 'move': at(o.parent).insertBefore(at(o.ref), at(o.before)); break;
case 'setText': at(o.ref).nodeValue = o.text; break;
case 'setAttr': at(o.ref).setAttribute(o.name, o.value); break;
case 'removeAttr': at(o.ref).removeAttribute(o.name); break;
case 'replace': { const old = at(o.ref), n = render(doc, o.node); refs.set(o.newRef, n); old.replaceWith(n); break; }
default: throw new Error('unknown op ' + o.op);
}
}
}
const html = (v) => (typeof v === 'string' ? v : `<${v.tag}${Object.entries(v.props).map(([k, x]) => ` ${k}="${x}"`).join('')}>${v.children.map(html).join('')}</${v.tag}>`);
// ---- example with readable output ----
const li = (k, text, props = {}) => h('li', { key: k, ...props }, text);
const before = h('ul', { class: 'list' }, li('a', 'Apple'), li('b', 'Banana'), li('c', 'Cherry'), li('d', 'Date'), li('e', 'Elder'));
const after = h('ul', { class: 'list wide', id: 'fruits' }, li('b', 'Banana'), li('c', 'Cherry'), li('d', 'Date'), li('f', 'Fig'), li('a', 'Apricot'));
const ops = diff(before, after);
console.log(ops.map((o) => JSON.stringify(o.node ? { ...o, node: html(o.node) } : o)).join('\n'));
const dom = new JSDOM('<div id="root"></div>');
const root = dom.window.document.getElementById('root');
root.appendChild(render(dom.window.document, before));
const keptNodes = Object.fromEntries([...root.firstChild.children].map((e) => [e.textContent, e]));
applyOps(root, before, ops);
console.log('after patch :', root.innerHTML);
assert.equal(root.innerHTML, html(after));
const nowByKey = Object.fromEntries([...root.firstChild.children].map((e) => [e.textContent, e]));
assert.equal(nowByKey.Banana, keptNodes.Banana); // same DOM objects: nothing was re-created
assert.equal(nowByKey.Apricot, keptNodes.Apple); // the moved node kept its identity and got new text
console.log('ops:', ops.length, ' moves:', ops.filter((o) => o.op === 'move').length);
// duplicate keys are rejected, whether they sit in the old tree or the new one
const dup = h('ul', {}, li('x', '1'), li('x', '2'));
assert.throws(() => diff(dup, before), /duplicate key/);
assert.throws(() => diff(before, dup), /duplicate key/);
// ---- fuzz: patched DOM must equal a fresh render of the new tree, surviving keyed nodes must be the same objects ----
function rng(seed) { return () => { seed |= 0; seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
function randomTree(r, depth = 0) {
const pick = (a) => a[Math.floor(r() * a.length)];
const n = depth === 0 ? 2 + Math.floor(r() * 8) : Math.floor(r() * 4);
const keys = [...'abcdefghij'].sort(() => r() - 0.5).slice(0, n);
const kids = keys.map((k) => {
const x = r();
if (x < 0.15) return pick(['hi', 'yo', 'ok']);
const props = r() < 0.5 ? { class: pick(['p', 'q']) } : {};
if (r() < 0.7) props.key = k;
return h(pick(['li', 'li', 'li', 'p']), props, ...(depth < 2 ? randomTree(r, depth + 1).children : []));
});
return h('ul', r() < 0.5 ? { id: pick(['u', 'v']) } : {}, ...kids);
}
function check(pickStable, seeds) {
const failures = [];
for (let seed = 1; seed <= seeds; seed++) {
const r = rng(seed), a = randomTree(r), b = randomTree(r);
const d = new JSDOM('<div id="root"></div>'); const rt = d.window.document.getElementById('root');
rt.appendChild(render(d.window.document, a));
const before = new Map();
a.children.forEach((c, i) => { if (typeof c !== 'string' && c.key !== undefined) before.set(c.key, { tag: c.tag, el: rt.firstChild.childNodes[i] }); });
try {
applyOps(rt, a, diff(a, b, pickStable));
assert.equal(rt.innerHTML, html(b));
b.children.forEach((c, i) => {
const was = typeof c !== 'string' && c.key !== undefined ? before.get(c.key) : undefined;
if (was && was.tag === c.tag) assert.equal(rt.firstChild.childNodes[i], was.el); // keyed node kept: same DOM object
});
} catch { failures.push(seed); }
}
return failures;
}
const none = () => new Set(); // nothing is declared stable: correct but wasteful
const everything = (arr) => new Set(arr.keys()); // everything declared stable: nothing moves, order breaks
console.log('fuzz 500 seeds, real LIS : failures =', check(undefined, 500).length);
console.log('fuzz 500 seeds, everything stable: failures =', check(everything, 500).length > 0 ? 'some (detected)' : 0);
// ---- minimality: every permutation of up to 6 keyed items, compared with the true minimum found by breadth-first search ----
const perms = (a) => (a.length <= 1 ? [a] : a.flatMap((x, i) => perms([...a.slice(0, i), ...a.slice(i + 1)]).map((p) => [x, ...p])));
function minMoves(n) { // BFS over "take one item out and put it anywhere"
const start = [...Array(n).keys()].join(','), dist = new Map([[start, 0]]); let frontier = [start.split(',').map(Number)];
while (frontier.length) {
const next = [];
for (const p of frontier) for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
if (i === j) continue; const q = [...p]; q.splice(j, 0, q.splice(i, 1)[0]); const k = q.join(',');
if (!dist.has(k)) { dist.set(k, dist.get(p.join(',')) + 1); next.push(q); }
}
frontier = next;
}
return dist;
}
function minimalityFailures(pickStable) {
let bad = 0, total = 0;
for (let n = 1; n <= 6; n++) {
const best = minMoves(n);
for (const p of perms([...Array(n).keys()])) {
const mk = (order) => h('ul', {}, ...order.map((i) => li('k' + i, 'x')));
const o = diff(mk([...Array(n).keys()]), mk(p), pickStable);
total++; if (o.length !== best.get(p.join(','))) bad++;
}
}
return `${bad} of ${total} permutations not minimal`;
}
console.log('minimal moves, real LIS :', minimalityFailures(undefined));
console.log('minimal moves, nothing stable:', minimalityFailures(none));
Run in a node:22 container (Node v22, jsdom, a DOM implementation in JavaScript), it prints:
{"op":"setAttr","ref":"old:0","name":"class","value":"list wide"}
{"op":"setAttr","ref":"old:0","name":"id","value":"fruits"}
{"op":"remove","ref":"old:0.4"}
{"op":"move","ref":"old:0.0","parent":"old:0","before":null}
{"op":"insert","parent":"old:0","before":"old:0.0","ref":"new:0.3","node":"<li>Fig</li>"}
{"op":"setText","ref":"old:0.0.0","text":"Apricot"}
after patch : <ul class="list wide" id="fruits"><li>Banana</li><li>Cherry</li><li>Date</li><li>Fig</li><li>Apricot</li></ul>
ops: 6 moves: 1
fuzz 500 seeds, real LIS : failures = 0
fuzz 500 seeds, everything stable: failures = some (detected)
minimal moves, real LIS : 0 of 873 permutations not minimal
minimal moves, nothing stable: 873 of 873 permutations not minimal
Reading the output
The operations come from the right-to-left loop in diffChildren. For the new list Banana, Cherry, Date, Fig, Apricot, match is [1, 2, 3, -1, 0] (the old index of each new child, or -1 for Fig, which is new), and the lis step marks the first three as stable. Going from the last child to the first: Apricot (a) is not stable and is last, so it moves before null (the end); Fig is new, so it is inserted before the node that follows it, which is a (old:0.0); Date, Cherry and Banana are stable and produce nothing.
The example list goes from Apple, Banana, Cherry, Date, Elder to Banana, Cherry, Date, Fig, Apricot (Apple's key is a, and its text changed). The six operations fall into five groups:
- Two attribute updates on the
ul(classchanged,idadded). removeofold:0.4, the Elder item (keyeis gone).- One
move: itemagoes to the end (before: null). Banana, Cherry and Date (old positions 1, 2, 3) are already in increasing order, so they stay put; onlya(old position 0) breaks the order. - One
insert: Fig is created in front ofa. Operations are produced from the last child to the first so the "next sibling" they refer to is always already in its final place. - One
setTexton the text node insidea, which changes "Apple" into "Apricot".
The applied patch gives exactly the markup of the new tree, and the checks confirm that the Banana element is the same DOM object as before and that the moved a element kept its identity but shows the new text: nothing was destroyed and rebuilt.
Walking lisPositions on a small array
The argument to lisPositions is the list of old positions of the matched children, in new order. For the example list it is [1, 2, 3, 0] (Banana, Cherry, Date, then Apple). tails[k] holds the position in arr of the smallest possible last value of an increasing run of length k + 1 found so far, and prev[i] remembers which element came just before i in its run. For each value, a binary search finds the first slot whose tail value is not smaller than it, and the value takes that slot.
Position i | Value | Slot chosen | tails after | prev after |
|---|---|---|---|---|
| 0 | 1 | 0 | [0] | [-1, -1, -1, -1] |
| 1 | 2 | 1 | [0, 1] | [-1, 0, -1, -1] |
| 2 | 3 | 2 | [0, 1, 2] | [-1, 0, 1, -1] |
| 3 | 0 | 0 | [3, 1, 2] | [-1, 0, 1, -1] |
The final loop starts at the last entry of tails (position 2) and follows prev back: 2, then 1, then 0, then -1 stops it. The kept positions are {0, 1, 2}, the values 1, 2, 3. Position 3 (the value 0, which is Apple) is not kept, so it is the one child that moves. For [2, 0, 1, 3] the same procedure keeps positions 1, 2 and 3 (the values 0, 1, 3), so only the child at position 0 moves.
Why keys, and why LIS
- Without keys, an inserted item at the front makes every following item look "changed" (item 1 vs the old item 0, and so on), so each is rewritten and any state inside it (focus, input text) is attached to the wrong item. With keys the algorithm finds that the items merely shifted.
- Moving an element is a real DOM mutation that the browser has to lay out again, so fewer moves is better. If you walked the new list left to right and moved every out-of-place item, turning
[A, B, C, D]into[B, C, D, A]would move B, C and D (three moves) when moving A once is enough. LIS finds the largest set that can stay, so the number of moves is the number of matched children minus the LIS length.
Verification
- Fuzz test: fuzzing means feeding a program many random inputs and checking a property that must always hold. Here the test builds 500 random pairs of trees (nested elements, text nodes, keyed and unkeyed children, tag changes, attribute changes) from a seeded generator, which starts from a fixed number so the same 500 pairs appear on every run. For each pair, the patched DOM must serialise exactly as the new tree and every keyed child of the root list that survives with the same tag must be the same DOM object. With the real LIS there were no failures. The same fuzz with a deliberately wrong "everything is stable" choice fails, so the check can detect a wrong diff.
- Minimality test: for every ordering (permutation) of up to six keyed items (873 cases in total), the number of operations equals the true minimum number of single-item moves. The minimum comes from breadth-first search: starting from the original order, try every one-move reordering, then every two-move reordering, and so on, so the first time a target order appears gives its smallest move count. The real LIS has zero cases above the minimum. A variant that declares nothing stable (so every matched child moves) is above the minimum in all 873, so that check can fail too.
Complexity, edge cases and limits
- Per parent, matching is O(n) with a map, and the LIS step is O(n log n) using binary search; the whole diff is O(N log N) for N nodes in the worst case (a reordered list) because the algorithm only compares nodes that sit under the same parent. Space is O(N) for the operation list and maps.
- Duplicate keys among siblings, in the old or the new tree, are an error: the code throws, because the match would be ambiguous. The listing asserts both throws, and deleting either check makes it fail.
- Mixed keyed and unkeyed children: unkeyed ones are matched by position, and a keyed child never matches an unkeyed one.
- Different tags (
libecomesp) or text versus element: replace the whole subtree, and do not diff the children of the two. - Moving a child to a different parent is not detected: it is a remove plus an insert (a new element), which is the same simplification real libraries make.
- Not covered: event handlers, DOM properties versus attributes (such as an input's
value), SVG namespaces and component state. These belong to the renderer around the diff, not to the list-diff itself.
Running the code
Save the listing as vdom.mjs (the .mjs extension lets Node read import as an ES module) and run it with Node 22:
npm i jsdom
node vdom.mjs
The output above was produced with jsdom 30.1.2.
Implement mergeDeep(target, source) for nested plain objects where arrays in the source replace those in the target. Source must not be mutated. Discuss the edge cases and how the array policy would change if the business rule were to combine arrays instead.
Sample Answer
Direct answer
Walk the two objects key by key. When both sides hold a plain object, recurse. In every other case (scalar, null, an array, or two different types) the source value wins, and an array is copied rather than merged. Build a fresh result instead of writing into target, and copy everything you take from source, so neither input is mutated and the result shares no nested objects with either. A "plain object" means an object whose prototype (the object it inherits properties from; most objects inherit from Object.prototype) is Object.prototype or null; Dates, Maps, class instances and the like are treated as opaque values and replaced whole.
Implementation
The same function also supports the other array rules through one option, so the business-rule change in the question is a parameter and not a rewrite: replace (the default), concat (append everything) and union (append only items not already present, compared with a pluggable equals).
import assert from 'node:assert/strict';
const isPlainObject = (v) => {
if (v === null || typeof v !== 'object') return false;
const proto = Object.getPrototypeOf(v);
return proto === Object.prototype || proto === null;
};
// Copies plain objects and arrays all the way down so the result shares no references with its inputs.
function clone(v) {
if (Array.isArray(v)) return v.map(clone);
if (isPlainObject(v)) {
const out = {};
for (const k of Object.keys(v)) if (k !== '__proto__') out[k] = clone(v[k]);
return out;
}
return v; // primitives, Dates, Maps, functions: kept as the same value
}
const sameValueZero = (a, b) => a === b || (a !== a && b !== b);
function mergeDeep(target, source, { arrays = 'replace', equals = sameValueZero } = {}) {
const mergeArrays = (a, b) => {
if (arrays === 'replace') return clone(b);
if (arrays === 'concat') return [...clone(a), ...clone(b)];
if (arrays === 'union') {
const out = clone(a);
for (const item of b) if (!out.some((x) => equals(x, item))) out.push(clone(item));
return out;
}
throw new RangeError(`unknown array policy: ${arrays}`);
};
const merge = (t, s) => {
if (isPlainObject(t) && isPlainObject(s)) {
const out = {};
for (const k of Object.keys(t)) {
if (k === '__proto__') continue; // an own "__proto__" key from JSON.parse must never reach the prototype
const sv = Object.hasOwn(s, k) ? s[k] : undefined;
out[k] = sv === undefined ? clone(t[k]) : merge(t[k], sv); // undefined means "no opinion"; null is a real value and overrides
}
for (const k of Object.keys(s)) {
if (k === '__proto__' || s[k] === undefined || Object.hasOwn(out, k)) continue;
out[k] = clone(s[k]);
}
return out;
}
if (Array.isArray(t) && Array.isArray(s)) return mergeArrays(t, s);
return clone(s); // scalar, null, or conflicting types: the source wins
};
return merge(target, source);
}
// ---- checks ----
const deepFreeze = (o) => { if (o && typeof o === 'object') { Object.values(o).forEach(deepFreeze); Object.freeze(o); } return o; };
const target = { a: 1, db: { host: 'x', ports: [1, 2], opts: { ssl: true } }, tags: ['a', 'b'], n: { k: 1 } };
const source = { a: null, db: { ports: [3], opts: { retries: 2 } }, tags: ['b', 'c'], n: 5, z: undefined };
const tSnap = JSON.stringify(target), sSnap = JSON.stringify(source);
deepFreeze(target); deepFreeze(source); // a write to either input would throw in strict mode (ES modules)
const r = mergeDeep(target, source);
console.log('replace :', JSON.stringify(r));
assert.deepEqual(r, { a: null, db: { host: 'x', ports: [3], opts: { ssl: true, retries: 2 } }, tags: ['b', 'c'], n: 5 });
assert.equal(JSON.stringify(target), tSnap); assert.equal(JSON.stringify(source), sSnap);
assert.notEqual(r.db.ports, source.db.ports); // no aliasing: mutating the result cannot reach the source
assert.ok(!('z' in r));
const u = mergeDeep(target, source, { arrays: 'union' });
console.log('union :', JSON.stringify(u));
assert.deepEqual(u.tags, ['a', 'b', 'c']); assert.deepEqual(u.db.ports, [1, 2, 3]);
const c = mergeDeep(target, source, { arrays: 'concat' });
console.log('concat :', JSON.stringify(c.tags), JSON.stringify(c.db.ports));
assert.deepEqual(c.tags, ['a', 'b', 'b', 'c']);
// no aliasing anywhere: no object or array in a result is also reachable from either input
const refsOf = (o, seen = new Set()) => {
if (o && typeof o === 'object' && !(o instanceof Date)) { seen.add(o); Object.values(o).forEach((x) => refsOf(x, seen)); }
return seen;
};
const shares = (a, b) => { const A = refsOf(a); return [...refsOf(b)].some((x) => A.has(x)); };
const t2 = deepFreeze({ a: { b: [1] }, c: { x: 1 } });
const s2 = deepFreeze({ a: { n: { d: [2] } }, c: [{ y: 1 }], e: { f: 1 }, g: [{ h: 1 }] });
for (const policy of ['replace', 'concat', 'union']) {
const m = mergeDeep(t2, s2, { arrays: policy });
assert.ok(!shares(m, t2) && !shares(m, s2), `aliasing under ${policy}`);
const top = mergeDeep(deepFreeze([{ x: 1 }]), deepFreeze([{ y: 2 }]), { arrays: policy }); // arrays at the root
assert.ok(top.length >= 1);
}
const topT = deepFreeze([{ x: 1 }]), topS = deepFreeze([{ y: 2 }]);
const topU = mergeDeep(topT, topS, { arrays: 'union' });
assert.deepEqual(topU, [{ x: 1 }, { y: 2 }]);
assert.ok(!shares(topU, topT) && !shares(topU, topS));
// nested arrays and objects inside arrays need a custom equality, otherwise they are compared by reference
const rows = mergeDeep({ r: [[1], { id: 1 }] }, { r: [[1], { id: 1 }] }, { arrays: 'union' });
console.log('union, default equality :', JSON.stringify(rows.r));
assert.equal(rows.r.length, 4);
const byJson = (a, b) => JSON.stringify(a) === JSON.stringify(b);
const rows2 = mergeDeep({ r: [[1], { id: 1 }] }, { r: [[1], { id: 1 }] }, { arrays: 'union', equals: byJson });
console.log('union, JSON-string equality:', JSON.stringify(rows2.r));
assert.equal(rows2.r.length, 2);
// prototype pollution attempt
const evil = JSON.parse('{"__proto__":{"polluted":true},"ok":1}');
const p = mergeDeep({}, evil);
assert.equal({}.polluted, undefined); assert.equal(p.polluted, undefined); assert.equal(p.ok, 1);
const q = mergeDeep(evil, { ok: 2 }); // the hostile key can also sit in the target
assert.equal(Object.getPrototypeOf(q), Object.prototype); assert.equal(q.polluted, undefined); assert.equal(q.ok, 2);
console.log('__proto__ key ignored; Object.prototype.polluted =', {}.polluted);
// a naive version, for contrast, does pollute
const naive = (t, s) => { for (const k in s) { if (s[k] && typeof s[k] === 'object') { t[k] = t[k] || {}; naive(t[k], s[k]); } else t[k] = s[k]; } return t; };
naive({}, evil);
console.log('naive merge on same input: Object.prototype.polluted =', {}.polluted);
delete Object.prototype.polluted;
// type conflict and Date
const d = new Date(0);
const tc = mergeDeep({ a: { x: 1 }, d: 1 }, { a: [1], d });
console.log('type conflict:', JSON.stringify(tc), tc.d === d);
Run in a node:22 container (Node v22), it prints:
replace : {"a":null,"db":{"host":"x","ports":[3],"opts":{"ssl":true,"retries":2}},"tags":["b","c"],"n":5}
union : {"a":null,"db":{"host":"x","ports":[1,2,3],"opts":{"ssl":true,"retries":2}},"tags":["a","b","c"],"n":5}
concat : ["a","b","b","c"] [1,2,3]
union, default equality : [[1],{"id":1},[1],{"id":1}]
union, JSON-string equality: [[1],{"id":1}]
__proto__ key ignored; Object.prototype.polluted = undefined
naive merge on same input: Object.prototype.polluted = true
type conflict: {"a":[1],"d":"1970-01-01T00:00:00.000Z"} true
Why each decision was made
- Fresh result, deep copies, tested for every path. The checks walk each result and assert that no object or array in it is also reachable from either input, for all three array policies, for a source key that does not exist in the target, for an object replaced by an array, and for arrays at the root; removing any one of the
clonecalls makes that assertion fail. - Deep copies.
clonecopies plain objects and arrays all the way down. Without it,merge({}, {a: {b: 1}})would return an object whoseais the very object insidesource(aliasing: two names for one object), and a later write to the result would silently change the input. ThedeepFreezecalls in the checks make that class of bug throw: both inputs are frozen, so any write to them fails (ES modules run in strict mode, the JavaScript mode in which writing to a frozen object throws instead of failing silently). - Arrays replace by default. An array is an ordered whole (a list of ports, an allow-list). Merging element by element by index would produce hybrids such as
[3, 2]out of[1, 2]and[3], which no caller wants. Sodb.portsbecomes[3]. nulloverrides,undefineddoes not.nullis a deliberate "no value" in config files and JSON, soa: nullwins.undefinedis treated as "this key was not provided", soz: undefinedleaves the result untouched. Either rule is defensible; the point is to choose one and state it.- Type conflicts: the source wins.
n: {k: 1}merged withn: 5becomes5, anda: {x: 1}merged witha: [1]becomes[1]. Trying to merge an object with an array would produce something that is neither. - Prototype pollution.
JSON.parse('{"__proto__": {...}}')creates an own property literally named__proto__. A naivefor...inmerge that recurses intotarget['__proto__']writes ontoObject.prototypeitself and affects every object in the process; the run above shows the naive version settingObject.prototype.pollutedwhile this one leaves itundefined. The function therefore skips that key, whether it arrives in the source or in the target (aJSON.parsed target holds the same hostile key), and usesObject.keys, which returns only an object's own properties (not inherited ones), only the enumerable ones (the ordinary kind that loops andJSON.stringifysee) and only string keys, so inherited properties are never visited. A two-line example of the danger:const evil = JSON.parse('{"__proto__":{"polluted":true}}')gives an object with an own key named__proto__; a merge that doestarget['__proto__'] = ...or recurses intotarget['__proto__']reachesObject.prototypeitself, after which({}).pollutedistruefor every object in the program.
Changing the array rule: combine instead of replace
{ arrays: 'union' } gives tags: ['a','b','c'] and ports: [1,2,3] in the run above. Edge cases that come with combining:
- Duplicates need an equality definition. The default
sameValueZero(===plusNaNequal toNaN) works for strings and numbers. For arrays of objects it compares by reference, so two copies of{id: 1}are both kept. Pass a stable-key comparison ((a, b) => a.id === b.id) when items have identities. TheJSON.stringifycomparison in the run handles nested arrays and objects but depends on key order, so it is a quick check and not a general answer. - Order is part of the contract. Union keeps the target's order and appends new items from the source in source order. If the business wants source-first, swap the arguments or add a policy.
concatkeeps duplicates, which is correct for things like log lines and wrong for tags.- Who wins on a matching element? With keyed items (
{id: 1, name: 'a'}in both), "union" may really mean "merge items with the same id". That is a fourth policy and needs anidKeyoption. - Nested arrays (arrays of arrays) are treated as single items, as the run shows.
Remaining edge cases
- Cycles. A self-referencing object makes
clonerecurse forever and overflow the stack. Config data from JSON cannot have cycles; for arbitrary objects, track visited nodes in aWeakMapor throw a clear error. - Non-plain values (Dates, Maps, RegExps, class instances) are kept by reference. The last line of the run ends in
true, meaningtc.d === d: the result holds the very sameDateobject, so the "no shared references" guarantee covers plain objects and arrays only. - Symbol keys and non-enumerable properties are ignored by
Object.keys. UseReflect.ownKeysif they matter. - Getters are read once and the resulting value is copied, so the result holds data and not the accessor.
Running the code
Save the listing as merge.mjs (the .mjs extension makes Node read import as an ES module) and run it with Node 22, which needs no packages:
node merge.mjs
Complexity
Time is O(p) for replace and concat, where p counts the nodes of both inputs once per path from the root (for tree-shaped data, which is what JSON gives, that is simply the number of nodes): every such node is cloned or merged exactly once, because merge clones only the target keys the source does not touch and recurses into the rest. (Cloning the whole target object at every level of recursion would be O(p times depth): measured when merging two chains that are each 1,000 levels deep, ending in {x: 1} and {y: 1}, that version made 502,503 clone calls, where this one makes 2, one per leaf value, because every key on the chain is merged and nothing needs copying until the leaf.) The bound does not hold for shared references. Neither clone nor merge remembers what it has already copied, so an object reachable by two paths is copied once per path. Measured with mergeDeep({}, source) on a source where each level references the next level twice and the last object holds one number (k + 1 distinct objects), clone is called 3,070 times for k = 10, 98,302 for k = 15 and 3,145,726 for k = 20: exponential in the number of distinct objects, though still linear in paths. Config data parsed from JSON cannot share objects, so this only matters for hand-built graphs; to keep such input linear, memoize clone in a WeakMap from input object to its copy (which also preserves the sharing inside the result, while still sharing nothing with the inputs). union with the default equals is O(m times k) for arrays of m and k items because of the some scan; replace it with a Set of keys when items are primitives or have a key function. Space is O(n) for the new result plus recursion depth equal to the nesting depth.
Write a React hook in TypeScript that returns a debounced copy of a value. It should work for any value type, optionally return the first value immediately, avoid updating state after unmount, avoid recreating timers needlessly, and let the caller force a pending value through right away. Walk through the edge cases.
Sample Answer
A debounced value hook keeps the value it shows in state and a timer in a ref. When the input value changes it does not show the new value yet: it remembers it as "pending" and restarts a timer, and only when the timer finishes quietly does the pending value become the shown one. A hook is a function component's way of keeping state and side effects across renders; an effect (useEffect) is code React runs after rendering and can undo with a cleanup function. A ref (useRef) is a box React keeps across renders; writing to its .current does not trigger a re-render, which suits a timer id. A render is one run of the component function, and unmount means the component is removed from the screen. useCallback and useMemo return the same function or object on every render until their dependency list (the array of values they watch) changes. Object.is(a, b) is the strict same-value comparison React uses for state; unlike === it treats NaN as equal to itself. Five requirements shape the design: any value type, an optional immediate first value, no update after unmount, no needless timers, and a flush that forces the pending value through.
Design decisions
- Any type. The pending value is stored in a box,
{ value }, and "nothing pending" isnull. Testingif (pending)on the raw value would dropundefined,0,''andfalse. The tests showundefinedandnullpropagating. - First value immediately. On first render the hook returns the input as-is (the state starts with it). With
leading: true, the first change after a quiet period is also shown at once, and the delay then guards the rest of the burst. - No update after unmount. A separate effect whose cleanup calls
cancelclears the timer when the component unmounts, so no timer outlives it and nothing callssetStatelater. The test counts live timers: 0 after unmount. - No needless timers. The value effect depends on
[value, set]only.delayandleadingare copied into a ref that is read when a change arrives. Passing a fresh{ leading }object on every render therefore starts nothing, and neither does re-rendering with the same value (compared withObject.is, the same equality React uses for state). A change back to the value that is already shown drops the pending update and, outside leading mode, the timer. - Force it through.
flush()clears the timer and applies the pending value synchronously.
A trace of the setter shows how the branches fit together. Take the shown value 'a', leading: false and a 300 ms delay. set('ab'): Object.is('ab', 'a') is false and no leading shortcut applies, so the ref pending becomes { value: 'ab' } and one timer starts. set('a') 100 ms later: Object.is('a', 'a') is true, so pending becomes null and clear() cancels the timer. Nothing is pending, no timer is alive, and the screen never changed. Had the second call been set('abc'), the old timer would be cleared, pending would become { value: 'abc' }, and a new 300 ms timer would start; when it fires, commit (the helper that applies the pending value) calls show('abc') once.
The hooks
useDebouncedState holds the logic and gives a useState-like setter. useDebouncedValue is a thin wrapper that feeds a prop or state value into that setter. The setter takes a value, not an updater function, because an updater would have to run against a state that the debounce has not applied yet.
import { useCallback, useEffect, useMemo, useRef, useState } from 'react';
export interface DebounceControls {
flush(): void; // apply the pending update now
cancel(): void; // drop the pending update
isPending(): boolean;
}
export interface DebounceOptions {
leading?: boolean; // apply the first update of a burst immediately
}
// useState-like: the setter is debounced, `flush` applies the pending update at once.
export function useDebouncedState<T>(
initial: T,
delay: number,
{ leading = false }: DebounceOptions = {}
): [T, (next: T) => void, DebounceControls] {
const [shown, setShown] = useState<T>(initial);
const shownRef = useRef<T>(initial); // what `shown` will be after the last setState
const pending = useRef<{ value: T } | null>(null); // boxed, so undefined and null are legal values
const timer = useRef<ReturnType<typeof setTimeout> | undefined>(undefined);
// delay and leading are read at call time, so changing them never recreates anything
const config = useRef({ delay, leading });
useEffect(() => {
config.current = { delay, leading };
});
const show = useCallback((v: T) => {
shownRef.current = v;
setShown(v);
}, []);
const clear = useCallback(() => {
if (timer.current !== undefined) clearTimeout(timer.current);
timer.current = undefined;
}, []);
const commit = useCallback(() => {
timer.current = undefined;
const p = pending.current;
pending.current = null;
if (p) show(p.value);
}, [show]);
const set = useCallback(
(next: T) => {
if (Object.is(next, shownRef.current)) {
pending.current = null; // the user came back to what is already shown
if (!config.current.leading) clear();
return;
}
if (config.current.leading && timer.current === undefined) {
show(next);
pending.current = null;
} else {
pending.current = { value: next };
}
clear();
timer.current = setTimeout(commit, config.current.delay);
},
[show, clear, commit]
);
const controls = useMemo<DebounceControls>(
() => ({
flush: () => {
clear();
commit();
},
cancel: () => {
clear();
pending.current = null;
},
isPending: () => pending.current !== null,
}),
[clear, commit]
);
// Unmount: no timer may outlive the component.
useEffect(() => controls.cancel, [controls]);
return [shown, set, controls];
}
// A debounced copy of a value of any type.
export function useDebouncedValue<T>(
value: T,
delay: number,
options?: DebounceOptions
): [T, DebounceControls] {
const [debounced, set, controls] = useDebouncedState(value, delay, options);
useEffect(() => {
set(value); // runs only when the value changes (Object.is), never for a new options object
}, [value, set]);
return [debounced, controls];
}
Tests that render the hook
The harness renders with React 18 and Testing Library under jsdom (a simulated browser DOM for Node), with virtual timers and a count of live timers. mock.timers from node:test replaces setTimeout so tick(ms) moves the clock by hand; the lines after it wrap setTimeout and clearTimeout once more so the live set holds every timer that has been started and not yet fired or cleared, and created counts every start. act makes React finish its updates before the next line runs. Probe is a component that calls the hook and copies what it returns into out, so assertions can read the shown value and the render count from outside; mount renders it and returns a set function that re-renders with a new input value, the way a parent would.
import assert from 'node:assert/strict';
import { mock } from 'node:test';
import { StrictMode } from 'react';
import { JSDOM } from 'jsdom';
import { useDebouncedState, useDebouncedValue, type DebounceControls } from './useDebounced.js';
const dom = new JSDOM('<!doctype html><body></body>');
Object.assign(globalThis, { window: dom.window, document: dom.window.document });
Object.defineProperty(globalThis, 'navigator', { value: dom.window.navigator, configurable: true });
(globalThis as any).IS_REACT_ACT_ENVIRONMENT = true;
const { render, act } = await import('@testing-library/react');
mock.timers.enable({ apis: ['setTimeout'], now: 0 });
// Count timers so tests can prove "no needless timers" and "none left after unmount".
const live = new Set<unknown>();
let created = 0;
const mockedSet = globalThis.setTimeout;
const mockedClear = globalThis.clearTimeout;
globalThis.setTimeout = ((fn: () => void, ms?: number) => {
created++;
const id = mockedSet(() => { live.delete(id); fn(); }, ms);
live.add(id);
return id;
}) as typeof setTimeout;
globalThis.clearTimeout = ((id: any) => { live.delete(id); mockedClear(id); }) as typeof clearTimeout;
const tick = (ms: number) => act(() => { mock.timers.tick(ms); });
type Out<T> = { shown?: T; controls?: DebounceControls; renders: number };
function Probe<T>({ value, delay, leading, out }: { value: T; delay: number; leading?: boolean; out: Out<T> }) {
const [shown, controls] = useDebouncedValue(value, delay, { leading }); // new options object every render
out.shown = shown;
out.controls = controls;
out.renders++;
return null;
}
const mount = <T,>(value: T, delay: number, leading?: boolean, strict = false) => {
const out: Out<T> = { renders: 0 };
const el = (v: T) => {
const probe = <Probe value={v} delay={delay} leading={leading} out={out} />;
return strict ? <StrictMode>{probe}</StrictMode> : probe;
};
const view = render(el(value));
return { out, view, set: (v: T) => view.rerender(el(v)) };
};
const log: string[] = [];
// 1. Trailing: the debounced value follows 300 ms after the last change.
{
const { out, set } = mount('a', 300);
set('ab'); tick(100); set('abc');
tick(299); assert.equal(out.shown, 'a');
tick(1); assert.equal(out.shown, 'abc');
log.push(`trailing a -> ${out.shown} after 400 ms`);
}
// 2. Leading: the first change shows at once, the rest settle after the delay.
{
const { out, set } = mount('a', 200, true);
set('b'); assert.equal(out.shown, 'b');
tick(50); set('c'); tick(50); set('d');
assert.equal(out.shown, 'b');
tick(199); assert.equal(out.shown, 'b');
tick(1); assert.equal(out.shown, 'd');
log.push(`leading shown b at once, then ${out.shown} after the quiet period`);
}
// 3. Any value type: undefined and null are real values, not "nothing pending".
{
const { out, set } = mount<number | undefined | null>(1, 100);
set(undefined); tick(100); assert.equal(out.shown, undefined);
set(null); tick(100); assert.equal(out.shown, null);
log.push('falsy values undefined and null both pass through');
}
// 4. No needless timers: re-rendering with the same pending value and a fresh options object
// must not restart the countdown that is already running.
{
const { out, set } = mount('x', 100);
set('xy');
const before = created;
tick(40);
set('xy'); set('xy');
assert.equal(created, before, 'no timer was started by the re-renders');
tick(59); assert.equal(out.shown, 'x');
tick(1); assert.equal(out.shown, 'xy', 'it fired 100 ms after the change, not after the re-renders');
log.push(`needless timers ${created - before} created by 2 re-renders while a change was pending`);
}
// 5. flush(): the caller forces the pending value through.
{
const { out, set } = mount('q', 500);
set('qu'); assert.equal(out.shown, 'q'); assert.equal(out.controls!.isPending(), true);
act(() => out.controls!.flush());
assert.equal(out.shown, 'qu'); assert.equal(out.controls!.isPending(), false); assert.equal(live.size, 0);
log.push(`flush shown ${out.shown} with 0 live timers`);
}
// 6. Unmount: nothing is left running and nothing renders afterwards.
{
const { out, view, set } = mount('a', 300);
set('b');
assert.equal(live.size, 1);
const rendersBefore = out.renders;
view.unmount();
assert.equal(live.size, 0, 'the timer is cleared on unmount');
tick(1000);
assert.equal(out.renders, rendersBefore);
log.push(`unmount live timers ${live.size}, renders after unmount ${out.renders - rendersBefore}`);
}
// 7. React StrictMode runs effects twice in development; the result must be the same.
{
const { out, set } = mount('a', 300, false, true);
set('b'); tick(300);
assert.equal(out.shown, 'b');
log.push('strict mode a -> b after 300 ms');
}
// 8. useDebouncedState: a useState-like setter with flush().
{
let api!: ReturnType<typeof useDebouncedState<string>>;
function Form() { api = useDebouncedState('', 400); return null; }
render(<Form />);
act(() => api[1]('dra')); act(() => api[1]('draft'));
assert.equal(api[0], '');
act(() => api[2].flush());
assert.equal(api[0], 'draft');
log.push(`useDebouncedState flush -> ${api[0]}`);
}
console.log(log.join('\n'));
Compiled with TypeScript 5 and run in a node:22 container, it prints:
trailing a -> abc after 400 ms
leading shown b at once, then d after the quiet period
falsy values undefined and null both pass through
needless timers 0 created by 2 re-renders while a change was pending
flush shown qu with 0 live timers
unmount live timers 0, renders after unmount 0
strict mode a -> b after 300 ms
useDebouncedState flush -> draft
Deleting the unmount effect makes the "timer is cleared on unmount" assertion fail, and removing the Object.is guard makes the suite fail as well, so the checks can detect those bugs. Adding options to the dependency list of the value effect in useDebouncedValue makes the "no timer was started by the re-renders" assertion fail, because every re-render would then restart the countdown that is already running.
Edge cases walked through
| Situation | What the hook does |
|---|---|
| Value changes 3 times in 100 ms | One timer at a time; shown value changes once, after the last change plus the delay |
Value changes to undefined | Pending box { value: undefined } is applied, not skipped |
| Same value re-rendered | Object.is match, no pending update, no timer |
User types ab, then back to the shown a | Pending update dropped; the timer is cleared (non-leading) so nothing flickers |
| Component unmounts mid-countdown | Cleanup runs cancel: timer cleared, pending dropped |
delay prop changes | Applies to the next change; the running timer is not restarted |
| Enter pressed | Caller invokes flush() and the pending value is shown now |
| React StrictMode (development mode that runs each effect's setup, cleanup, setup once extra) | Same result: the extra cycle runs at mount, when nothing is pending |
Trade-offs
- The input change renders once with the old shown value, and the timer's
setShowncauses a second render when it fires. That second render is the price of delaying a value: render code cannot wait, so a timer plus state is the standard shape. useMemofor the controls object is a performance cache only: React documents that it may discard cached values, so nothing here depends on the controls staying identical. The correctness-critical state lives in refs anduseState.- Debouncing a value delays the display of the value. Debounce the effect (for example the fetch) by running it on the debounced value, so the typed text in the input still updates on every keystroke.
- Each change is O(1) work, with one timer and one pending box alive at a time.
Running the code
Save the hook as useDebounced.ts and the test as useDebounced.test.tsx next to a package.json containing { "type": "module" } and this tsconfig.json:
{ "compilerOptions": { "target": "ES2022", "module": "NodeNext", "moduleResolution": "NodeNext",
"jsx": "react-jsx", "strict": true, "outDir": "dist", "skipLibCheck": true },
"include": ["*.ts", "*.tsx"] }
Then, with Node 22:
npm i react@18 react-dom@18 @testing-library/react@14 jsdom typescript@5 @types/react@18 @types/react-dom@18 @types/node@22 @types/jsdom
npx tsc && node dist/useDebounced.test.js
Unlock Full Question Bank
Get access to all 21 Polyfills and JavaScript Utility Implementation interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.