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

Window.location object

Javascript can access the URL of the current page with window.location object. This object contains various properties of the URL such as protocol, host, pathname, search and more.

  • window.location.href returns the href (URL) of the current page
  • window.location.hostname returns the domain name of the web host
  • window.location.pathname returns the path and filename of the current page
  • window.location.protocol returns the web protocol used (http: or https:)
  • window.location.assign() loads a new document
<button class="newDocument">
   New Document
</button>
console.log(window.location.href); //"https://fiddle.jshell.net/_display/?editor_console=true"

console.log(window.location.hostname); //"fiddle.jshell.net"

console.log(window.location.pathname); //"/_display/"

console.log(window.location.protocol); //"https:"

//Window.location.assign - click on the "New Document" button to load a new document.

function newDocument() {
  window.location.assign("https://www.collegestash.com/")
}

const newDocButton = document.querySelector(".newDocument");

newDocButton.addEventListener('click', newDocument);

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