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

Categories
interview

Network Delay Time

Calculate and return the network delay time if all “n” nodes in a network can be reached can be reached. If they cannot be reached return -1.

Input times -> [source, target, weight (time)]
n -> Number of nodes
k -> Source node

1<= k <= n <= 100

You can assume that there are no multi nodes.

The Bellman-Ford algorithm can be used to solve this.

Runtime: O(n^2)

const networkDelayTime = (times, n, k) => {
  const distFromSource = new Array(n + 1);  // Since, k >= 1.
  distFromSource.fill(Number.MAX_VALUE, 1);
  distFromSource[k] = 0;
  
  // (n - 1) Edges.
  for (let i = 0; i < n-1; i++) {
    for (const time of times) {
      if (distFromSource[time[0]] !== Number.MAX_VALUE && (distFromSource[time[0]] + time[2]) < distFromSource[time[1]]) {
        distFromSource[time[1]] = distFromSource[time[0]] + time[2];
      }
    }
  }
  
  const max = Math.max(...distFromSource.slice(1));
  return max === Number.MAX_VALUE ? -1 : max;
};

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

Demo

Categories
interview

Longest Consecutive Sequence

Find the longest consecutive sequence in a given array of length “n” in 0(n) time.

For example, lets consider the following input:
[1000, 1001, 1002, 1003, 2001, 2, 3]
The longest consecutive sequence in this case would be
[1000, 1001, 1002, 1003]
The length of this array is 4.

/**
 * @param {number[]} nums
 * @return {number}
 */
const longestConsecutive = function(nums) {
  if (!nums || !nums.length) {
    return 0;
  }

  var obj = {};

  for (let val of nums) {
    obj[val] = true;
  }

  let max = 1;

  for (let val of nums) {
    if (!((val - 1) in obj)) {
      let currLen = 1;
      let curr = val;
      while ((curr + 1) in obj) {
        curr++;
        currLen++;
      }
      max = Math.max(max, currLen);
    }
  }

  return max;
};

console.log(longestConsecutive([1000, 1001, 1002, 1003, 2001, 2, 3]));
// 4

Demo

Categories
interview

Sudoku Solver – Javascript

This solution uses DFS (Depth First Search) Algorithm and looks for a unique solution to the given Sudoku Puzzle.

DFS Solution

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
const solveSudoku = function(board) {
  canSolveCheck(board, 0, 0);
};

// sudoku solver (backtracking) Time complexity = O(9^m)  m = number of spaces to be filled.

const canSolveCheck = (board, x, y) => {
  if (x === 9) {
    return true;
  } else if (y === 9) {
    return canSolveCheck(board, x + 1, 0);
  }
  if (board[x][y] !== '.') {
    return canSolveCheck(board, x, y + 1);
  } else {
    for (let i = 1; i <= 9; i++) {
      board[x][y] = i + '';
      if (valid(board, x, y) && canSolveCheck(board, x, y + 1)) {
        return true;
      }
      board[x][y] = '.';
    }
    return false;
  }
};

const valid = (board, x, y) => {
  const i = board[x][y];
  for (let k = 0; k < 9; k++) {
    if (k !== y && board[x][k] === i) {
      return false;
    }
    if (k !== x && board[k][y] === i) {
      return false;
    }
    const row = Math.floor(x / 3) * 3 + Math.floor(k / 3);
    const col = Math.floor(y / 3) * 3 + (k % 3);
    if (!(row === x && col === y) && board[row][col] === i) {
      return false;
    }
  }
  return true;
};

Using a Map

Instead of running valid() for all possible values, we can pre-compute and check if the current value is valid.


const solveSudoku = function(board) {
  canSolveCheckMemoryOptimized(board, 0, 0);
};

const canSolveCheckMemoryOptimized = (board, x, y) => {
  if (x === 9) {
    return true;
  } else if (y === 9) {
    return canSolveCheck(board, x + 1, 0);
  }
  if (board[x][y] !== '.') {
    return canSolveCheck(board, x, y + 1);
  } else {
    const obj = {};
    buildObj(board, x, y, obj);
    for (let i = 1; i <= 9; i++) {
      board[x][y] = i + '';
      if (!(board[x][y] in obj) && canSolveCheck(board, x, y + 1)) {
        return true;
      }
      board[x][y] = '.';
    }
    return false;
  }
};

const buildObj = (board, x, y, obj) => {
  for (let k = 0; k < 9; k++) {
   obj[board[x][k]] = true;
   obj[board[k][y]] =true;
   const row = Math.floor(x / 3) * 3 + Math.floor(k / 3);
   const col = Math.floor(y / 3) * 3 + (k % 3);
   obj[board[row][col]] = true;
  }
};

Demo

Another alternate solution would be to precompute these values into lists of Maps.

Categories
interview

Group API calls with callbacks (asynchronous)

Write a class with a method getKey(key, callback) that invokes an API with the provided key. The method should also invoke a callback with the corresponding value returned by the API . Calls that are made within a given interval should be grouped.

Input:
getKey(v1/get?key=foo , ()=> console.log(x));

Output:
Let us assume the API returns the following
{foo: 50} 
Then the callback is going to be invoked with corresponding value 50
// 50

API call with grouped keys, is used when the the subsequent calls are made within a 20 ms delay for example,

Input:
getKey(v1/get?key=foo , ()=> console.log(x)); // at t = 0
getKey(v1/get?key=bar , ()=> console.log(x)); // at t = 10
getKey(v1/get?key=foo , ()=> console.log(x)); // at t =20

Output:
Let us assume the API (domain/get?key=foo,bar,foo) returns the following
{foo: 50, bar: 100} 
Then the callbacks are going to be invoked with the corresponding values 50, 100 and 50.
// 50
// 100
// 50
class Api {
   constructor(url, delay) {
     this.url = url + '?key=';
     this.delay = delay;
     this.queue = [];
     this.blocked = false;
   }

 getkey(key, cb) {
     this.queue.push([key, cb]);
     if (!this.blocked) {
       this.blocked = true;
       setTimeout(() => this.callApi(), this.delay)
     }
   }

 async callApi() {
     if (this.queue.length) {
       let keys = '';
       const keyMap = {};
       while (this.queue.length) {
         const [key, cb] = this.queue.shift();
         keys = keys === '' ? key : keys + ',' + key;
         (keyMap[key] || (keyMap[key] = [])).push(cb);
       }
       try {
         const response = await fetch(this.url + keys);
         if (!response.ok) {
           throw 'Status: ' + response.status;
         }
         const data = await response.json();
         // testing for
         data[data.args.key] = 12;
         for (const [key, val] of Object.entries(data)) {
           keyMap[key] && keyMap[key].forEach(cb => cb(val));
         }
       } catch (e) {
         throw e;
       }
       this.callApi();
     } else {
       this.blocked = false;
     }
   }

 }

 /* Test case */
 const api = new Api('https://httpbin.org/get', 20)
 const test = (x) => console.log(x);
 api.getkey('foo', test)

Demo

Categories
interview

Find the City With the Smallest Number of Neighbors at a Threshold Distance

For a given bidirectional weighted graph, find the node (city) with the least number of nodes reachable within a given threshold.

Note: If there are multiple such nodes, then return the node with the highest value among them.

Time Complexity: O(n^3)

const findtheCity = (n, edges, threshold) => {
  const adjMatrix = Array(n);

  for (let i = 0; i < n; i++) {
    adjMatrix[i] = [];
    for (let j = 0; j < n; j++) {
      adjMatrix[i][j] = (i === j) ? 0 : Number.MAX_VALUE;
    }
  }

  for (const val of edges) {
    adjMatrix[val[0]][val[1]] = val[2];
    adjMatrix[val[1]][val[0]] = val[2];
  }

  fw(adjMatrix);

  let minNeighbours = Number.MAX_VALUE;
  let neighbour;
  for (let i = 0; i < n; i++) {
    let currNeighbours = 0;

    for (let j = 0; j < n; j++) {
      if (adjMatrix[i][j] <= threshold) {
        currNeighbours++;
      }
    }

    if (currNeighbours <= minNeighbours) {
      minNeighbours = currNeighbours;
      neighbour = i;
    }
  }

  return neighbour;
};


const fw = (adjMatrix) => {
  const n = adjMatrix.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        adjMatrix[i][j] = Math.min(adjMatrix[i][j],
        adjMatrix[i][k] + adjMatrix[k][j]);
      }
    }

  }
};

console.log(findtheCity(4, [
  [0, 1, 3],
  [1, 2, 1],
  [1, 3, 4],
  [2, 3, 1]
], 4)); // 3

Demo