Write a higher-order function memoize(fn) that returns a new function with the same behaviour as fn, except results are cached by argument. Repeat calls with the same argument skip fn entirely and return the cached value. This is the classic memoization pattern — a single-argument wrapper backed by a Map, useful for pure functions that are expensive to recompute.
// Returns a wrapped version of `fn` that caches by its single argument.
// Subsequent calls with an argument already in the cache return the stored
// result and DO NOT invoke `fn` again.
function memoize<A, R>(fn: (arg: A) => R): (arg: A) => R;let calls = 0;
const square = memoize((n) => {
calls++;
return n * n;
});
square(5); // 25 (calls === 1)
square(5); // 25 (calls === 1 — cache hit, fn not invoked)
square(6); // 36 (calls === 2 — distinct arg, fn invoked once more)
square(5); // 25 (calls === 2 — still cached)// Different argument types each get their own cache entry.
const id = memoize((x) => x);
id(1); // 1
id('1'); // '1' (a separate slot — string '1' !== number 1)
id(null); // null
id(undefined); // undefined
id({ a: 1 }); // { a: 1 } (cached by reference, not by shape)memoize wraps unary functions. Don't try to handle (a, b) here — that's a multi-arg variant and is out of scope for this question.Map, keyed on the argument as-is. Use new Map() (not a plain object). The argument is the key directly — no JSON.stringify, no coercion. That means lookup is reference equality for objects/arrays, value equality for primitives.fn on a cache hit. Even if the cached value is undefined, a second call with the same argument must return the stored undefined without calling fn. Use cache.has(key) to test presence, not cache.get(key) (which can't distinguish "missing" from "stored undefined").fn returned the first time for that argument — no cloning, no freezing.this. Tests call the memoized function as a plain function. You can ignore Function.prototype.call/apply binding for this exercise.You'll wrap a function in another function so that repeat calls with the same argument return a stored answer instead of recomputing — the classic memoization pattern, backed by a closure-scoped Map.
Some functions are deterministic but expensive: a naive recursive Fibonacci, a parser that re-runs on the same string, a layout calculator called with the same DOM node. Calling them with the same input twice does identical work both times. Memoization records the answer the first time and serves it from a lookup table on every subsequent call with the same input. You trade memory (one cache entry per distinct argument) for speed (no recomputation).
A memoized function has two pieces wired together by a closure — a function that remembers variables from where it was defined. The outer piece is memoize itself: it runs once, creates a private Map, and returns the inner piece. The inner piece is the function the caller actually invokes; on every call it consults the cache, returns a hit if it has one, and otherwise calls the original fn, stores the answer, and returns it.
The flow inside one call is a single branch — hit or miss — and the miss path always stores the freshly computed result before returning it, so the next call with the same argument becomes a hit.
A reasonable first instinct is to lean on a plain object for the cache, because object literals are the most familiar key-value container in JS:
function memoize(fn) {
const cache = {};
return function (arg) {
if (cache[arg]) return cache[arg]; // hit?
const result = fn(arg);
cache[arg] = result;
return result;
};
}This breaks in three concrete ways. First, cache[arg] coerces arg to a string before indexing. So memoize(fn)(1) and memoize(fn)('1') end up writing to the same key "1" — the first call's result clobbers the second, even though 1 !== '1'. Second, object keys for objects coerce to the literal string "[object Object]", so fn({ id: 1 }) and fn({ id: 2 }) collide on a single cache slot. Third, the if (cache[arg]) check fails for any falsy cached value — call memoize(() => 0)(7) once and the result 0 is stored, but the next call sees the falsy 0, treats it as a miss, and calls fn again. Same problem with cached undefined, null, '', and false.
Each of those is a real bug a beginner ships. The fix is to use the right data structure (Map, not {}) and the right presence check (has, not truthiness).
function memoize(fn) {
// One Map per memoize() call. Living in the outer scope means it persists
// across every invocation of the returned function — that's the closure.
const cache = new Map();
// The returned function is what the caller invokes. It captures `cache` and
// `fn` from the surrounding scope.
return function (arg) {
// `has` distinguishes "key absent" from "key present but value is undefined".
// If we only checked `cache.get(arg)` truthiness, a cached 0 / '' / null /
// undefined would look like a miss and we'd re-invoke fn — defeating the cache.
if (cache.has(arg)) {
return cache.get(arg);
}
// Cache miss. Invoke the original function exactly once for this argument.
const result = fn(arg);
// Store the result under the argument key. For object args, the Map keys by
// reference — two distinct objects with the same shape get separate entries.
cache.set(arg, result);
return result;
};
}
module.exports = { memoize };Three shifts from the naive version. new Map() instead of {} means object keys stay objects (no toString coercion) and primitive keys keep their type (number 1 and string '1' are different keys). cache.has(arg) instead of truthiness means a stored undefined/null/0/''/false is still a hit — the test is "is there an entry?", not "is the entry truthy?". The cache lives in the closure, not on the returned function, so it's private; nothing outside memoize can read or clear it.
Trace four calls against the same memoized function:
let calls = 0;
const slow = memoize((n) => {
calls++;
return n * 2;
});
slow(5); // call 1
slow(5); // call 2
slow(6); // call 3
slow(5); // call 4slow(5). Inside the returned function, arg = 5. cache.has(5) is false — the Map is empty. We fall through to fn(5), which increments calls to 1 and returns 10. cache.set(5, 10). Return 10. Cache state: { 5 => 10 }.slow(5). arg = 5. cache.has(5) is now true. We return cache.get(5) → 10. fn is NOT invoked; calls stays at 1. This is the cache hit — the entire point of memoization.slow(6). arg = 6. cache.has(6) is false — different key, no entry. Fall through to fn(6), which increments calls to 2 and returns 12. cache.set(6, 12). Return 12. Cache state: { 5 => 10, 6 => 12 }.slow(5). arg = 5. cache.has(5) is still true (entries are never evicted). Return 10. calls stays at 2.After four calls, calls === 2 — fn ran exactly twice, once per distinct argument. That ratio (distinct-args : total-calls) is the leverage memoization gives you; the bigger the gap, the bigger the win.
The shape of that win is most dramatic on functions with overlapping subproblems. A recursive Fibonacci is the textbook case:
cache[arg] truthiness instead of cache.has(arg). Call const f = memoize(x => x); f(0); f(0); — with truthiness, the second call sees cache[0] === 0, treats it as a miss, and re-invokes the wrapped function. With has, it's a hit. Same trap for cached null, undefined, '', and false.{} as the cache. cache[{ id: 1 }] = 'a'; cache[{ id: 2 }] = 'b'; both stringify to "[object Object]" — they overwrite each other in a single slot. Map keys by identity for non-primitives, so two distinct objects get two distinct entries. (See the diagram below.)fn({ id: 1 }) then fn({ id: 1 }) — are two cache misses. The Map sees two different references and stores two entries. If you actually need shape-based caching, you'd serialize the argument (see Going further), but that's a different and slower beast.memoize instances. Don't hoist the Map to module scope; keep it inside memoize so each call to memoize(someFn) gets its own. Otherwise memoize(double) and memoize(triple) would step on each other — calling either with 5 would return whichever wrote first.fn(5) returns Date.now() or reads a mutable global, the first call's result is frozen into the cache forever. Subsequent calls return stale data and you'll lose hours debugging why your "fresh timestamp" never updates. Only memoize pure, deterministic functions of their argument.memoize libraries accept (a, b, c) and need a composite cache key. Two common shapes: a nested Map<a, Map<b, Map<c, R>>> (handles object args without serializing), or a single flat Map keyed on a string built from the args (cheap but loses identity for object args and is wrong for circular refs). lodash's memoize defaults to using only the first argument as the key, which is precisely the unary version above — a sharp edge worth knowing.Map in a least-recently-used policy: every get re-inserts the key (which moves it to the end of Map's insertion order), and when size exceeds a cap you delete the first key. About 10 extra lines, turns this into a production-grade utility.fn({ id: 1 }) and fn({ id: 1 }) to hit the same slot, use a WeakMap keyed by an interned canonical object (heavyweight) or fall back to JSON.stringify(arg) (cheap, but fails on circular references and on objects with Date/Map/Set/undefined values — JSON.stringify quietly drops or mangles those). There is no free lunch; pick the failure mode that matches your data.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Write a higher-order function memoize(fn) that returns a new function with the same behaviour as fn, except results are cached by argument. Repeat calls with the same argument skip fn entirely and return the cached value. This is the classic memoization pattern — a single-argument wrapper backed by a Map, useful for pure functions that are expensive to recompute.
// Returns a wrapped version of `fn` that caches by its single argument.
// Subsequent calls with an argument already in the cache return the stored
// result and DO NOT invoke `fn` again.
function memoize<A, R>(fn: (arg: A) => R): (arg: A) => R;let calls = 0;
const square = memoize((n) => {
calls++;
return n * n;
});
square(5); // 25 (calls === 1)
square(5); // 25 (calls === 1 — cache hit, fn not invoked)
square(6); // 36 (calls === 2 — distinct arg, fn invoked once more)
square(5); // 25 (calls === 2 — still cached)// Different argument types each get their own cache entry.
const id = memoize((x) => x);
id(1); // 1
id('1'); // '1' (a separate slot — string '1' !== number 1)
id(null); // null
id(undefined); // undefined
id({ a: 1 }); // { a: 1 } (cached by reference, not by shape)memoize wraps unary functions. Don't try to handle (a, b) here — that's a multi-arg variant and is out of scope for this question.Map, keyed on the argument as-is. Use new Map() (not a plain object). The argument is the key directly — no JSON.stringify, no coercion. That means lookup is reference equality for objects/arrays, value equality for primitives.fn on a cache hit. Even if the cached value is undefined, a second call with the same argument must return the stored undefined without calling fn. Use cache.has(key) to test presence, not cache.get(key) (which can't distinguish "missing" from "stored undefined").fn returned the first time for that argument — no cloning, no freezing.this. Tests call the memoized function as a plain function. You can ignore Function.prototype.call/apply binding for this exercise.You'll wrap a function in another function so that repeat calls with the same argument return a stored answer instead of recomputing — the classic memoization pattern, backed by a closure-scoped Map.
Some functions are deterministic but expensive: a naive recursive Fibonacci, a parser that re-runs on the same string, a layout calculator called with the same DOM node. Calling them with the same input twice does identical work both times. Memoization records the answer the first time and serves it from a lookup table on every subsequent call with the same input. You trade memory (one cache entry per distinct argument) for speed (no recomputation).
A memoized function has two pieces wired together by a closure — a function that remembers variables from where it was defined. The outer piece is memoize itself: it runs once, creates a private Map, and returns the inner piece. The inner piece is the function the caller actually invokes; on every call it consults the cache, returns a hit if it has one, and otherwise calls the original fn, stores the answer, and returns it.
The flow inside one call is a single branch — hit or miss — and the miss path always stores the freshly computed result before returning it, so the next call with the same argument becomes a hit.
A reasonable first instinct is to lean on a plain object for the cache, because object literals are the most familiar key-value container in JS:
function memoize(fn) {
const cache = {};
return function (arg) {
if (cache[arg]) return cache[arg]; // hit?
const result = fn(arg);
cache[arg] = result;
return result;
};
}This breaks in three concrete ways. First, cache[arg] coerces arg to a string before indexing. So memoize(fn)(1) and memoize(fn)('1') end up writing to the same key "1" — the first call's result clobbers the second, even though 1 !== '1'. Second, object keys for objects coerce to the literal string "[object Object]", so fn({ id: 1 }) and fn({ id: 2 }) collide on a single cache slot. Third, the if (cache[arg]) check fails for any falsy cached value — call memoize(() => 0)(7) once and the result 0 is stored, but the next call sees the falsy 0, treats it as a miss, and calls fn again. Same problem with cached undefined, null, '', and false.
Each of those is a real bug a beginner ships. The fix is to use the right data structure (Map, not {}) and the right presence check (has, not truthiness).
function memoize(fn) {
// One Map per memoize() call. Living in the outer scope means it persists
// across every invocation of the returned function — that's the closure.
const cache = new Map();
// The returned function is what the caller invokes. It captures `cache` and
// `fn` from the surrounding scope.
return function (arg) {
// `has` distinguishes "key absent" from "key present but value is undefined".
// If we only checked `cache.get(arg)` truthiness, a cached 0 / '' / null /
// undefined would look like a miss and we'd re-invoke fn — defeating the cache.
if (cache.has(arg)) {
return cache.get(arg);
}
// Cache miss. Invoke the original function exactly once for this argument.
const result = fn(arg);
// Store the result under the argument key. For object args, the Map keys by
// reference — two distinct objects with the same shape get separate entries.
cache.set(arg, result);
return result;
};
}
module.exports = { memoize };Three shifts from the naive version. new Map() instead of {} means object keys stay objects (no toString coercion) and primitive keys keep their type (number 1 and string '1' are different keys). cache.has(arg) instead of truthiness means a stored undefined/null/0/''/false is still a hit — the test is "is there an entry?", not "is the entry truthy?". The cache lives in the closure, not on the returned function, so it's private; nothing outside memoize can read or clear it.
Trace four calls against the same memoized function:
let calls = 0;
const slow = memoize((n) => {
calls++;
return n * 2;
});
slow(5); // call 1
slow(5); // call 2
slow(6); // call 3
slow(5); // call 4slow(5). Inside the returned function, arg = 5. cache.has(5) is false — the Map is empty. We fall through to fn(5), which increments calls to 1 and returns 10. cache.set(5, 10). Return 10. Cache state: { 5 => 10 }.slow(5). arg = 5. cache.has(5) is now true. We return cache.get(5) → 10. fn is NOT invoked; calls stays at 1. This is the cache hit — the entire point of memoization.slow(6). arg = 6. cache.has(6) is false — different key, no entry. Fall through to fn(6), which increments calls to 2 and returns 12. cache.set(6, 12). Return 12. Cache state: { 5 => 10, 6 => 12 }.slow(5). arg = 5. cache.has(5) is still true (entries are never evicted). Return 10. calls stays at 2.After four calls, calls === 2 — fn ran exactly twice, once per distinct argument. That ratio (distinct-args : total-calls) is the leverage memoization gives you; the bigger the gap, the bigger the win.
The shape of that win is most dramatic on functions with overlapping subproblems. A recursive Fibonacci is the textbook case:
cache[arg] truthiness instead of cache.has(arg). Call const f = memoize(x => x); f(0); f(0); — with truthiness, the second call sees cache[0] === 0, treats it as a miss, and re-invokes the wrapped function. With has, it's a hit. Same trap for cached null, undefined, '', and false.{} as the cache. cache[{ id: 1 }] = 'a'; cache[{ id: 2 }] = 'b'; both stringify to "[object Object]" — they overwrite each other in a single slot. Map keys by identity for non-primitives, so two distinct objects get two distinct entries. (See the diagram below.)fn({ id: 1 }) then fn({ id: 1 }) — are two cache misses. The Map sees two different references and stores two entries. If you actually need shape-based caching, you'd serialize the argument (see Going further), but that's a different and slower beast.memoize instances. Don't hoist the Map to module scope; keep it inside memoize so each call to memoize(someFn) gets its own. Otherwise memoize(double) and memoize(triple) would step on each other — calling either with 5 would return whichever wrote first.fn(5) returns Date.now() or reads a mutable global, the first call's result is frozen into the cache forever. Subsequent calls return stale data and you'll lose hours debugging why your "fresh timestamp" never updates. Only memoize pure, deterministic functions of their argument.memoize libraries accept (a, b, c) and need a composite cache key. Two common shapes: a nested Map<a, Map<b, Map<c, R>>> (handles object args without serializing), or a single flat Map keyed on a string built from the args (cheap but loses identity for object args and is wrong for circular refs). lodash's memoize defaults to using only the first argument as the key, which is precisely the unary version above — a sharp edge worth knowing.Map in a least-recently-used policy: every get re-inserts the key (which moves it to the end of Map's insertion order), and when size exceeds a cap you delete the first key. About 10 extra lines, turns this into a production-grade utility.fn({ id: 1 }) and fn({ id: 1 }) to hit the same slot, use a WeakMap keyed by an interned canonical object (heavyweight) or fall back to JSON.stringify(arg) (cheap, but fails on circular references and on objects with Date/Map/Set/undefined values — JSON.stringify quietly drops or mangles those). There is no free lunch; pick the failure mode that matches your data.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.