Author: Shiva Charan Devabhaktuni

Categories
interview

Promise.all() polyfill

Javascript

Promise.alll = promises => new Promise((resolve, reject) => {
  let count = 0;
  const responses = [];
  promises.forEach((promise, index) => {
    promise.then((response) => {
      responses[index] = response;
      if (++count === promises.length) {
        resolve(responses);
      }
    }).catch(reject);
  })
});

const promise1 = Promise.resolve(3);
const promise2 = Promise.resolve(6);
const promise3 = Promise.resolve(9);
Promise.alll([promise1, promise2, promise3]).then((values) => {
  console.log(values);
}).catch((error) => {
  console.log(error);
});

Output

[3, 6, 9]

Demo

Categories
interview

Invert Binary Tree

Javascript

/**
 * Definition for a binary tree node.
 */
 class TreeNode {
  constructor(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
const invertTree = root => root !== null ? new TreeNode(root.val, invertTree(root.right), invertTree(root.left)) : null;

// Alternate answer.
function invert(node) {
  if (!node) return node;
  [node.right, node.left] = [invert(node.left), invert(node.right)];
  return node;
}
Categories
interview

Largest Rectangular Area in a Histogram

/**
 * @param {number[]} inp
 * @return {number}
 */
const largestRectangleArea = function(inp) {
  const s = [];
  let i = 0;
  let max = 0;
  while (i < inp.length) {
    const val = inp[i];
    if (!s.length || val >= inp[s[s.length - 1]]) {
      s.push(i++);
    } else {
      const top = s.pop();
      max = Math.max(s.length ? (i - s[s.length - 1] - 1) * inp[top] : i * inp[top], max);
    }
  }
  while (s.length) {
    const top = s.pop();
    max = Math.max(s.length ? (i - s[s.length - 1] - 1) * inp[top] : i * inp[top], max);
  }
  return max;
};

Demo

Categories
interview

Improving React Performance with useMemo and useCallback Hooks

useMemo and useCallback are two React hooks that can help improve performance in your application by optimizing the rendering of your components.

useMemo is used to memoize a value and only recalculate it when one of its dependencies changes. This is useful when you have a costly calculation that you don’t want to perform on every render. useMemo takes two arguments: a function that returns the value to be memoized, and an array of dependencies. The value returned by the function will only be recalculated when one of the dependencies changes.

const memoizedValue = useMemo(() => {
  // perform a costly calculation
  return result;
}, [dependency1, dependency2]);

useCallback is similar to useMemo, but it is used to memoize a function instead of a value. This is useful when you have a function that you want to pass down to child components as a prop, but you don’t want it to be re-created on every render. useCallback takes two arguments: a function, and an array of dependencies. The function returned by useCallback will only be re-created when one of the dependencies changes.

const memoizedFunction = useCallback((arg1, arg2) => {
  // perform some logic
}, [dependency1, dependency2]);

In general, you should use useMemo to memoize a value and useCallback to memoize a function. However, if you have a function that returns a value, you can use useMemo instead of useCallback.

Categories
interview

Understanding the Difference Between event.target and event.currentTarget in JavaScript

In JavaScript, when handling an event in the browser, there are two different ways to access the event target: event.currentTarget and event.target.

event.target refers to the element on which the event was originally triggered. This may be the element that was clicked on or interacted with by the user.

event.currentTarget refers to the element that the event listener is attached to. This may be the parent element or some other ancestor of the element that was clicked on.

Here’s an example to illustrate the difference between event.target and event.currentTarget:

<body>
  <div class="parent">
    <button class="child">Click me</button>
  </div>
</body>

<script>
  const parent = document.querySelector('.parent');
  const child = document.querySelector('.child');

  parent.addEventListener('click', function(event) {
    console.log(`Current target: ${event.currentTarget.tagName}`);
    console.log(`Target: ${event.target.tagName}`);
  });

  child.addEventListener('click', function(event) {
    console.log(`Current target: ${event.currentTarget.tagName}`);
    console.log(`Target: ${event.target.tagName}`);
  });
</script>

In this example, we have a parent element with a child element inside it. We attach a click event listener to both the parent and child elements.

When we click on the child element, the event listener attached to the child element is triggered first. In this case, the current target and target are both the child element.

Next, the event listener attached to the parent element is triggered because the click event bubbles up from the child element to its parent. In this case, the current target is the parent element (because that’s where the event listener is attached), but the target is still the child element (because that’s where the click event originated).

So, in summary, event.currentTarget refers to the element that the event listener is attached to, while event.target refers to the element on which the event was originally triggered.

Categories
interview

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

Categories
interview

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

Categories
interview

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

Categories
interview

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

Categories
interview

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)