Memoize | #2634 | LeetCode Solution

Problem: Memoize | #2634 | LeetCode

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 `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

"sum"

["call","call","getCallCount","call","getCallCount"]

[[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); // Returns 4. sum() was called as (2, 2) was not seen before.

memoizedSum(2, 2); // Returns 4. However sum() was not called because the same inputs were seen before.

// Total call count: 1

memoizedSum(1, 2); // Returns 3. sum() was called as (1, 2) was not seen before.

// Total call count: 2

Example 2:

Input

"factorial"

["call","call","call","getCallCount","call","getCallCount"]

[[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); // Returns 2.

memoFactorial(3); // Returns 6.

memoFactorial(2); // Returns 2. However factorial was not called because 2 was seen before.

// Total call count: 2

memoFactorial(3); // Returns 6. However factorial was not called because 3 was seen before.

// Total call count: 2

Example 3:

Input

"fib"

["call","getCallCount"]

[[5],[]]

Output

[8,1]

Explanation

fib(5) = 8

// Total call count: 1

Solution:

              /**

     * @param {Function} fn

     */

    function memoize(fn) {

        // Create a Map to store cached results

        const cache = new Map(); 

        return function (...args) {

            // Create a unique key based on the input arguments

            const key = args.join(","); 

            if (cache.has(key)) {

                // If the result is already cached, return it

                return cache.get(key);

            } else {

                // If not cached, compute the result using the original function

                const result = fn(...args);

                // Cache the result for future use

                cache.set(key, result);

                return result;

            }

        };

    }

Explanation:

To implement the `memoize` function as described, you can use a caching mechanism to store the results of previous function calls based on their input arguments. Here's the code with step-by-step explanations:

Let's break down the code step by step:

1. The `memoize` function is defined, taking a single parameter `fn`, which is the function to be memoized.

2. Inside the `memoize` function, a `cache` variable is created as a new `Map` object. This map will be used to store the results of function calls based on their input arguments.

3. The `memoize` function returns a new function created using a closure. This new function accepts any number of arguments using the rest operator `...args`.

4. Inside the returned function:

   - It creates a unique key based on the input arguments by converting the arguments array into a JSON string using `JSON.stringify(args)`. This key uniquely represents the specific combination of input arguments.

5. It checks if the `cache` already contains a result associated with the computed key using `cache.has(key)`.

   - If the result is already cached, it returns the cached result using `cache.get(key)`.

   - If not cached, it computes the result by invoking the original function `fn` with the provided arguments using `fn(...args)`.

6. After computing the result, it caches the result in the `cache` map using `cache.set(key, result)` so that it can be reused if the same input arguments are encountered again in the future.

7. Finally, it returns the computed result, whether it was fetched from the cache or freshly computed.

In summary, the `memoize` function creates a memoized version of a given function `fn`. It stores the results of previous function calls in a cache based on their input arguments, ensuring that the same inputs do not trigger redundant function calls, and returning the cached result instead.