What is Memoization?
Learn memoization with a Fibonacci code example, step-by-step breakdown, and the difference from bottom-up tabulation.
Expected Interview Answer
Memoization is an optimization technique that caches the results of expensive function calls keyed by their arguments, so repeated calls with the same inputs return instantly instead of recomputing.
It is the top-down approach to dynamic programming: a recursive function checks a cache before doing work, and stores its result in the cache before returning. This turns algorithms with overlapping subproblems, like naive recursive Fibonacci, from exponential time down to linear or polynomial time by ensuring each unique subproblem is solved only once. Memoization trades memory for speed, since the cache must hold every distinct input seen so far. Interviewers use it to test whether you can spot overlapping subproblems and convert brute-force recursion into an efficient solution.
- Eliminates redundant recursive computation
- Converts exponential-time recursion to polynomial or linear time
- Simple to add on top of existing recursive code
- Foundation of top-down dynamic programming
AI Mentor Explanation
A statistician calculating a batter’s average against every bowling attack does not recompute it from raw ball-by-ball data each time it is asked for — the first calculation is cached, and every later request for that same batter-bowler pairing is an instant lookup. Only new, never-seen pairings trigger fresh computation. Memoization works identically: cache the result of a function call keyed by its inputs so identical future calls skip the work entirely.
Step-by-Step Explanation
Step 1
Identify overlapping subproblems
Check if the recursive calls repeat the same arguments multiple times, like naive Fibonacci.
Step 2
Add a cache
Use a dictionary or array keyed by function arguments to store computed results.
Step 3
Check cache before recursing
At the top of the function, return the cached value immediately if the input was already computed.
Step 4
Store before returning
After computing the result, write it to the cache before returning it up the call stack.
What Interviewer Expects
- Recognizing overlapping subproblems as the trigger for memoization
- Correctly choosing a cache key (often a tuple of arguments)
- Explaining the time complexity improvement (e.g. exponential to linear for Fibonacci)
- Distinguishing memoization (top-down) from tabulation (bottom-up)
Common Mistakes
- Forgetting to check the cache before doing the recursive work
- Using a mutable or unhashable cache key
- Applying memoization to functions with side effects, causing stale results
- Confusing memoization with plain caching of unrelated data
Best Answer (HR Friendly)
“Memoization means remembering the answer to a problem you have already solved so you never solve it twice — like keeping a lookup table of results next to a recursive function. It is the technique that turns slow, repetitive recursive algorithms like naive Fibonacci into fast ones by skipping redundant work.”
Code Example
def fibonacci(n, cache=None):
if cache is None:
cache = {}
if n in cache:
return cache[n]
if n <= 1:
return n
cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache)
return cache[n]Follow-up Questions
- What is the difference between memoization and tabulation?
- How does memoization change the time complexity of naive recursive Fibonacci?
- When can memoization be unsafe to apply to a function?
- How would you implement memoization as a reusable decorator?
MCQ Practice
1. What time complexity does memoization give naive recursive Fibonacci?
Memoization ensures each of the n unique subproblems is computed once, giving O(n) time.
2. Memoization is best described as which approach to dynamic programming?
Memoization caches results within a top-down recursive structure, unlike bottom-up tabulation.
3. What must a function have for memoization to be safe to apply?
Memoization assumes a pure function, since it reuses a cached result for identical inputs.
Flash Cards
Memoization — Caching function results keyed by input arguments to avoid redundant recomputation.
Top-down DP — Recursive dynamic programming that uses memoization to skip repeated subproblems.
Cache key — The function’s arguments, used to look up or store a previously computed result.
Requires purity — Memoization is only safe for pure functions with no side effects or randomness.