Author: Shiva Charan Devabhaktuni

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
Uncategorized

Mutation Observer

If you want to listen to DOM Mutations then you can use the Mutation Observer.

const observer = new MutationObserver((mutations) => {
  mutations.forEach(function(mutation) {
    for (let i = 0; i < mutation.addedNodes.length; i++) { // i.e., nodeList
      console.log(mutation.addedNodes[i]);
      // You can perform your actions here.
    }
  });
});
observer.observe(document.body, {
  childList: true,
  subtree: true,
  attributes: false,
  characterData: false,
});
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

Categories
interview

Meeting Rooms II

Given a list of meetings, that may or may not overlap, calculate the total number of rooms that are required to conduct all the meetings according to the schedule.

Java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int endPtr = 0, rooms = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (start[i] < end[endPtr]) {
                rooms++;
            } else {
                endPtr++;
            }
        }
        return rooms;
    }
}

Runtime Complexity: O(nlog(n))

Space Complexity: O(n)

Javascript (ES6)

/**
 * @param {number[][]} intervals
 * @return {number}
 */
const minMeetingRooms = (intervals) => {
  let startList = [];
  let endList = [];
  let endPos = 0;
  let rooms = 0;
  for (const [start, end] of intervals) {
    startList.push(start);
    endList.push(end);
  }
  startList.sort((a, b) => a - b);
  endList.sort((a, b) => a - b);
  for (let i = 0; i < intervals.length; i++) {
    if (startList[i] < endList[endPos]) {
      rooms++;
    } else {
      endPos++;
    }
  }
  return rooms;
};

// console.log(minMeetingRooms([[7, 10],[2, 4]]));
// 1

Demo

Categories
interview

Word Break

Given a non-empty string “word” can it be broken into a list of non-empty words contained in a dictionary ? The words can be repeated.

Java

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

JavaScript (ES6)

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
const wordBreak = (s, wordDict) => canWordBreak(s, 0, wordDict);

const dp = {};

const canWordBreak = (word, index, wordDict) => {
  if (index === word.length) {
    return dp[index] = true;
  }
  if (dp[index] !== undefined) {
    return dp[index];
  }
  for (let breakIndex = index + 1; breakIndex <= word.length; breakIndex++) {
    if (wordDict.indexOf(word.substring(index, breakIndex)) > -1 && canWordBreak(word, breakIndex, wordDict)) {
      return dp[index] = true;
    }
  }
  return dp[index] = false;
}

// console.log(wordBreak("catsandog",
// ["cats","dog","sand","and","cat"]));
// false

Demo