JS - Map & Symbol object
Published: 2023-04-16 09:21:34

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