Memoize II

Problem Statement

In this problem, you are given a function fn and are required to transform it into a memoized version of itself. A function is termed memoized when it stores the result of its computations; if it is again called with the same inputs, instead of recalculating, it retrieves the result from its cache. This ensures that the function computation for previously seen inputs is almost instantaneous, leading to increased efficiency especially with recursive calls or operations with significant computational overhead.

The function fn can be any function - the memoization should work regardless of its complexity or the types of parameters it accepts. You must ensure that inputs to this function are considered identical strictly (===), which implies that this comparison needs to be both type and value correct for basic types, and referentially correct for objects and arrays.

Examples

Example 1

Input:

getInputs = () => [[2,2],[2,2],[1,2]]
fn = function (a, b) { return a + b; }

Output:

[{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}]

Explanation:

const inputs = getInputs();
const memoized = memoize(fn);
for (const arr of inputs) {
memoized(...arr);
}
For the inputs of (2, 2): 2 + 2 = 4, and it required a call to fn().
For the inputs of (2, 2): 2 + 2 = 4, but those inputs were seen before so no call to fn() was required.
For the inputs of (1, 2): 1 + 2 = 3, and it required another call to fn() for a total of 2.

Example 2

Input:

getInputs = () => [[{},{}],[{},{}],[{},{}]]
fn = function (a, b) { return ({...a, ...b}); }

Output:

[{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]

Explanation:

Merging two empty objects will always result in an empty object. It may seem like there should only be 1 call to fn() because of cache-hits, however none of those objects are === to each other.

Example 3

Input:

getInputs = () => { const o = {}; return [[o,o],[o,o],[o,o]]; }
fn = function (a, b) { return ({...a, ...b}); }

Output:

[{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]

Explanation:

Merging two empty objects will always result in an empty object. The 2nd and 3rd third function calls result in a cache-hit. This is because every object passed in is identical.

Constraints

• 1 <= inputs.length <= 105
• 0 <= inputs.flat().length <= 105
• inputs[i][j] != NaN

Approach and Intuition

In order to develop a memoized version of the function fn, we can take the following logical steps.

1. Define a new function, called memoizedFn that encapsulates the memoization logic.
2. Create a cache (using an object or a new Map) within memoizedFn where results of previous computations are stored.
3. When memoizedFn is called:
   • Create a unique identifier for the input arguments. In JavaScript, for primitive values and object references, this can typically be achieved through serialization, or by directly using the values as keys if they are primitively unique (e.g., strings, numbers).
   • Check the cache for this identifier.
     • If the value exists, retrieve it from the cache and return this value without calling fn.
     • If the value does not exist, call fn with the current inputs, store the result in the cache using the identifier, and then return the result.
4. Be mindful of how inputs are checked for 'sameness'. JavaScript's strict equality (===) will be leveraged, ensuring that object references must point to the exact same object, not merely structurally similar ones.

Applying the Steps in the Examples

• Example 1:

  • First Call with (2,2): Computed as 4 and stored in cache.
  • Second Call with (2,2): Retrieved from cache, no recomputation.
  • Third Call with (1,2): Computed as 3, since it doesn't exist in the cache, and stored.

• Example 2:

  • Calls with different {} objects: Each is unique (different references), leading to repeated computation even though they result in the same structure ({}).

• Example 3:

  • Repeated Calls with the same {} object reference: All fetch the result from the cache post the first computation, since the reference is unchanged across calls.

This demonstrates how determining input sameness effectively, especially for objects, is crucial in memoization, and also shows how memoization can save computational costs by preventing repeated calculations.

Solutions

class SearchTree {
  keyMap = new Map();
    
  hasEntry = false;
    
  storedValue = null;
    
  retrieveValue(path, idx) {
    const currentKey = path[idx];
    if (idx >= path.length) {
      if (this.hasEntry) {
        return { value: this.storedValue, success: true };
      } else {
        return { value: undefined, success: false };
      }
    } else {
      if (this.keyMap.has(currentKey)) {
        return this.keyMap.get(currentKey).retrieveValue(path, idx + 1);
      } else {
        return { value: undefined, success: false };
      }
    }
  }
    
  findValue(path) {
    return this.retrieveValue(path, 0);
  }
    
  insertValue(path, idx, value) {
    const currentKey = path[idx];
    if (idx >= path.length) {
      this.storedValue = value;
      this.hasEntry = true;
    } else {
      if (!this.keyMap.has(currentKey)) {
        this.keyMap.set(currentKey, new SearchTree());
      }
      return this.keyMap.get(currentKey).insertValue(path, idx + 1, value);
    }
  }
    
  assignValue(path, value) {
    return this.insertValue(path, 0, value);
  }
}
    
function cacheFunction(originalFunc) {
  const cacheTree = new SearchTree();
  const cachedFunc = (...args) => {
    const lookup = cacheTree.findValue(args);
    if (lookup.success) {
      return lookup.value;
    }
    const outcome = originalFunc(...args);
    cacheTree.assignValue(args, outcome);
    return outcome;
  };
  return cachedFunc;
}