Categories
interview

Box Stacking Problem

Box stacking problem max height of stack possible (can be rotated). The length and breadth of the box beneath should be greater than the one stacked above it.

box-stacking
const getMaxHeight = (boxes) => {
  const rotatedBoxes = [];
  for (let i = 0; i < boxes.length; i++) {
    rotatedBoxes[3 * i] = boxes[i];
    rotatedBoxes[(3 * i) + 1] = {
      width: boxes[i].height,
      breadth: boxes[i].width,
      height: boxes[i].breadth,
      area: boxes[i].height * boxes[i].width
    };
    rotatedBoxes[(3 * i) + 2] = {
      width: boxes[i].breadth,
      breadth: boxes[i].height,
      height: boxes[i].width,
      area: boxes[i].breadth * boxes[i].height
    };
  }
  // Sort in non-increasing order. 
  rotatedBoxes.sort((box1, box2) => box2.area - box1.area);
  const maxStackedHeight = [];
  for (let i = 0; i < rotatedBoxes.length; i++) {
    maxStackedHeight[i] = 0;
    let box = rotatedBoxes[i];
    let prevMaxVal = 0;
    for (let j = 0; j < i; j++) {
      let prev = rotatedBoxes[j];
      if (prev.width > box.width && prev.breadth > box.breadth) {
        prevMaxVal = Math.max(prevMaxVal, maxStackedHeight[j]);
      }
    }
    maxStackedHeight[i] = prevMaxVal + box.height;
  }
  let max = 0;
  for (let i = 0; i < maxStackedHeight.length; i++) {
    max = Math.max(maxStackedHeight[i], max);
  }
  return max;
};

Test

console.log(getMaxHeight([{
                    width: 1,
                    breadth: 1,
                    height: 1,
                    area: 1,
                    }, {
                    width: 2,
                    breadth: 3,
                    height: 10,
                    area: 6,
                    }, {
                    width: 2,
                    breadth: 4,
                    height: 1,
                    area: 8,
                  }]));
// 16

Demo

Categories
Uncategorized

Mutation Observer

If you want to listen to DOM Mutations then you can use the Mutation Observer.

const observer = new MutationObserver((mutations) => {
  mutations.forEach(function(mutation) {
    for (let i = 0; i < mutation.addedNodes.length; i++) { // i.e., nodeList
      console.log(mutation.addedNodes[i]);
      // You can perform your actions here.
    }
  });
});
observer.observe(document.body, {
  childList: true,
  subtree: true,
  attributes: false,
  characterData: false,
});
Categories
interview

Quicksort

Worst Complexity: O(n^2)


const sort = (arr, low, high) => {
  if (low < high) {
    const p = getPartition(arr, low, high);
    sort(arr, low, p);
    sort(arr, p + 1, high);
  }
};

const getPartition = (arr, low, high) => {
  const pivot = arr[low + Math.floor((high - low) / 2)];
  low--;
  high++;
  while (true) {
    do {
      low++;
    } while (arr[low] < pivot)
    do {
      high--;
    } while (arr[high] > pivot)
    if (low >= high)
      return high;
    const temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
  }
};

const inp = [4, 3, 2, 1];
sort(inp, 0, inp.length - 1);
console.log(inp); // [1, 2, 3, 4]

Demo

Categories
interview

Merge Sort

Runtime Complexity: O(n*log(n))

const sort = (arr, low, high) => {
  if (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    sort(arr, low, mid);
    sort(arr, mid + 1, high);
    merge(arr, low, mid, high);
  }
}

const merge = (arr, low, mid, high) => {
  const leftSize = mid - low + 1;
  const rightSize = high - mid; // i.e., high - (mid+1) + 1;
  const left = [];
  const right = [];
  for (let i = 0; i < leftSize; i++) {
    left[i] = arr[low + i];
  }
  for (let i = 0; i < rightSize; i++) {
    right[i] = arr[mid + 1 + i];
  }
  let i = 0;
  let j = 0;
  while (i < leftSize && j < rightSize) {
    arr[low++] = left[i] <= right[j] ? left[i++] : right[j++];
  }
  while (i < leftSize) {
    arr[low++] = left[i++];
  }
  while (j < rightSize) {
    arr[low++] = right[j++];
  }
};

const inp = [4, 3, 2, 1];
sort(inp, 0, 3);
console.log(inp);
// [1, 2, 3, 4]

Demo

Categories
interview

Coin Change 2

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
const change = (amount, coins) => {
  const dp = [];
  for (let i = 0; i < amount + 1; i++) {
    dp[i] = 0;
  }
  dp[0] = 1;
  for (const [key, coin] of Object.entries(coins)) {
    for (let i = coin; i < amount + 1; i++) {
      dp[i] += dp[i - coin];
    }
  }
  return dp[amount];
};
// Analysis   n - length of coins
//            m - amount
// Time Complexity O(n*m)
// Space Complexity O(m)

Demo