Categories
interview

KMP (Knuth–Morris–Pratt) Algorithm

// Knuth–Morris–Pratt algorithm.
const patternMatch = function(pattern, str) {
  let i = 0;
  let j = 0;
  let n = str.length;
  let m = pattern.length;
  const lps = [];

  // Compute longest prefix string.
  computeLPS(pattern, m, lps);

  while (i < n) {
    if (str.charAt(i) === pattern.charAt(j)) {
      i++;
      j++;
    }
    if (j === m) {
      console.log('String found at: ' + (i - j));
      j = lps[j - 1];
    } else if (i < n && str.charAt(i) !== pattern.charAt(j)) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
};

const computeLPS = function(pattern, m, lps) {
  let i = 1;
  let len = 0;
  while (i < m) {
    if (pattern.charAt(i) === pattern.charAt(len)) {
      lps[i++] = ++len;
    } else {
      if (len > 0) {
        len = lps[len - 1];
      } else {
        lps[i++] = 0;
      }
    }
  }
};

patternMatch('john', 'helloworldjohnhelloworldjohnn');
/*
"String found at: 10"
"String found at: 24"
*/

Demo

Categories
interview

Longest Common Prefix

Find the longest common prefix for a list of strings.

const longestCommonPrefix = (arr) => {
  if (!arr || !arr.length) {
    return;
  }

  let low = 0;
  let high = arr[0].length - 1;

  for (const str of arr) {
    high = Math.min(str.length - 1, high);
  }

  let str = '';

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (hasPrefix(arr, low, mid)) {
      str += arr[0].substring(low, mid + 1);
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return str;
};

const hasPrefix = (arr, low, mid) => {
  const prefix = arr[0].substring(low, mid + 1);

  for (const str of arr) {
    if (!str.substring(low, mid + 1).startsWith(prefix)) {
      return false;
    }
  }

  return true;
};

console.log(longestCommonPrefix(['johnSmith', 'johnWick', 'john1'])); // 'john'
console.log(longestCommonPrefix(['jo1hnSmith', 'johnWick', 'john1'])); // 'jo'
console.log(longestCommonPrefix(['Smith', 'Wick', 'red'])); // ''

Demo

Runtime complexity: m*log(n)

m = length of the smallest string in the list.

n = length of the list.

Categories
interview

Js reduce() polyfill

Array.prototype.reduce = function(fn, initialValue) {
  let acc = initialValue;

  for (const [key, val] of Object.entries(this)) {
    if (acc === undefined && key === '0') {
      acc = this[0];
    } else {
      acc = fn.call(null, acc, this[key], key, this);
    }
  }
  return acc;
};

const arr = [3, 4, 5, 0, -1];

console.log(arr.reduce((acc, curr) => acc + curr)); // 11

Demo

Categories
interview

Js filter() polyfill

Array.prototype.filter = function(callback, context) {
  const ret = [];
  for (const [key, val] of Object.entries(this)) {
    if (callback.call(context, this[key], key, this)) {
      ret.push(val);
    }
  }
  return ret;
};

console.log([4, -1, 1, 2, 3].filter(x => x >= 2)); // [4, 2, 3];

Demo

Categories
interview

Binary search

const binarySearch = (arr, x) => {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) /
 2);
    if (x === arr[mid]) {
      return mid;
    } else if (x < arr[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
};

const inpArr = [-1, 0, 2, 4, 9, 10, 3000];

console.log(binarySearch(inpArr, 2));  // 2

console.log(binarySearch(inpArr, 11)); // -1

// Runtime Complexity O(log(n))
// Space Complexity O(1)

Demo

Categories
interview

Subsets with no duplicates

Generate subsets with no duplicates.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const subsetsWithDup = (nums) => {
  if (!nums) {
    return;
  }

  const len = nums.length;
  const ret = [];
  const subsetStore = {};

  for (let i = 0; i < (1 << len); i++) {
    const currSubset = [];

    for (let j = 0; j < len; j++) {
      if ((1 << j) & i) {
        currSubset.push(nums[j]);
      }
    }

    const subsetKey = [...currSubset].sort((a,b) => a - b).join('.');

    if (!(subsetKey in subsetStore)) {
      ret.push(currSubset);
      subsetStore[subsetKey] = true;
    }

  }

  return ret;
};

console.log(subsetsWithDup([1,1,2]));
// [[], [1], [1, 1], [2], [1, 2], [1, 1, 2]]

Demo

Categories
interview

Looping through Arrays and Objects in Javascript

///  ARRAYS ///
const arr = [1, 2, 3];

for (const val of arr) {
  console.log(val);
}

for (const [key, val] of arr.entries()) {
  console.log(key, val);
}

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

///  OBJECTS ///

const obj = {
  abc: 123,
  cc: 33
};

for (const [key, val] of Object.entries(obj)) {
  console.log(key, val);
}

for (const [key] of Object.entries(obj)) {
  console.log(key);
}

for (let key in obj) { // returns Enumerable (peperties whose internal flag is set to true) properties as well.
  if (obj.hasOwnProperty()) {
    console.log(obj[key])
  }
}

Demo

Categories
interview

Servers that communicate

Given a 2D array that has 1s & 0s where 1 denotes a server, return the count of the number of servers that communicate with other servers. A server can communicate with another server only if they are in the same row/column.

For example: [ [1, 0],
[1, 1] ] output = 3

const countLiveServers = (inp) => {
  const rows = Array(inp.length).fill(0);
  const cols = Array(inp[0].length).fill(0);

  for (let i = 0; i < inp.length; i++) {
    for (let j = 0; j < inp[0].length; j++) {
      if (inp[i][j]) {
        rows[i]++;
        cols[j]++;
      }
    }
  }

  let liveServerCount = 0;
  for (let i = 0; i < inp.length; i++) {
    for (let j = 0; j < inp[0].length; j++) {
      if (inp[i][j] && (rows[i] > 1 || cols[j] > 1)) {
        liveServerCount++;
      }
    }
  }

  return liveServerCount;
};

console.log(countLiveServers([[1,0],[1,1]])); // 3

Demo

Categories
interview

Basic Calculator

Implement a function calculate() that takes a string as an input. The string can contain +, -, (, ), 0-9 and spaces. The function should return the result like a basic calculator.

/**
 * @param {string} str       
 * @return {number}
 */
const calculate = (str) => {
  if (!str) {
    return;
  }
  const stack = [];
  let operand = 0;
  let result = 0;
  let sign = 1;
  for (let i = 0; i < str.length; i++) {
    const curr = str.charAt(i);
    if (curr === '(') {
      stack.push(result);
      stack.push(sign);
      sign = 1;
      result = 0;
    } else if (curr === ')') {
      result += sign * operand;
      result *= stack.pop();
      result += stack.pop();
      operand = 0;
    } else if (curr === '+') {
      result += sign * operand;
      sign = 1;
      operand = 0;
    } else if (curr === '-') {
      result += sign * operand;
      sign = -1;
      operand = 0;
    } else if (!isNaN(parseInt(curr))) {
      operand = (operand * 10) + parseInt(curr);
    }
  }
  return result + (sign * operand);
};

console.log(calculate('1 + 1'));

Demo

Categories
interview

Bloomfilter in Js

We use multiple hash functions below to evenly space out the keys in the Bloom filter.

const arr = Array(Math.pow(2, 22) - 1).fill(0);
const HASHES_COUNT = 6;
const keys = ['John', 'Smith', 'Adam'];

const getHashes = (inp) => {
  const hashes = [];
  for (let i = 0; i < HASHES_COUNT; i++) {
    hashes.push(Math.abs(inp.split('').reduce((acc, curr) =>
      (acc >> i) - acc + curr.charCodeAt(0) | 0, 0)));
  }
  return hashes;
};

for (let key of keys) {
  const hashes = getHashes(key);
  for (const hash of hashes) {
    arr[hash] = 1;
  }
}

const isPresent = (key) => {
  const hashes = getHashes(key);
  for (const hash of hashes) {
    if (!arr[hash]) {
      return false;
    }
  }
  return true;
};

console.log(isPresent('John')); // true
console.log(isPresent('Smith')); // true
console.log(isPresent('Adam')); // true
console.log(isPresent('Sam')); // false
console.log(isPresent('Harry')); // false

Demo