Given a function fn, return a memoized version of that function.
A memoized function is a function that will never be called twice with the same inputs. Instead it will return a cached value.
You can assume there are 3 possible input functions: sum, fib, and factorial.
sum accepts two integers a and b and returns a + b. Assume that if a value has already been cached for the arguments (b, a) where a != b, it cannot be used for the arguments (a, b). For example, if the arguments are (3, 2) and (2, 3), two separate calls should be made.fib accepts a single integer n and returns 1 if n <= 1 or fib(n - 1) + fib(n - 2) otherwise.factorial accepts a single integer n and returns 1 if n <= 1 or factorial(n - 1) * n otherwise.Example 1:
Input: fnName = "sum" actions = ["call","call","getCallCount","call","getCallCount"] values = [[2,2],[2,2],[],[1,2],[]] Output: [4,4,1,3,2] Explanation: 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] Explanation: 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] Explanation: fib(5) = 8 // "call" // "getCallCount" - total call count: 1
Constraints:
0 <= a, b <= 1051 <= n <= 101 <= actions.length <= 105actions.length === values.lengthactions[i] is one of "call" and "getCallCount"fnName is one of "sum", "factorial" and "fib"The core idea behind Memoize is to cache the result of a function call so that repeated calls with the same inputs can return the stored result instead of recomputing it. This optimization technique is known as memoization and is commonly used to improve performance in recursive and repeated computations.
A common approach is to use a hash-based cache such as a Map or object. When the memoized function is called, the arguments are converted into a unique cache key (often by serializing the arguments). If the key already exists in the cache, the stored result is returned immediately. Otherwise, the original function is executed, and its result is stored in the cache for future calls.
This approach significantly reduces redundant work. Cache lookups are typically O(1) on average, while space grows with the number of unique argument combinations stored. Care must be taken when generating stable keys for argument lists.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map / Map-based Memoization | O(1) average lookup per call | O(n) for storing cached results |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You can create copy of a function by spreading function parameters. function outerFunction(passedFunction) { return newFunction(...params) { return passedFunction(...params); }; }
params is an array. Since you know all values in the array are numbers, you can turn it into a string with JSON.stringify().
In the outerFunction, you can declare a Map or Object. In the inner function you can avoid executing the passed function if the params have already been passed before.
In this approach, we can utilize a dictionary (or map) to cache the results of the function calls. The keys in this dictionary will be the string representation of the input arguments, and the values will be the corresponding function output. We will also maintain a count of how many unique calls have been made with new inputs.
The time complexity for each call is O(1) due to dictionary lookups. The space complexity is O(n) in the worst case, where n is the number of unique calls made, due to storage in the cache.
1class Memoize:
2 def __init__(self, func):
3 self.func = func
4 self.cache = {}
5 self.call_count = 0
6
7 def __call__(self, *args):
8 if args in self.cache:
9 return self.cache[args]
10 else:
11 result = self.func(*args)
12 self.cache[args] = result
13 self.call_count += 1
14 return result
15
16 def getCallCount(self):
17 return self.call_count
18
19
20def sum(a, b):
21 return a + b
22
23def fib(n):
24 if n <= 1:
25 return 1
26 return fib(n - 1) + fib(n - 2)
27
28def factorial(n):
29 if n <= 1:
30 return 1
31 return n * factorial(n - 1)The Memoize class is defined to wrap the target function. It maintains a cache dictionary and a call count integer. If the input arguments are already present in the cache, the cached result is returned. Otherwise, the function is called, the result is cached, and the call count is incremented.
Preserving the order and distinction of each argument set is crucial and can be achieved using tuples for arguments. With languages like Python, tuples can directly represent immutable and hashable keys for our cache. Similar adaptations exist for other languages, respecting each language's constraints around tuple-like structures and hashable types.
O(1) lookup time in the cache; Space complexity is O(n), dependent on the number of distinct calls stored.
1class Memoize:
2 def __init__(
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, memoization is a common concept tested in coding interviews, including FAANG companies. Interviewers often expect candidates to understand caching techniques and how they optimize recursive or repeated computations.
The optimal approach uses a hash-based cache such as a Map or object to store results of previous function calls. Each set of arguments is converted into a unique key so the function result can be retrieved instantly on repeated calls.
Memoization prevents repeated computation by storing results of expensive function calls. It improves performance in problems involving recursion, dynamic programming, or repeated function evaluations.
A Map is often the best choice because it supports efficient key lookups and flexible key handling. It allows storing cached results based on argument combinations with average O(1) access time.
This approach defines the key for cache lookups as a tuple of the input arguments, leveraging Python's native tuple hashability to allow efficient cache operations.