Use a Map to Help You Navigate thru the Maze of an Interview

One of the most important tools you should have in your toolbox when you are trying to solve an algorithm problem during a javascript interview is using a “map”. I will explain what I mean by that in a moment.

The map is not the actual map but rather a Map-like type, in fact the Ojbect. After all, in javascript, both Object and Map are practically equivalent.

The logic behind this is that:

1. Compared with that of an Array, Object’s key has much more information.
2. Object keys are unique to each other, making them perfect to tracking things.
3. When you need something to track historic information, use Object.

To better understand this, let’s walk through a real problem.

If you are given a string that reads "Let me walk you through a real problem to better understand this" you must find the alphabit character that appears most frequently.
Solution: The idea is to create a map that entails the frequency information of the string, in the form of:
{
"L":1,
"h":4,
...
}

First let’s create that map/histogram, like this:

const strOld="Hello World";
const strNew=strOld.replaceAll(' ','');
function createMap(strNew){
 const map={};
 for(let i=0; i<strNew.length; i++){
  let tmp=strNew[i];
  if(map[tmp] && map[tmp]>0){
    map[tmp]++;  
  }else{
     map[tmp]=1;
  }  
 }
 return map;  
}
console.log(createMap(strNew))
/* {
  d: 1,
  e: 1,
  H: 1,
  l: 3,
  o: 2,
  r: 1,
  W: 1
} */

Then let’s find the max value in the map object above:

const hGram=createMap(strNew);
const keys   = Object.keys(hGram);
const values = Object.values(hGram);
const sortedValues = [...Object.values(hGram)];
      sortedValues.sort((a, b)=> b-a);
      
const maxValue=sortedValues[0];
const result=keys[values.indexOf(maxValue)];
console.log(result);
//l

Note: You must be very careful about using the sort/reverse function, because it will mutate the original array!!

Because of this, let’s look at a safer way:

let result2;
let max=-1;
for (let k in hGram){
    let v=hGram[k];
    if(v>max){
     max=v;
     result2=k;
    }
}
console.log(result2, max);
//"l", 3

Let’s try another problem:

const nums=[2, 7, 11, 15];
const target=9;
const result=[];
for (let v of nums){
    let i=nums.indexOf(v);
    let desired= target-v;
    
    if( nums.indexOf(desired) !== -1 ){
        
          result.push(i);
          result.push(nums.indexOf(desired));
          
          break;
          //use break to stop the loop
    }
}
console.log(result);
//[0,1]

Solution 1: use target — each element =desired and then search desired in the array

Another solution:

Use the map to keep track of array’s element and its index history, like this

{ 2:0,7:1}

const result2=[];
const map={};
for (let i=0; i<nums.length; i++){
   let v=nums[i];
   let desired=target-v;
  
   if(map[desired] !==undefined){
       //note. here must be undefined, because it can be 0/zero!!
        result2.push(map[desired]);
        result2.push(i);
      break;
   }else{
     map[v]=i;
  }
}
console.log(result2);
//[0,1]