Category: interview

Categories
interview

Serialize / Deserialize

You can do in this in many ways, the following code does this using prefix traversal.

/**
 * @param {Node} root
 * @return {string}
 */
function serialize(root) {
  if(!root) return '_';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

/**
 * @param {string} str
 * @return {Node}
 */
function deserialize(str) {
  const q = str.split(',');
  return dfs(q);

 /**
 * @param {string} str
 * @return {Node}
 */
  function dfs(que) {
    if(!que.length) return null;
    const n = que.shift()
;
    if(n !== '_') {
      const node = new Node(n.value)
      node.left = dfs(q);
      node.right = dfs(q);
      return node;
    }
    return null;
  }
}
Categories
interview

DOM Elements as Keys in Object

To store DOM Elements as keys in object without using WeakMap( ), we can do the following:

<div id="root"></div>
<script>
  class NodeStore {
    static key = 'key';

    set(node, value) {
      node.dataset[NodeStore.key] = value;
    }

    get(node) {
      return this.has(node) && node.dataset[NodeStore.key];
    }

    has(node) {
      return NodeStore.key in (node?.dataset || {});
    }
  }

  const nodeStore = new NodeStore();
  const root = document.getElementById('root');
  nodeStore.set(root, 'root value');
  console.log(nodeStore.has(root)); // true
  console.log(nodeStore.get(root)); // 'root value'
</script>

Demo

However the above solution can only support values of type string. To support any type of value we can use the following solution:

<div id="root"></div>
<script>
class NodeStore {
  static key = 'key';
  constructor() {
    this.map = {};
    this.counter = 0;
  }
   /**
   * @param {Node} node
   * @param {any} value
   */
  set(node, value) {
    node[NodeStore.key] = this.counter;
    this.map[this.counter++] = value;
  }
  /**
   * @param {Node} node
   * @return {any}
   */
  get(node) {
     if (this.has(node)) {
       return this.map[node[NodeStore.key]];
     }
     return;
   }
  
  /**
   * @param {Node} node
   * @return {Boolean}
   */
  has(node) {
    return NodeStore.key in node;
  }
}
const nodeStore = new NodeStore();
const root = document.getElementById('root');
nodeStore.set(root, 22);
console.log(nodeStore.has(root)); // true
console.log(nodeStore.get(root)); // 22
</script>

Demo

Categories
interview

Generator Functions in JavaScript:

Introduction

ES6 introduced new type of functions called Generator Functions. A function keyword with an asterisk * is used to define a generator function.

function* generatorFunction(i) {
  yield i;
  yield i + 10;
}
const generator = generatorFunction(1);
console.log(generator.next().value); //1
console.log(generator.next().value); //11

Demo

A Generator Function can be called as many times as desired. Every time the function is called it returns a special type of iterator object called Generator. Generators are unique, calling the function by next() method returns a new Generator. The next() method returns an object with a Value property containing the yield value and a done property which is a Boolean indicating whether the generator has yielded its last value.

//Normal functions 

function normalFunction() {
  console.log("cannot");
  console.log("be");
  console.log("stopped");
}

normalFunction()// cannot be stopped

//Generator function

function* generatorFunction() {
  yield console.log("can");
  yield console.log("be");
  yield console.log("stopped");
}

const generator = generatorFunction();
generator.next().value; // can
generator.next().value; // be
generator.next().value; // stopped

Demo

Memory Efficient

Generator Functions are memory efficient, they can be stopped midway or suspend function execution to yield values on demand and continue from where it was stopped by calling next().

They are efficient when iterating over a large data set(or an infinite list). Most of the time we may not want to iterate through the full list and want to generate only what is needed at that time.

function* generatorFunction(max) {
    let number = 0;

    //iterate over an infinite count to generate squared numbers

    while (number < max) {
      number++;
      yield number * number;
    }
  }

  const max = Infinity;

  let iterationCount = 0;
  
  const totalIterations = 5;

  const squaredNumber = generatorFunction(max);

  //generate first 5 squared numbers
  
  while (iterationCount < totalIterations) {
    iterationCount++;
    console.log(squaredNumber.next().value);
  }

Demo

Using Return in the Generator Function

When the return statement gets executed then the done property will be set to true. Any subsequent next() method will not be executed. Note that any error that is not caught in the function execution will finish the function as well and returns.

function* generatorWithReturn(i) {
  yield i; //returns i
  return i; //returns i
  yield i; //returns undefined
}

var gen = generatorWithReturn("conitnue")
console.log(gen.next()); // { value: "continue", done: false }
console.log(gen.next()); // { value: continue, done: true }
console.log(gen.next()); // { value: undefined, done: true }

Demo

Categories
interview

Alien Dictionary

Given a list of words (Strings), generate the order of the language. If the given input is invalid you can return an empty string (”). Sometimes, multiple orders are possible. The following approach uses Topological Sort and DFS (Depth First Search).

const buildAdjacencyList = (wordList, adjacencyList) => {
   for (const word of wordList) {
     for (let i = 0; i < word.length; i++) {
       if (!adjacencyList.has(word.charAt(i))) {
         adjacencyList.set(word.charAt(i), []);
       }
     }
   }

 for (let i = 0; i < wordList.length - 1; i++) {              
     const firstWord = wordList[i];
     const secondWord = wordList[i + 1];
     if (firstWord.startsWith(secondWord) && firstWord.length > secondWord.length) {
       return false;
      }
     const minLen = Math.min(firstWord.length, secondWord.length);
     for (let j = 0; j < minLen; j++) {
       const firstWordChar = firstWord.charAt(j);
       const secondWordChar = secondWord.charAt(j);
       if (firstWordChar !== secondWordChar) {
         // Store in reverse to get the correct order in the end.
         adjacencyList.get(secondWordChar).push(firstWordChar);
         break;
       }
     }
   }
   return true;
 };

 const topologicalSort = (currChar, adjacencyList, visited, resultStack) => {
   if (!(currChar in visited)) {
     visited[currChar] = false;
     if (adjacencyList.has(currChar)) {
       for (const char of adjacencyList.get(currChar)) {
         const result = topologicalSort(char, adjacencyList, visited, resultStack);
         if (!result) return false;
       }
     }
     visited[currChar] = true;
     resultStack.push(currChar);
     return true;
   } else {
            return visited[currChar];
           }
 };

 var alienOrder = function(words) {
   const adjacencyList = new Map();
   const valid = buildAdjacencyList(words, adjacencyList);
   if (!valid) {
     return '';
   }
   const resultStack = [];
   const visited = {};
   for (const [key, value] of adjacencyList) {
     const result = topologicalSort(key, adjacencyList, visited, resultStack);
     if (!result) {
       return '';
     }
   };
   if (resultStack.length !== adjacencyList.size) {
     return '';
   }
   return resultStack.join('');
 };

 console.log(alienOrder(['dog', 'dot', 'dotted']));
 // "dogte"

Demo

Categories
interview

Maximum height by stacking Cuboids

Box stacking problem max height of stack possible (can be rotated). All the dimensions of the box beneath should be greater than the one stacked above it.

box-stacking

Javascript

const maxHeight = (cuboids) => {
  // Sort each cuboid dimensions.
  for (const cuboid of cuboids) {
    cuboid.sort((a, b) => a - b);
  }
  
  // Sort the cuboids from largest to smallest order.
  cuboids.sort((a, b) => {
    if (a[0] != b[0]) {
      return b[0] - a[0];
    }
    if (a[1] != b[1]) {
      return b[1] - a[1];
    }
    return b[2] - a[2];
  });
  
  // dp[i] means max height upto cuboid 'i' (row i).
  const dp = Array(cuboids.length);
  
  for (let i = 0; i < cuboids.length; i++) {
    // We choose the largest side of cuboid to be height to maximize it.
    dp[i] = cuboids[i][2];
    for (let j = 0; j < i; j++) {
      if (cuboids[j][0] >= cuboids[i][0] && cuboids[j][1] >= cuboids[i][1] && cuboids[j][2] >= cuboids[i][2]) {
        dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
      }
    }
  }
  
  return Math.max(...dp);
}

console.log(maxHeight([
  [1, 1, 1 ],
  [2, 3, 10],
  [2, 4, 1 ],
]));
// 15

Demo

Categories
interview

Quicksort

Worst Case Time Complexity: O(n^2)

const quickSort = (arr, low, high) => {
  if (low >= 0 && high >= 0 && low < high) {
    const partition = getPartition(arr, low, high);
    quickSort(arr, low, partition);
    quickSort(arr, partition + 1, high);
  }
};

const getPartition = (arr, low, high) => {
  const pivot = arr[low + Math.floor((high - low) / 2)];
  low--;
  high++;
  while (true) {
    do {
      low++;
    } while (arr[low] < pivot)
    do {
      high--;
    } while (arr[high] > pivot)
    if (low >= high) {
      return high;
    }
    swap(arr, low, high);
  }
};

const swap = (arr, a, b) => {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

const arr = [4, 3, -1, 4, 1, 0];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]

Demo

Categories
interview

Merge Sort

Runtime Complexity: O(n*log(n))

const mergeSort = (arr, low, high) => {
  if (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    merge(arr, low, mid, high);
  }
};

const merge = (arr, low, mid, high) => {
  const tempArr = [];
  let i = low;
  let j = mid + 1;
  let k = 0;
  while (i <= mid && j <= high) {
    tempArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
  }
  while (i <= mid) {
    tempArr[k++] = arr[i++];
  }
  while (j <= high) {
    tempArr[k++] = arr[j++];
  }
  for (const val of tempArr) {
    arr[low++] = val;
  }
};

const arr = [4, -1, 1, 0, 3, 4];
mergeSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]

Demo

Categories
interview

Coin Change II

The following solution uses “Bottom up dynamic programming” approach.

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
const change = (amount, coins) => {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }
  return dp[amount];
};

// Analysis   n - length of coins
//            m - amount
// Time Complexity O(n*m)
// Space Complexity O(m)

Demo

Categories
interview

Reorganize String (Js)

/**
 * @param {string} S
 * @return {string}
 */
const reorganizeString = (S) => {
  let counts = [];
  for (let i = 0; i < 26; i++) {
    counts[i] = 0;
  }
  for (let i = 0; i < S.length; i++) {
    counts[S.charAt(i).charCodeAt(0) - 'a'.charCodeAt(0)] += 100;
  }
  for (let i = 0; i < 26; i++) {
    counts[i] += i;
  }
  //Encoded counts[i] = 100*(actual count) + (i)
  counts.sort((a, b) => a - b);
  let t = 1;
  let ret = [];
  for (let i = 0; i < 26; i++) {
    const ch = String.fromCharCode('a'.charCodeAt(0) + (counts[i] % 100));
    let count = Math.floor(counts[i] / 100);
    if (count > Math.floor((S.length + 1) / 2))
      return '';
    while (count > 0) {
      if (t >= S.length)
        t = 0;
      ret[t] = ch;
      t += 2;
      count--;
    }
  }
  return ret.join('');
};

console.log(reorganizeString('aab'));
// 'aba'

Demo

Categories
interview

Decode String (Js)

Given an encoded string 3[abc]2[bc] the decoded output should be of the form “abcabcabcbcbc”. Assume that all the brackets are well formed and that all strings are encoded correctly.

/**
 * @param {string} s
 * @return {string}
 */
const decodeString = (str) => {
  const stack = [];
  for (const ch of str.split('')) {
    if (ch === ']') {
      let currStr = '';
      while (stack[stack.length - 1] !== '[') {
        currStr = stack.pop() + currStr;
      }
      stack.pop();
      let k = 0;
      let base = 1;
      while (stack.length && parseInt(stack[stack.length - 1]) >= 0) {
        k += parseInt(stack.pop()) * base;
        base *= 10;
      }
      if (k !== 0) {
        stack.push(currStr.repeat(k));
      }
    } else {
      stack.push(ch);
    } 
  }
  return stack.join('');
};

Demo