We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Memoize II

Difficulty: Hard

Problem Description

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. Inputs are considered identical if they are === to each other.

Key Insights

  • The memoization technique caches the results of expensive function calls and returns the cached result when the same inputs occur again.
  • Inputs can be of any type, and for objects, reference equality (===) is used to determine if the inputs are the same.
  • Care must be taken with mutable data types like arrays and objects to ensure they are correctly cached.

Space and Time Complexity

Time Complexity: O(n) where n is the number of unique input calls made to the function. Space Complexity: O(n) for storing the cached results of the function calls.

Solution

The solution involves creating a wrapper function around the original function that checks if the inputs have been seen before. If they have, it returns the cached result. If not, it calls the original function, stores the result in the cache, and then returns that result. A Map can be used to efficiently store and lookup cached results by input reference.

Code Solutions

function memoize(fn) {
    const cache = new Map();
    return function(...args) {
        const key = args.map(arg => (typeof arg === 'object' ? arg : JSON.stringify(arg))).join(',');
        if (cache.has(key)) {
            return cache.get(key);
        }
        const result = fn(...args);
        cache.set(key, result);
        return result;
    };
}
← Back to All Questions