DEV Community: jiiin✨

JS - Map

jiiin✨ — Sun, 16 Apr 2023 11:23:05 +0000

Related leetCode question:
https://leetcode.com/problems/two-sum/description/

Here is my original answer, which uses double for-loop. It is no ideal in terms of iteration time, because there is no breaks and it iterates two loops 😧

var twoSum = function(nums, target) {
    let result = [];
    for(let i = 0; i < nums.length -1; i++ ) {
        const val1 = nums[i];
        const nextIndice = i + 1;
        const newArr = nums.slice(nextIndice);

        for(let j =0 ; j < newArr.length; j++) {
            const sum = val1 + newArr[j];
            if(sum === target) {
                result = [i, nextIndice + j];

            }
        } 
    }   
    return result;

We can make it more performative algorithm using Map object!

The return value we are interested in is getting array of 'index' that satisfies condition. Thus, first step is to create table having index as value (invert). So we can get the index using get method from Map class instance.

const map = new Map();
map.set(nums[i], i)  // index is value in Map object

The value we are interested in is that the sum of two values are equal to 'target', and we will iterate through nums array.

// target = nums[i] + val 
// same as val = target - nums[i]

if(map.has(target - nums[i])) {
   return [map.get(target - nums[i]), i] // this is what we are looking for! 🌟
} else {
   map.set(nums[i], i)  // update table
}

Again, here we use Map object to avoid double for-loops!

JS basics - 1

jiiin✨ — Sun, 16 Apr 2023 10:38:58 +0000

This questions if from: 70 JavaScript Interview Questions

Compre undefined vs. null (my initial answer) Undefined and Null both are primitive value in Javascript, but I normally use Undefined when a variable is supposed to have a value in future but not sure which value it will be. Meanwhile I use null to identify the variable should not contain any reference.

(correct answer)
JavaScript's 7 primitive types.
string, number, null, undefined, boolean, symbol, bigint, ~~object~~

Both are falsy values by converting Boolean(value) object or double Not operator (!!value).

undefined:

Default value of a variable that has not been assigned a specific value yet
A function that has no explicit return value
Property that does not exist in an object

null:

A value that explicitly represents no value

null == undefined // abstract equality, compares value only, true
null === undefined // strict equality, compares value and type, false

What does the && operator do? Logical And operator compares conditions and returns true if all conditions are true.

const trueResult = true && true // true
const falsyResult = true && false // false

Logical operator returns true if first operand is true,
or returns right operand value if left is false

Logical And operator evaluates from left to right operands, and returns first falsy value*. If none is false, returns last expression.

const value = " " && true && 'apple' // 'apple'
const apple = false && 'apple' && 'orange' // false

Falsy value:

undefined
null
NaN
empty string
false
0

What does Logical Or operator do? Logical Or operator evaluates if any conditions are true, then return true. If one of any conditions are false, returns false

For example

x || y

If x can be converted true, return x. Else, return y.

[some truthy expression] || expr

JS - Map & Symbol object

jiiin✨ — Sun, 16 Apr 2023 09:21:34 +0000

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

a unique key to mark the value as result,
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 💪💪💪