JS – Map & Symbol object

Here is my initial (failed) LeetCode answer for 2630. Memoize II 🙈🙈🙈

function memoize(fn) {
    let previousParameters = [];
    let cachedResult;

    return function(...params) {
       // if params and previousParameters array are deep equal, use cached result
       const isEqual = isDeepEqual(params, previousParameters);

        if(isEqual) {
            return cachedResult;
        }

       // else update previousParameters, call fn(...params), assign result 
       previousParameters = params.slice();
       cachedResult = fn(...params);
       return cachedResult;     
    }
}

const isDeepEqual = (object1, object2) => {

  const objKeys1 = Object.keys(object1);
  const objKeys2 = Object.keys(object2);

  if (objKeys1.length !== objKeys2.length) return false;

  for (var key of objKeys1) {
    const value1 = object1[key];
    const value2 = object2[key];

    const isObjects = isObject(value1) && isObject(value2);

    if ((isObjects && !isDeepEqual(value1, value2)) ||
      (!isObjects && value1 !== value2)
    ) {
      return false;
    }
  }
  return true;
};

const isObject = (object) => {
  return object != null && typeof object === "object";
};

isDeepEqual was a method that I normally use in my practice. But this solution fails to differentiate unique parameters. Because previousParameters is a shallow copy of given param, it creates new reference ([o, o] will always differ from next [o, o])

After couple of failures, I (had to) glanced a few solutions 😏 and got a hint that Map object was right way to go! Unfortunately I have no idea what javascript Map object (or Hash Map data structure) is.

To begin with, what is data structure?

Data structure (DS) is a way of organising data so that it can be accessed, queried, updated quickly and easily
There is a related concept called Abstract Data Types (ADT).

Abstract Data Types vs. Data Structure

• Abstract Data Type (ADT) provides the interface
• Interface does not give any specific details or in what programming language
• How Data Structure behave & what method this data structure have is ADT

Here I made the second mistake that I simply assigned param as key value.

let localCache = new Map();

if(!localCache.has(params)) {
  localCache.set(params, fn(...params))
}

return localCache.get(params) 

This solution failed because params in localCache.has(params) method does not compare individual values in params array 😅

For example, const foo = [2, 2] and const bar =[2, 2], foo and bar has different reference therefor it is always unique.

Which implies that Map object is a perfect data structure
when ** a value paired to a single key! **

In other words, to use Map object correctly, I need to create nested Map object from { [2, 2]: 4 } to { 2: { 2: 4 }}

But this approach has one challenge that get method will return a branch instead of result. For example:

fn(1, 2) // { 1: {2: 3 }} 
cache.get(1) // will return {2: 3} which is branch not the result 3

To solve it, we need

1. a unique key to mark the value as result,
2. a local variable that stores the last child map object in nested map so we can extract the result value by get method 🌟

Here is final solution:

const RES = Symbol('result') // 1. a unique key 
return function(...params) {
   let localCache = new Map(); // 2. a local variable 
   for(let param of params) {
     if(!localCache.has(param)) {
        localCache.set(param, new Map())
      }
     localCache = localCache.get(param) 
   }

if(!localCache.has(RES)) {
   // assign function result in last child 
   localCache.set(RES, fn(...params))
}

return localCache.get(RES)

}

This question was really great to understand the usage of Map object! Faster querying 💪💪💪