CollegeStash

  • Valid Sudoku

    A valid Sudoku is a 9×9 grid puzzle where each row, column, and 3×3 subgrid contains the numbers 1 to 9 exactly once. Here is an example of a valid Sudoku:

    5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
---------------------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
---------------------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
    /**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
  if (!board) {
    return false;
  }
  const rowArr = [...Array(9)].map(x => new Object());
  const colArr = [...Array(9)].map(x => new Object());
  const boxObj = {};
  for (let i = 0; i < 9; i++) {
    let boxRow = 3 * Math.floor(i / 3) + '.';
    for (let j = 0; j < 9; j++) {
      let c = board[i][j];
      if (c !== '.') {
        if (c in rowArr[i]) {
          return false;
        } else {
          rowArr[i][c] = true;
        }
        if (c in colArr[j]) {
          return false;
        } else {
          colArr[j][c] = true;
        }
        const boxKey = boxRow + (3 * Math.floor(j / 3));
        if (!(boxKey in boxObj)) {
          boxObj[boxKey] = {};
        }
        if (c in boxObj[boxKey]) {
          return false;
        } else {
          boxObj[boxKey][c] = true;
        }
      }
    }
  }
  return true;
}

/**
 * @param {character[][]} board
 * @return {boolean}
 */
// var isValidSudoku = function(board) {
//     if (!board) {
//         return false;
//     }
//     for (let i = 0; i < board.length; i++) {
//       for (let j = 0; j < board[0].length; j++) { 
//           const c = board[i][j];
//           if ( c!== '.' && !valid(c, i , j, board)) {
//             return false;
//           }
//       }
//     }
//     return true;
// };

// var valid = function(c, i, j, board) {
//         const rowStart = 3 * Math.floor(i / 3);
//         const colStart = 3 * Math.floor(j / 3);
//         for (let k = 0; k < 9; k++) {
//           if ((k !== j && board[i][k] === c) || (k !== i && board[k][j] === c)) {
//             return false;
//           }
//             let row = rowStart + Math.floor(k / 3);
//             let col = colStart + (k % 3);
//             if (!(row === i && col === j) && c === board[row][col]) {
//                     return false;
//             }
//     }
//     return true;
// }

    Demo

  • Array.map() Polyfill

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

console.log([5, 4, 2].map((x, y) => {
  console.log(x, y);
  return 2 * x;
}));
/*
5, 0
4, 1
2, 2
[10, 8, 4]
*/

    Demo

  • Matrix Chain Multiplication

    const matrixChainMultiplication = (matrix, n) => {
  const dp = Array(100).fill(0).map(x => Array(100).fill(-1));
  // Ai Matrix dimensions = (i - 1) x (i)
  return MCM(matrix, 1, n - 1, dp);
};

const MCM = (matrix, i, j, dp) => {
  if (i === j) {
    return 0;
  }
  if (dp[i][j] !== -1) {
    return dp[i][j];
  }
  dp[i][j] = Number.MAX_VALUE;
  for (let k = i; k < j; k++) {
    dp[i][j] = Math.min(dp[i][j],
      MCM(matrix, i, k, dp) + MCM(matrix, k + 1, j, dp) + (matrix[i - 1] * matrix[k] * matrix[j]));
  }
  return dp[i][j];
};

const test = [1, 2, 3, 4, 3];
console.log(matrixChainMultiplication(test, test.length)); // 30

    Demo

  • Spiral Matrix

    /**
 * @param {number[][]} matrix
 * @return {number[]}
 */
const spiralOrder = function(matrix) {
  const list = [];
  let r1 = 0;
  let r2 = matrix.length - 1;
  let c1 = 0;
  let c2 = matrix[0].length - 1;
  while (c1 <= c2 && r1 <= r2) {
    for (let c = c1; c <= c2; c++)
      list.push(matrix[r1][c]);
    for (let r = r1 + 1; r <= r2; r++)
      list.push(matrix[r][c2]);
    if (r1 < r2 && c1 < c2) {
      for (let c = c2 - 1; c >= c1; c--)
        list.push(matrix[r2][c]);
      for (let r = r2 - 1; r > r1; r--)
        list.push(matrix[r][c1]);
    }
    r1++;
    r2--;
    c1++;
    c2--;
  }
  return list;
};

    Output

    const arr = [
  [1, 2, 3],
  [8, 9, 4],
  [7, 6, 5]
];

console.log(spiralOrder(arr));

// [1, 2, 3, 4, 5, 6, 7, 8, 9]

    Demo

  • Best time to buy and sell stock

    /**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function(prices) {
  let min = prices[0];
  let max = 0;
  for (const price of prices) {
    min = Math.min(min, price);
    max = Math.max(max, price - min);
  }
  return max;
};

console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5

    Demo

    n = size of input array

    Time complexity: O(n)

    Space complexity: O(1)

  • Container With Most Water

    /**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = (height) => {
  let low = 0;
  let high = height.length - 1;
  let max = 0;
  while (low < high) {
    max = Math.max(max, (high - low) * Math.min(height[low], height[high]));
    if (height[low] <= height[high]) {
      low++
    } else {
      high--;
    }
  }
  return max;
};

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

    Demo

  • Group Anagrams

    Group Permutations of the same strings in a given list in Javascript:

    /**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams = function(strs) {
  const obj = {};
  for (const str of strs) {
    const key = str.split('').sort().join('');
    (obj[key] || (obj[key] = [])).push(str);
  }
  return Object.values(obj);
};

console.log(groupAnagrams(['abc', 'bbc', 'cab', 'ccc']));
// [["abc", "cab"], ["bbc"], ["ccc"]]

    Demo

  • Rotate Image

    Javascript (ES6) code to rotate a Image or a 2D square matrix in place:

    const rotate = (matrix) => {
  const n = matrix.length;
  for (let layer = 0; layer < Math.floor(n / 2); layer++) {
    for (let i = layer; i < n - layer - 1; i++) {
      const temp = matrix[layer][i];
      matrix[layer][i] = matrix[n - i - 1][layer];
      matrix[n - i - 1][layer] = matrix[n - layer - 1][n - i - 1];
      matrix[n - layer - 1][n - i - 1] = matrix[i][n - layer - 1];
      matrix[i][n - layer - 1] = temp;
    }
  }
};

    Demo

    Output

    
rotate([
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]);

/*
[
  [7, 4, 1],
  [8, 5, 2],
  [9, 6, 3],
]
*/

  • Event Emitter pattern

    Event emitter pattern implemented using a Javascript ES6 class.

    class EventEmitter {
  events = {};

  subscribe = (event, cb) => {
    (this.events[event] || (this.events[event] = [])).push(cb);
    return {
      unsubscribe: () => {
        const arr = this.events[event];
        const index = arr.indexOf(cb);
        if (index < 0) {
          return;   
        }
        arr.splice(index, 1);
        if (arr.length === 0) {
          delete this.events[event]; 
        }
      }
    };
  };

  emit = (event, ...rest) => {
    (this.events[event] || []).forEach(val => {
      val(...rest);
    });
  };
}

const eventEmitter = new EventEmitter();
const ret1 = eventEmitter.subscribe('test', () => {
  console.log('test1');
});
const ret2 = eventEmitter.subscribe('test', () => {
  console.log('test2');
});
const ret3 = eventEmitter.subscribe('test3', () => {
  console.log('test3');
});
eventEmitter.emit('test'); // test1, test2
ret1.unsubscribe();
ret1.unsubscribe(); // Should still function as expected.
eventEmitter.emit('test'); // test2

    Demo

  • Employee badging times – Javascript

    We are working on a security system for a badged-access room in our company’s building.

    We want to find employees who badged into our secured room unusually often. We have an unordered list of names and entry times over a single day. Access times are given as numbers up to four digits in length using 24-hour time, such as “800” or “2250”.

    Write a function that finds anyone who badged into the room three or more times in a one-hour period. Your function should return each of the employees who fit that criteria, plus the times that they badged in during the one-hour period. If there are multiple one-hour periods where this was true for an employee, just return the earliest one for that employee.

    badge_times = [
    [‘Paul’, ‘1355’],
    [‘Jennifer’, ‘1910’],
    [‘Jose’, ‘835’],
    [‘Jose’, ‘830’],
    [‘Paul’, ‘1315’],
    [‘Chloe’, ‘0’],
    [‘Chloe’, ‘1910’],
    [‘Jose’, ‘1615’],
    [‘Jose’, ‘1640’],
    [‘Paul’, ‘1405’],
    [‘Jose’, ‘855’],
    [‘Jose’, ‘930’],
    [‘Jose’, ‘915’],
    [‘Jose’, ‘730’],
    [‘Jose’, ‘940’],
    [‘Jennifer’, ‘1335’],
    [‘Jennifer’, ‘730’],
    [‘Jose’, ‘1630’],
    [‘Jennifer’, ‘5’],
    [‘Chloe’, ‘1909’],
    [‘Zhang’, ‘1’],
    [‘Zhang’, ’10’],
    [‘Zhang’, ‘109’],
    [‘Zhang’, ‘110’],
    [‘Amos’, ‘1’],
    [‘Amos’, ‘2’],
    [‘Amos’, ‘400’],
    [‘Amos’, ‘500’],
    [‘Amos’, ‘503’],
    [‘Amos’, ‘504’],
    [‘Amos’, ‘601’],
    [‘Amos’, ‘602’],
    [‘Paul’, ‘1416’],
    ];

    Expected output (in any order)

    {
    Paul: [‘1315’, ‘1355’, ‘1405’],
    Jose: [‘830’, ‘835’, ‘855’, ‘915’, ‘930’],
    Zhang: [’10’, ‘109’, ‘110’],
    Amos: [‘500’, ‘503’, ‘504’],
    }
    n: length of the badge records array.

    const badge_records = [
  ['Paul', '1355'],
  ['Jennifer', '1910'],
  ['Jose', '835'],
  ['Jose', '830'],
  ['Paul', '1315'],
  ['Chloe', '0'],
  ['Chloe', '1910'],
  ['Jose', '1615'],
  ['Jose', '1640'],
  ['Paul', '1405'],
  ['Jose', '855'],
  ['Jose', '930'],
  ['Jose', '915'],
  ['Jose', '730'],
  ['Jose', '940'],
  ['Jennifer', '1335'],
  ['Jennifer', '730'],
  ['Jose', '1630'],
  ['Jennifer', '5'],
  ['Chloe', '1909'],
  ['Zhang', '1'],
  ['Zhang', '10'],
  ['Zhang', '109'],
  ['Zhang', '110'],
  ['Amos', '1'],
  ['Amos', '2'],
  ['Amos', '400'],
  ['Amos', '500'],
  ['Amos', '503'],
  ['Amos', '504'],
  ['Amos', '601'],
  ['Amos', '602'],
  ['Paul', '1416']
];

const getOftenUsersOfBadge = (records) => {
  records.sort((a, b) => a[1] - b[1]);
  const obj = {};
  for (const [name, time] of records) {
    (obj[name] || (obj[name] = [])).push(time);
  }
  const result = {};
  for (const [key, val] of Object.entries(obj)) {
    const len = val.length;
    if (len >= 3) {
      for (let i = 2; i < len; i++) {
        if (val[i] - val[i - 2] <= 100) {
          const start = i - 2;
          const max = parseInt(val[start]) + 100;
          while (parseInt(val[++i]) <= max) {}
          result[key] = val.slice(start, i);
          break;
        }
      }
    }
  }
  return result;
};

console.log(getOftenUsersOfBadge(badge_records));

/* Explanation:
1) Sort the input records based on times in increasing order.
2) Build a map { name : [time1, time2,  ... timen], }
3) Computing times
          1 --> 00:01
        101 --> 01:01
        diff is 100 for 1 hour.
    No need to check (i < len) in the while loop as we break the loop on first failure of condition.
*/

    Demo