Memoize

Problem Statement

Memoization is a powerful technique in programming, where functions avoid re-computing results for previously processed input by caching these results. The given task involves building a memoized version of a function, fn, which should not re-compute results for the same inputs but instead, retrieve them from a cache.

Three specific functions can be memoized:

• Sum Function: This function, sum(a, b), computes the sum of two integers. If sum has already been computed for a pair (a, b), retrieving it from a cache must consider (a, b) and (b, a) as different pairs unless a = b.

• Fibonacci Function: The fib(n) calculates the n-th Fibonacci number. For input values where n <= 1, it returns 1. For other values, it uses the recursive relation fib(n) = fib(n - 1) + fib(n - 2).

• Factorial Function: The factorial(n) computes the factorial of n, where factorial(n) = n * factorial(n - 1) for n > 1, and returns 1 if n <= 1.

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]

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. factorial was not called because 2 was seen before.
"getCallCount" - total call count: 2
memoFactorial(3); // "call" - returns 6. 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 <= 10⁵
• 1 <= n <= 10
• 1 <= actions.length <= 10⁵
• actions.length == values.length
• actions[i] is one of "call" or "getCallCount"
• fnName is one of "sum", "factorial", or "fib"

Approach and Intuition

The problem showcases interactions with memoized functions via a simulated environment where a series of actions and their respective values are provided. The core principle is:

• Cache results: Store function results for each unique set of arguments.
• Unique cache key: For functions with multiple arguments (e.g. sum(a, b)), use an argument string such as "a,b" to differentiate inputs properly.
• Track function calls: Maintain a counter that only increments when an actual computation happens (i.e. when the result is not fetched from the cache).

Function Behavior:

1. Sum Function:

   • (a, b) and (b, a) are treated as different unless a === b.
   • Function call counter increases only for first-time calls for a unique argument pair.

2. Factorial Function:

   • Caches results of factorial(n).
   • Recursive calls within factorial also benefit from memoization, reducing the number of computations.

3. Fib Function:

   • Fibonacci is the most computationally expensive of the three without memoization.
   • Memoization drastically reduces redundant computations by caching fib(n) results.

By applying these memoization principles consistently, the solution optimizes both time and resource usage across all three functions.

Solutions

var cacheFunction = (func, cacheStore = {}) => (...params) => cacheStore[params.join()] ?? (cacheStore[params.join()] = func(...params))