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