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

Abstraction (ADT)	Implementation (DS)
List	Dynamic Array, Linked List
Queue	Linked List based Queue, Array based Queue, Stack based Queue
Map	Tree Map, Hash Map / Hash Table (here is our map!✨)

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