[Medium] LeetCode JS 30 - 2623. Memoize

Question Prompt

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.
• fib accepts a single integer n and returns 1 if orotherwise. n <= 1 fib(n - 1) + fib(n - 2)
• 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

Solutions

First, create a memoize function. It takes another function (fn) as input. Its goal is to create a memoized version of that input function. To memoize, we need to have a cache, a plain JavaScript object, which will act as our storage for remembered results.

The memoize function returns an inner function. This inner function is where the magic happens. It will take the arguments we’d normally pass to the original function.

In the inner function, we create a unique key by converting the arguments into a string. This is how we'll check our 'memory' to see if we've done this calculation before. We use if (key in cache) to do the checking. If it is in the cache already, we immediately return the stored result, skipping the potentially expensive calculation.

If it’s not in the cache , we will calculate and get the result by calling fn(...args). Before returning the result, we save it in the cache first by cache[key] = result. After that, we return the calculated result.

function memoize(fn) {
  const cache = {}; // Our 'memory' - a simple JavaScript object

  return function (...args) {
    // The inner function that does the magic
    const key = String(args); // Creates a unique key from the arguments

    if (key in cache) {
      // Have we seen this input before?
      return cache[key]; // Yes! Return the stored result
    }

    const result = fn(...args); // No? Call the original function
    cache[key] = result; // Store the result for next time
    return result; // Return the calculated result
  };
}