CollegeStash

  • Js reduce() polyfill

    Array.prototype.reduce = function(callback, initialValue) {
  let acc = initialValue;
  for (let index = 0; index < this.length; index++) {
    if (!index && acc === undefined) {
      acc = this[index];
    } else {
      acc = callback(acc, this[index], index, this);
    }
  }
  return acc;
};

const arr = [3, 4, 5, 0, -1];
console.log(arr.reduce((acc, curr) => acc + curr)); // 11

    Demo

  • Array.filter() polyfill

    Array.prototype.filter = function(callback, context) {
  const ret = [];
  for (let index = 0; index < this.length; index++) {
    if (callback.call(context, this[index], index, this)) {
      ret.push(this[index]);
    }
  }
  return ret;
};

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

    Demo

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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