CollegeStash

  • 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,
});

  • Quicksort

    Worst Case Time Complexity: O(n^2)

    const quickSort = (arr, low, high) => {
  if (low >= 0 && high >= 0 && low < high) {
    const partition = getPartition(arr, low, high);
    quickSort(arr, low, partition);
    quickSort(arr, partition + 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;
    }
    swap(arr, low, high);
  }
};

const swap = (arr, a, b) => {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

const arr = [4, 3, -1, 4, 1, 0];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]

    Demo

  • Merge Sort

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

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

const merge = (arr, low, mid, high) => {
  const tempArr = [];
  let i = low;
  let j = mid + 1;
  let k = 0;
  while (i <= mid && j <= high) {
    tempArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
  }
  while (i <= mid) {
    tempArr[k++] = arr[i++];
  }
  while (j <= high) {
    tempArr[k++] = arr[j++];
  }
  for (const val of tempArr) {
    arr[low++] = val;
  }
};

const arr = [4, -1, 1, 0, 3, 4];
mergeSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]

    Demo

  • Coin Change II

    The following solution uses “Bottom up dynamic programming” approach.

    /**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
const change = (amount, coins) => {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let i = coin; i <= amount; 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

  • Reorganize String (Js)

    /**
 * @param {string} S
 * @return {string}
 */
const reorganizeString = (S) => {
  let counts = [];
  for (let i = 0; i < 26; i++) {
    counts[i] = 0;
  }
  for (let i = 0; i < S.length; i++) {
    counts[S.charAt(i).charCodeAt(0) - 'a'.charCodeAt(0)] += 100;
  }
  for (let i = 0; i < 26; i++) {
    counts[i] += i;
  }
  //Encoded counts[i] = 100*(actual count) + (i)
  counts.sort((a, b) => a - b);
  let t = 1;
  let ret = [];
  for (let i = 0; i < 26; i++) {
    const ch = String.fromCharCode('a'.charCodeAt(0) + (counts[i] % 100));
    let count = Math.floor(counts[i] / 100);
    if (count > Math.floor((S.length + 1) / 2))
      return '';
    while (count > 0) {
      if (t >= S.length)
        t = 0;
      ret[t] = ch;
      t += 2;
      count--;
    }
  }
  return ret.join('');
};

console.log(reorganizeString('aab'));
// 'aba'

    Demo

  • Decode String (Js)

    Given an encoded string 3[abc]2[bc] the decoded output should be of the form “abcabcabcbcbc”. Assume that all the brackets are well formed and that all strings are encoded correctly.

    /**
 * @param {string} s
 * @return {string}
 */
const decodeString = (str) => {
  const stack = [];
  for (const ch of str.split('')) {
    if (ch === ']') {
      let currStr = '';
      while (stack[stack.length - 1] !== '[') {
        currStr = stack.pop() + currStr;
      }
      stack.pop();
      let k = 0;
      let base = 1;
      while (stack.length && parseInt(stack[stack.length - 1]) >= 0) {
        k += parseInt(stack.pop()) * base;
        base *= 10;
      }
      if (k !== 0) {
        stack.push(currStr.repeat(k));
      }
    } else {
      stack.push(ch);
    } 
  }
  return stack.join('');
};

    Demo

  • Meeting Rooms II

    Given a list of meetings, that may or may not overlap, calculate the total number of rooms that are required to conduct all the meetings according to the schedule.

    Java

    class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int endPtr = 0, rooms = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (start[i] < end[endPtr]) {
                rooms++;
            } else {
                endPtr++;
            }
        }
        return rooms;
    }
}

    Runtime Complexity: O(nlog(n))

    Space Complexity: O(n)

    Javascript (ES6)

    /**
 * @param {number[][]} intervals
 * @return {number}
 */
const minMeetingRooms = (intervals) => {
  let startList = [];
  let endList = [];
  let endPos = 0;
  let rooms = 0;
  for (const [start, end] of intervals) {
    startList.push(start);
    endList.push(end);
  }
  startList.sort((a, b) => a - b);
  endList.sort((a, b) => a - b);
  for (let i = 0; i < intervals.length; i++) {
    if (startList[i] < endList[endPos]) {
      rooms++;
    } else {
      endPos++;
    }
  }
  return rooms;
};

// console.log(minMeetingRooms([[7, 10],[2, 4]]));
// 1

    Demo

  • Word Break

    Given a non-empty string “word” can it be broken into a list of non-empty words contained in a dictionary ? The words can be repeated.

    Java

    public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

    JavaScript (ES6)

    /**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
const wordBreak = (s, wordDict) => canWordBreak(s, 0, wordDict);

const dp = {};

const canWordBreak = (word, index, wordDict) => {
  if (index === word.length) {
    return dp[index] = true;
  }
  if (dp[index] !== undefined) {
    return dp[index];
  }
  for (let breakIndex = index + 1; breakIndex <= word.length; breakIndex++) {
    if (wordDict.indexOf(word.substring(index, breakIndex)) > -1 && canWordBreak(word, breakIndex, wordDict)) {
      return dp[index] = true;
    }
  }
  return dp[index] = false;
}

// console.log(wordBreak("catsandog",
// ["cats","dog","sand","and","cat"]));
// false

    Demo

  • Script tag Async vs Defer

    In HTML5 you can use async or defer attributes to load javascript scripts using the script tag. Both async and defer tags make the loading of the script file asynchronous. Both these script tag attributes are compatible in all the major browsers out there today.

    Async

    Using the async attribute on a script tag, makes the script load asynchronously and executes it then.

    <script src="example_script.js" async></script>

    Defer

    Using the defer attribute on a script tag, makes the script load asynchronously and then wait until the whole page is finished parsing, for the script to execute. This attribute shouldn’t be used if the “src” attribute on the script tag is absent as this has no effect on inline scripts.

    <script src="example_script.js" defer></script>

    If you want to collect/respond to user clicks and you are using deferred loading of the javascript file that handles this, then the page may seem broken to the user, or you might miss some clicks based on the scenario.

  • Throttling function calls with a Queue in Javascript (ES6)

    The following ES6 Javascript code, helps to throttle function calls without discarding them. It uses a queue to keep track of all the function calls. We can use the reset method to reset the queue and the setTimeout() method.

    const throttle = (fn, delay) => {
  let timeout;
  let noDelay = true;
  let queue = [];
  const start = () => {
    if (queue.length) {
      const {context, args} = queue.shift();
      fn.apply(context, arguments);
      timeout = setTimeout(start, delay);
    } else {
      noDelay = true;
    }
  };

  const ret = (...args) => {
    queue.push({
      context: this,
      args,
    });
    if (noDelay) {
      noDelay = false;
      start();
    }
  };

  ret.reset = () => {
    clearTimeout(timeout);
    queue = [];
  };
  return ret;
};

/* Usage */
const print = (number) => {
  console.log(`Hello World! ${number}`);
}

const test = throttle(print, 3000);

test(1);
test(2);
test(3);

// test.reset(); This will clear the queue and hence the above test case will only output the first line.
// Output:
// Hello World! 1
// Hello World! 2
// Hello World! 3

    Demo