Author: Shiva Charan Devabhaktuni

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

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.

Java

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

Continue reading “Sudoku Solver”
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);
    }
  };

  callApi = async () => {
    if (this.queue.length) {
      const keyMap = {};
      while (this.queue.length) {
        const [key, cb] = this.queue.shift();
        (keyMap[key] || (keyMap[key] = [])).push(cb);
      }
      try {
        const response = await fetch(this.url + Object.keys(keyMap).join(','));
        if (!response.ok) {
          throw 'Status: ' + response.status;
        }
        const data = await response.json();
        console.log(data)
        /*
        Testing for httpbin response.
                const data = {
                  args: {
                    key: "foo"
                  }
                };
        */
        data[data.args.key] = 12;
        for (const [key, val] of Object.entries(data)) {
          (keyMap[key] || []).forEach(cb => cb(val));
        }
      } catch (error) {
        throw error;
      }
      this.callApi();
    } else {
      this.blocked = false;
    }
  };
}

/* Test case */
const api = new Api('https://httpbin.org/get', 3000);
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

Categories
interview

Find the winner

Lets say you want to find the winner of a game where the participants pick up stones (n). If ‘A’ and ‘B’ are the 2 players, then the rules of the game are as follows:

  • Player ‘A’ always starts first.
  • Player ‘A’ always picks 1 stone.
  • Player ‘B’ always picks 2 stones.
  • Player ‘A’ and Player ‘B’ take alternate turns.
  • The player to pick up the last stone is the loser.

Write a method that returns the winner. There can be 3 possible outcomes “A | B | null”.

/** 
 * @param {number} n
 * @return {'A' | 'B' | null}
 */
function findWinner(n) {
  // A : true
  // B : false
  if (!n || n <= 0)
    return null;
  return whoWins(n - 1, true) ? 'A' : 'B';
}

function whoWins(n, player) {
  if (n <= 0)
    return !player;
  return whoWins(n - (player ? 2 : 1), !player);
}

/** Test cases **/
console.log(findWinner(1)); // B
console.log(findWinner(2)); // A
console.log(findWinner(3)); // A
console.log(findWinner(4)); // B
console.log(findWinner(0)); // null
console.log(findWinner(null)); // null

Demo

A shorter version of the above code in ES6.

const findWinner = (n) => (!n || n <= 0) ? null : whoWins(n - 1, true) ? 'A' : 'B';
const whoWins = (n, player) => (n <= 0) ? !player : whoWins(n - (player ? 2 : 1), !player);

/** Test cases **/
console.log(findWinner(1)); // B
console.log(findWinner(2)); // A
console.log(findWinner(3)); // A
console.log(findWinner(4)); // B
console.log(findWinner(0)); // null
console.log(findWinner(null)); // null

Demo

Iterative Solution

const findWinner = (n) => {
  if (!n || n < 1) {
    return null;
  }
  let totalStones = 0;
  let player = 1; // A
  while (totalStones < n) {
    totalStones += player ? 1 : 2;
    player = !player;
  }
  return player ? 'A' : 'B';
};

Demo

Using for loop

const findWinner = (n) => {
  if (!n || n < 1) {
    return null;
  }
  let player = 1; // A
  for (let totalStones = 0; totalStones < n; totalStones += player ? 1 : 2) {
    player = !player;
  }
  return player ? 'A' : 'B';
};

/** Test cases **/
console.log(findWinner(1));      // B
console.log(findWinner(2));      // A
console.log(findWinner(3));      // A
console.log(findWinner(4));      // B
console.log(findWinner(0));      // null
console.log(findWinner(null));   // null

Demo

Categories
interview

Multi List Iterator – Javascript

Print a list of lists vertically using an Iterator.

For example:

// Usage
const node = new MultiIterator([[1, 2], [], [4], [5]]);

while (node.hasNext()) {
  console.log(node.next());
}

Input:

[[1, 2], [], [4], [5]]

Output:

1

4

5

2
class MultiIterator {
  constructor(inp) {
    this.inp = inp;
    this.x = -1;
    this.inpLen = inp.length;
    this.levelProgress = Array(inp.length).fill(0);
    this.nextX = 0;
  }

  hasNext() {
    var count = 0;
    var listIndex = this.x;
    var elemIndex;
    do {
      listIndex++;
      listIndex %= this.inpLen;
      elemIndex = this.levelProgress[listIndex]; // index = size - 1
      count++;
    } while (count < this.inpLen && elemIndex === this.inp[listIndex].length)
    if (elemIndex === this.inp[listIndex].length) {
      return false;
    }
    this.nextX = listIndex;
    return true;
  }

  next() {
    if (this.hasNext()) {
      this.x = this.nextX;
      this.levelProgress[this.x]++;
      return this.inp[this.x][this.levelProgress[this.x] - 1];
    }
    return null;
  }
}

// Test Code
const node = new MultiIterator([
  [1, 2],
  [],
  [4],
  [5],
]);

while (node.hasNext()) {
  console.log(node.next());
}

Demo

You can print this list horizontally as well.

For example:

Input:

[[1, 2], [], [4], [5]]

Output:

1

2

4

5
class MultiIterator {
  constructor(inp) {
    this.inp = inp;
    this.x = 0;
    this.y = -1;
    this.inpLen = inp.length;
    this.nextX = 0;
    this.nextY = 0;
  }

  hasNext() {
    var listIndex = this.x;
    var elemIndex = this.y + 1;
    while (listIndex < this.inpLen && elemIndex === this.inp[listIndex].length) {
      listIndex++;
      elemIndex = 0;
    }
    if (listIndex === this.inpLen) {
      return false;
    }
    this.nextX = listIndex;
    this.nextY = elemIndex;
    return true;
  }

  next() {
    if (this.hasNext()) {
      this.x = this.nextX;
      this.y = this.nextY;
      return this.inp[this.nextX][this.nextY];
    }
    return null;
  }
}

// Test Code
const node = new MultiIterator([
  [1, 2],
  [],
  [4],
  [5],
]);

while (node.hasNext()) {
  console.log(node.next());
}

Demo