Memoize

Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

1
2
3
4
5
6

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 <= 10^5
• 1 <= n <= 10
• 1 <= actions.length <= 10^5
• actions.length === values.length
• actions[i] is one of “call” and “getCallCount”
• fnName is one of “sum”, “factorial” and “fib”

Solution

Method 1 – Closure with Argument Serialization

Intuition

To memoize a function, we need to cache results for each unique set of arguments. For JavaScript, we can use a Map to store results, using a stringified version of the arguments as the key. This ensures that each argument combination is cached separately, and repeated calls with the same arguments return the cached result.

Approach

1. Create a cache (Map) to store results.
2. For each call, serialize the arguments (e.g., using JSON.stringify).
3. If the cache contains the key, return the cached value.
4. Otherwise, call the original function, store the result in the cache, and return it.
5. Track the number of times the original function is called (for getCallCount).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function memoize(fn) {
    const cache = new Map();
    let callCount = 0;
    const memoized = (...args) => {
        const key = JSON.stringify(args);
        if (cache.has(key)) return cache.get(key);
        callCount++;
        const res = fn(...args);
        cache.set(key, res);
        return res;
    };
    memoized.getCallCount = () => callCount;
    return memoized;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function memoize<T extends (...args: any[]) => any>(fn: T): T & { getCallCount: () => number } {
    const cache = new Map<string, ReturnType<T>>();
    let callCount = 0;
    const memoized = (...args: Parameters<T>): ReturnType<T> => {
        const key = JSON.stringify(args);
        if (cache.has(key)) return cache.get(key)!;
        callCount++;
        const res = fn(...args);
        cache.set(key, res);
        return res;
    };
    (memoized as any).getCallCount = () => callCount;
    return memoized as T & { getCallCount: () => number };
}

Complexity

• ⏰ Time complexity: O(1) for cache lookup and insert (amortized).
• 🧺 Space complexity: O(n), where n is the number of unique argument sets cached.