Detailed explanation
Memoization is an optimisation technique that stores a function’s computed result against its input arguments. When the function is called again with the same inputs, it returns the cached result instead of repeating the computation. It trades additional memory for reduced work and is most useful when expensive calculations repeatedly receive the same inputs. A cache hit is not literally instantaneous: looking up the key and returning the value still have a cost.
In the supplied example, memo creates a Map and returns a wrapper function. The wrapper closes over the Map, so the cache survives between calls without becoming global. For each argument n, c.has(n) checks whether a result exists; c.get(n) retrieves it. On a miss, fn(n) runs, c.set(n, result) stores its return value, and that value is returned. Using has rather than checking whether get returns a truthy value correctly handles cached results such as 0, false, and undefined. This wrapper supports only one argument and does not preserve the caller’s this binding.
The Fibonacci example works because recursive calls use fib, which refers to the memoized wrapper by the time computation starts. For a non-negative integer n, each distinct Fibonacci subproblem is computed once. Under the usual constant-cost arithmetic assumption, this reduces exponential recursive work to O(n) time, with O(n) cached entries and O(n) recursion depth. Memoizing only an outer call while internal recursion bypasses the wrapper would not eliminate repeated subproblems. JavaScript’s recursion limits and Number precision still apply, so memoization does not make this implementation suitable for arbitrarily large n.
Memoization is safest for pure functions: their results depend only on their arguments, and skipping execution does not skip required side effects. Interviewers also look for practical cache design. Map compares object keys by identity, not structural equality, so two separately created but identical-looking objects produce different entries. Multi-argument functions need a deliberate keying strategy. Long-lived caches may require eviction or invalidation, while cached mutable objects can expose shared state to callers. The optimisation is worthwhile only when saved computation outweighs cache-management costs.
Key points to remember
- Memoization caches results by input to avoid repeated computation.
- Pure functions are the safest candidates because cache hits skip execution.
- The example uses a closure to retain a single-argument Map cache.
- Recursive calls must pass through the memoized wrapper to reuse subproblem results.
- Key design, memory growth, invalidation, and shared mutable results affect correctness.
Common mistakes candidates make
- Checking cached values for truthiness, which incorrectly treats 0, false, or undefined as cache misses.
- Assuming Map compares objects by content or that JSON.stringify safely keys every possible input.
- Memoizing time-dependent or side-effecting functions without accounting for stale results or skipped effects.
Likely follow-up questions
How would you memoize a function with multiple arguments?
Use a keying strategy that represents the entire argument list, such as nested Maps keyed by each argument. Creating a fresh array as a Map key on every call will not work because arrays are compared by identity.
How is memoization different from dynamic programming?
Memoization is a caching technique commonly used in top-down dynamic programming to reuse overlapping subproblem results. Dynamic programming also includes bottom-up tabulation, which computes subproblems in a chosen order rather than through recursive cache lookups.
When should you avoid memoization?
Avoid it when inputs rarely repeat, computation is cheap, or skipping execution changes required behaviour. For long-lived caches with many distinct inputs, consider a size limit or eviction policy so memory usage remains controlled.
Interview tip: Define memoization, trace one cache miss and one hit in the example, then explain Fibonacci’s improvement and one cache-design limitation.