LeetCode Problem Workspace
Memoize
This problem focuses on creating a memoized function that caches results to prevent repeated computation with identical inputs efficiently.
0
Topics
1
Code langs
0
Related
Practice Focus
Medium · Memoize core interview pattern
Answer-first summary
This problem focuses on creating a memoized function that caches results to prevent repeated computation with identical inputs efficiently.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Memoize core interview pattern
Memoize requires wrapping a function so repeated calls with the same arguments return cached results without executing the original function again. It involves storing input-output pairs in a cache and updating a call counter only when the original function is actually invoked. This pattern tests understanding of closures, caching strategies, and call tracking within functional programming.
Problem Statement
Given a function fn that could be sum, factorial, or fib, return a memoized version that caches outputs for repeated inputs to avoid redundant calls. Each time the memoized function is called with new arguments, the result should be computed and stored, while repeated arguments should fetch the cached value.
Additionally, the memoized function should provide a method to return the number of times the original function was actually called. You can assume inputs are integers within the constraints, and only the actions 'call' or 'getCallCount' will be invoked on the memoized function.
Examples
Example 1
Input: fnName = "sum" actions = ["call","call","getCallCount","call","getCallCount"] values = [[2,2],[2,2],[],[1,2],[]]
Output: [4,4,1,3,2]
const sum = (a, b) => a + b; const memoizedSum = memoize(sum); memoizedSum(2, 2); // "call" - returns 4. sum() was called as (2, 2) was not seen before. memoizedSum(2, 2); // "call" - returns 4. However sum() was not called because the same inputs were seen before. // "getCallCount" - total call count: 1 memoizedSum(1, 2); // "call" - returns 3. sum() was called as (1, 2) was not seen before. // "getCallCount" - total call count: 2
Example 2
Input: fnName = "factorial" actions = ["call","call","call","getCallCount","call","getCallCount"] values = [[2],[3],[2],[],[3],[]]
Output: [2,6,2,2,6,2]
const factorial = (n) => (n <= 1) ? 1 : (n * factorial(n - 1)); const memoFactorial = memoize(factorial); memoFactorial(2); // "call" - returns 2. memoFactorial(3); // "call" - returns 6. memoFactorial(2); // "call" - returns 2. However factorial was not called because 2 was seen before. // "getCallCount" - total call count: 2 memoFactorial(3); // "call" - returns 6. However factorial was not called because 3 was seen before. // "getCallCount" - total call count: 2
Example 3
Input: fnName = "fib" actions = ["call","getCallCount"] values = [[5],[]]
Output: [8,1]
fib(5) = 8 // "call" // "getCallCount" - total call count: 1
Constraints
- 0 <= a, b <= 105
- 1 <= n <= 10
- 1 <= actions.length <= 105
- actions.length === values.length
- actions[i] is one of "call" and "getCallCount"
- fnName is one of "sum", "factorial" and "fib"
Solution Approach
Use a cache object
Create a dictionary or Map to store argument tuples as keys and function results as values. Check the cache first; if the input exists, return the cached value. Otherwise, call the original function, store the result, and increment the actual call count.
Handle variable function arguments
Spread function parameters into an array to handle arbitrary argument lengths, then convert this array to a string or tuple for caching. This ensures sum, factorial, or fib calls are properly memoized regardless of the number of inputs.
Expose call count
Attach a method to the memoized function that returns the total number of times the underlying function was invoked. This tracks actual computation, not repeated accesses from cache, which is critical for understanding the efficiency of memoization.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time and space complexity depend on how many unique input combinations are called. Each unique call requires storing its result, while repeated calls fetch cached results in constant time. Space grows with the number of unique calls.
What Interviewers Usually Probe
- Watch for correctly caching inputs to avoid duplicate computation.
- Check if the candidate can handle variable argument lengths in memoization.
- Ensure the solution tracks the actual function call count, not total calls to the wrapper.
Common Pitfalls or Variants
Common pitfalls
- Failing to convert argument arrays to a cacheable key, causing missed cache hits.
- Incrementing the call count even when returning cached results.
- Assuming only fixed numbers of arguments rather than supporting arbitrary input lengths.
Follow-up variants
- Memoize functions with multiple arguments including objects or arrays.
- Implement a time-limited cache where results expire after a set duration.
- Track both cache hits and misses to analyze memoization efficiency.
FAQ
What is the Memoize pattern in this LeetCode problem?
The Memoize pattern involves caching the results of function calls with specific inputs so repeated calls with the same arguments return the stored result without recomputation.
How do I handle variable numbers of function arguments?
Spread the arguments into an array and convert the array into a string or tuple to use as a cache key, ensuring all argument combinations are memoized correctly.
Why is tracking the actual function call count important?
It measures efficiency by counting only when the original function is executed, differentiating between cached and new computations.
Can memoization be used for recursive functions like fib?
Yes, memoization dramatically improves recursive calls like fib by storing previously computed results, preventing exponential recalculation.
What common mistakes should I avoid implementing Memoize?
Avoid missing cache hits due to improper key creation, incrementing call counts on cached returns, and assuming fixed argument lengths.
Solution
Solution 1
#### TypeScript
type Fn = (...params: any) => any;
function memoize(fn: Fn): Fn {
const cache: Record<any, any> = {};
return function (...args) {
if (args in cache) {
return cache[args];
}
const result = fn(...args);
cache[args] = result;
return result;
};
}
/**
* let callCount = 0;
* const memoizedFn = memoize(function (a, b) {
* callCount += 1;
* return a + b;
* })
* memoizedFn(2, 3) // 5
* memoizedFn(2, 3) // 5
* console.log(callCount) // 1
*/