Categories
interview

Minimum Window Substring

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
  if (s.length < t.length) {
    return '';
  }

  const sMap = Array(256).fill(0);
  const tMap = Array(256).fill(0);
  for (const c of t) {
    tMap[c.charCodeAt(0)]++;
  }
  let count = 0;
  let start = 0;
  let minStart = -1;
  let min = s.length;
  for (let j = 0; j < s.length; j++) {
    const c = s[j].charCodeAt(0);
    sMap[c]++;
    if (sMap[c] <= tMap[c]) {
      count++;
    }

    if (count === t.length) {
      // Minimize the window by moving the start pointer.
      while (sMap[s[start].charCodeAt(0)] > tMap[s[start].charCodeAt(0)]) {
        sMap[s[start].charCodeAt(0)]--;
        start++;
      }
      const currLen = j - start + 1;
      if (currLen < min) {
        min = currLen;
        minStart = start;
      }
    }
  }
  if (minStart === -1 && count !== t.length) {
    return '';
  }
  return minStart !== -1 ? s.substring(minStart, minStart + min) : s;
};

console.log(minWindow('ABCDFEDFI', 'DF'));
// DF

Demo

Categories
interview

Maximum Subarray of size K

// Uses sliding window technique. Runtime Complexity 0(n).
const maxSubarraySizeK = (arr, k) => {
  if (arr.length < k) {
    return [];
  }
  let sum = 0;
  let s = 0;
  let maxSum = Number.MIN_VALUE;
  for (let i = 0; i < arr.length; i++) {
    if (i < k) {
      sum += arr[i];
      maxSum = sum;
    } else {
      sum += arr[i] - arr[i - k];
      if (sum > maxSum) {
        maxSum = sum;
        s = i - k + 1;
      }
    }
  }
  return arr.slice(s, s + k);
};

console.log(maxSubarraySizeK([1, 4, 2, 10, 2, 3, 1, 0, 20], 4));
// [3, 1, 0, 20]  - 24

Demo

Categories
interview

Largest Subarray Length K

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var largestSubarray = function(arr, k) {
  let max = arr[0];
  let maxIndex = 0;
  for (let i = 0; i <= arr.length - k; i++) {
    if (arr[i] > max) {
      max = arr[i];
      maxIndex = i;
    }
  }

  return arr.slice(maxIndex, maxIndex + k);
};

console.log(largestSubarray([1, 4, 5, 2, 3], 4));
// [4, 5, 2, 3]

Demo

Categories
interview

Heap

Max Heap (Javascript)

class MaxHeap {
  constructor(capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.arr = [];
  }

  add(val) {
    if (this.size < this.capacity) {
      this.arr[this.size++] = val;
      this.trickleUp(this.size - 1);
    }
  }

  trickleUp(i) {
    const parent = Math.floor((i - 1) / 2);
    if (parent >= 0 && this.arr[i] > this.arr[parent]) {
      this.swap(i, parent);
      this.trickleUp(parent);
    }
  }

  delete() {
    if (this.size) {
      const ret = this.arr[0];
      this.arr[0] = this.arr[this.size-- - 1];
      this.trickleDown(0);
      return ret;
    }
  }

  trickleDown(i) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;
    if (left < this.size && this.arr[left] > this.arr[largest]) {
      largest = left;
    }
    if (right < this.size && this.arr[right] > this.arr[largest]) {
      largest = right;
    }
    if (largest !== i) {
      this.swap(i, largest);
      this.trickleDown(largest);
    }
  }

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

  hasNext() {
    return this.size > 0;
  }
}

/** Test **/
const maxHeap = new MaxHeap(1000);
maxHeap.add(1);
maxHeap.add(90);
maxHeap.add(11);
maxHeap.add(5);
while (maxHeap.hasNext()) {
  console.log(maxHeap.delete());
}

/* 
 Output:
     		90
     		11
     		5
     		1
*/

// Time complexity for each operation: O(log(n)).

Demo

Categories
interview

Design Add and Search Words Data Structure

The following code uses “Trie” data structure. The character ‘.’ in a word could represent any letter when searching.

class TrieNode {
  constructor(val) {
    this.val = val;
    this.children = {};
    this.isWord = false;
  }
}

var WordDictionary = function() {
  this.root = new TrieNode(null);
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
  let current = this.root;
  const charArray = word.split('');
  for (const s of charArray) {
    if (!(s in current.children)) {
      current.children[s] = new TrieNode(s);
    }
    current = current.children[s];
  }
  current.isWord = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
  return this.searchString(word, this.root);
};

WordDictionary.prototype.searchString = function(str, node) {
  let current = node;
  const charArray = str.split('');
  for (const [index, char] of Object.entries(charArray)) {
    if (!(char in current.children)) {
      if (char === '.') {
        for (const [key, childNode] of Object.entries(current.children)) {
          if (this.searchString(str.substring(parseInt(index) + 1), childNode)) {
            return true;
          }
        }
      }
      return false;
    } else {
      current = current.children[char];
    }
  }
  return current.isWord;
};

var obj = new WordDictionary();
obj.addWord('bad');
obj.addWord('bat');
obj.addWord('cat');
console.log(obj.search('b..')); // true
console.log(obj.search('cat')); // true
console.log(obj.search('dog')); // false

Demo

Categories
interview

Coin Change

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = (coins, amount) => {
  if (!coins) {
    return -1;
  }
  return getCoinChangeMin(coins, amount, {});
};

const getCoinChangeMin = (coins, amount, dp) => {
  if (amount < 0) {
    return -1;
  }
  if (amount === 0) {
    return 0;
  }
  if (amount in dp) {
    return dp[amount];
  }
  let min = Number.MAX_VALUE;
  for (const coin of coins) {
    let currMin = getCoinChangeMin(coins, amount - coin, dp);
    if (currMin >= 0 && currMin < min) {
      min = currMin;
    }
  }
  return dp[amount] = min === Number.MAX_VALUE ? -1 : min + 1;
};
Categories
interview

N-Queens Js

const solveNQueens = (n) => {
  if (n < 1) {
    return [];
  }
  const ret = [];
  getAll(n, 0, ret, []);
  return ret;
};


const getAll = (n, row, ret, rowCol) => {
  if (row === n) {
    ret.push(buildSolution(rowCol, n));
    return;
  }

  for (let col = 0; col < n; col++) {
    if (isValid(row, col, rowCol)) {
      rowCol[row] = col;
      getAll(n, row + 1, ret, rowCol);
    }
  }
};

const isValid = (row, col, rowCol) => {
  for (let r = 0; r < row; r++) {
    if (rowCol[r] === col) {
      return false;
    }

    const c = rowCol[r];

    if ((row - r) === Math.abs(c - col)) {
      return false;
    }
  }
  return true;
};

const buildSolution = (rowCol, n) => {
  const ans = [];
  for (let i = 0; i < n; i++) {
    let str = '';
    for (let j = 0; j < n; j++) {
      str += rowCol[i] === j ? 'Q' : '.';
    }
    ans.push(str);
  }
  return ans;
};
Categories
interview

Implementing a Trie in Javascript

class TrieNode {
  constructor(val) {
    this.val = val;
    this.children = {};
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(str) {
    let current = this.root;
    for (const char of str) {
      if (!(char in current.children)) {
        current.children[char] = new TrieNode(char);
      }
      current = current.children[char];
    }
    current.isWord = true;
  }

  search(str) {
    let current = this.root;
    for (const char of str) {
      if (!(char in current.children)) {
        return false;
      }
      current = current.children[char];
    }
    return current.isWord;
  }
}

const trie = new Trie();
trie.insert('john');
trie.insert('smith');
console.log(trie.search('john')); // true
console.log(trie.search('smith')); // true
console.log(trie.search('johny')); // false
console.log(trie.search('Tesla')); // false
console.log(trie.search('John')); // false

Demo

Categories
interview

Letter Combinations of a Phone Number

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if  (!digits) {
    return [];
  }
const result = [];
const map = {2: 'abc',
3: 'def',
4:'ghi',
5:'jkl',
6:'mno',
7:'pqrs',
8: 'tuv',
9:'wxyz',};
  computeCombinations(map, digits, 0, result, '');
  return result;
};

const computeCombinations = (map, digits, index, result, str) => {
  if (index === digits.length) {
    result.push(str);
  } else {
    for (const letter of map[digits[index]].split('')) {
       computeCombinations(map, digits, index + 1, result, str + letter);
    }
  }
};
Categories
interview

Top K Frequent Words

/**
* @param {string[]} words
* @param {number} k
* @return {string[]}
*/
const topKFrequent = (words, k) => {
  const wordFreq = {};
  for (const word of words) {
    if (word in wordFreq) {
      wordFreq[word]++;
    } else {
      wordFreq[word] = 0;
    }
  }

  return [...new Set(words)].sort((a, b) => {
    if (wordFreq[a] === wordFreq[b]) {
      return a.localeCompare(b);
    } else {
      return wordFreq[b] - wordFreq[a];
    }
  }).slice(0, k);
};