CollegeStash

Author: Shiva Charan Devabhaktuni

  • HTMLElement to Virtual DOM and back

    /**
 * @param {HTMLElement} 
 * @return {object} object literal presentation
 */
function virtualize(element) {
  if (element.nodeType === 3)
    return element.textContent;
  const ret = {
    type: element.tagName.toLowerCase(),
    props: {
      children: []
    }
  };
  element.childNodes.forEach(child => ret.props.children.push(virtualize(child)));
  if (ret.props.children.length === 1)
    ret.props.children = ret.props.children[0];
  for (const {
      name,
      value
    } of element.attributes)
    ret.props[name === 'class' ? 'className' : name] = value;
  return ret;
}

/**
 * @param {object} valid object literal presentation
 * @return {HTMLElement} 
 */
function render(obj) {
  if (typeof obj === 'string') return document.createTextNode(obj);
  const {
    type,
    props: {
      children,
      ...attributes
    }
  } = obj;
  const ret = document.createElement(type);
  const childNodes = typeof children === 'string' ? [children] : children;
  childNodes.forEach(childNode => ret.append(render(childNode)));
  for (const [key, val] of Object.entries(attributes)) {
    ret.setAttribute(key === 'className' ? 'class' : key, val)
  }
  return ret;
}

    Demo

  • Is Element in View

    <body onscroll="onscroll()">

  <div style="width: 400px; height:800px; border:1px solid #222;">Scroll Down</div>

  <div id="demo">
    Demo
  </div>

</body>

    const isInView = (element) => {
  const {
    top,
    right,
    bottom,
    left
  } = element.getBoundingClientRect();

  return top >= 0 &&
    left >= 0 &&
    right <= (window.innerWidth || document.documentElement.clientWidth) &&
    bottom <= (window.innerHeight || document.documentElemetn.clientHeight);
};

const demo = document.getElementById('demo');

const onscroll = function() {
  console.log(isInView(demo));
};

    Demo

  • accessKey

    <div>Test</div>
    const demo = document.getElementById('demo');

 demo.onclick = (e) => {
   console.log(e.target.textContent);
 };
 demo.accessKey = 'w';

 // Alt + W for Windows + Chrome
 // [Control] [Option] + accesskey for Mac
 // Alt + W for Linux + Chrome

    Demo

  • Serialize / Deserialize

    You can do in this in many ways, the following code does this using prefix traversal.

    /**
 * @param {Node} root
 * @return {string}
 */
function serialize(root) {
  if(!root) return '_';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

/**
 * @param {string} str
 * @return {Node}
 */
function deserialize(str) {
  const q = str.split(',');
  return dfs(q);

 /**
 * @param {string} str
 * @return {Node}
 */
  function dfs(que) {
    if(!que.length) return null;
    const n = que.shift()
;
    if(n !== '_') {
      const node = new Node(n.value)
      node.left = dfs(q);
      node.right = dfs(q);
      return node;
    }
    return null;
  }
}

  • DOM Elements as Keys in Object

    To store DOM Elements as keys in object without using WeakMap( ), we can do the following:

    <div id="root"></div>
<script>
  class NodeStore {
    static key = 'key';

    set(node, value) {
      node.dataset[NodeStore.key] = value;
    }

    get(node) {
      return this.has(node) && node.dataset[NodeStore.key];
    }

    has(node) {
      return NodeStore.key in (node?.dataset || {});
    }
  }

  const nodeStore = new NodeStore();
  const root = document.getElementById('root');
  nodeStore.set(root, 'root value');
  console.log(nodeStore.has(root)); // true
  console.log(nodeStore.get(root)); // 'root value'
</script>

    Demo

    However the above solution can only support values of type string. To support any type of value we can use the following solution:

    <div id="root"></div>
<script>
class NodeStore {
  static key = 'key';
  constructor() {
    this.map = {};
    this.counter = 0;
  }
   /**
   * @param {Node} node
   * @param {any} value
   */
  set(node, value) {
    node[NodeStore.key] = this.counter;
    this.map[this.counter++] = value;
  }
  /**
   * @param {Node} node
   * @return {any}
   */
  get(node) {
     if (this.has(node)) {
       return this.map[node[NodeStore.key]];
     }
     return;
   }
  
  /**
   * @param {Node} node
   * @return {Boolean}
   */
  has(node) {
    return NodeStore.key in node;
  }
}
const nodeStore = new NodeStore();
const root = document.getElementById('root');
nodeStore.set(root, 22);
console.log(nodeStore.has(root)); // true
console.log(nodeStore.get(root)); // 22
</script>

    Demo

  • Alien Dictionary

    Given a list of words (Strings), generate the order of the language. If the given input is invalid you can return an empty string (”). Sometimes, multiple orders are possible. The following approach uses Topological Sort and DFS (Depth First Search).

    const buildAdjacencyList = (wordList, adjacencyList) => {
   for (const word of wordList) {
     for (let i = 0; i < word.length; i++) {
       if (!adjacencyList.has(word.charAt(i))) {
         adjacencyList.set(word.charAt(i), []);
       }
     }
   }

 for (let i = 0; i < wordList.length - 1; i++) {              
     const firstWord = wordList[i];
     const secondWord = wordList[i + 1];
     if (firstWord.startsWith(secondWord) && firstWord.length > secondWord.length) {
       return false;
      }
     const minLen = Math.min(firstWord.length, secondWord.length);
     for (let j = 0; j < minLen; j++) {
       const firstWordChar = firstWord.charAt(j);
       const secondWordChar = secondWord.charAt(j);
       if (firstWordChar !== secondWordChar) {
         // Store in reverse to get the correct order in the end.
         adjacencyList.get(secondWordChar).push(firstWordChar);
         break;
       }
     }
   }
   return true;
 };

 const topologicalSort = (currChar, adjacencyList, visited, resultStack) => {
   if (!(currChar in visited)) {
     visited[currChar] = false;
     if (adjacencyList.has(currChar)) {
       for (const char of adjacencyList.get(currChar)) {
         const result = topologicalSort(char, adjacencyList, visited, resultStack);
         if (!result) return false;
       }
     }
     visited[currChar] = true;
     resultStack.push(currChar);
     return true;
   } else {
            return visited[currChar];
           }
 };

 var alienOrder = function(words) {
   const adjacencyList = new Map();
   const valid = buildAdjacencyList(words, adjacencyList);
   if (!valid) {
     return '';
   }
   const resultStack = [];
   const visited = {};
   for (const [key, value] of adjacencyList) {
     const result = topologicalSort(key, adjacencyList, visited, resultStack);
     if (!result) {
       return '';
     }
   };
   if (resultStack.length !== adjacencyList.size) {
     return '';
   }
   return resultStack.join('');
 };

 console.log(alienOrder(['dog', 'dot', 'dotted']));
 // "dogte"

    Demo

  • Maximum height by stacking Cuboids

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

    box-stacking

    Javascript

    const maxHeight = (cuboids) => {
  // Sort each cuboid dimensions.
  for (const cuboid of cuboids) {
    cuboid.sort((a, b) => a - b);
  }
  
  // Sort the cuboids from largest to smallest order.
  cuboids.sort((a, b) => {
    if (a[0] != b[0]) {
      return b[0] - a[0];
    }
    if (a[1] != b[1]) {
      return b[1] - a[1];
    }
    return b[2] - a[2];
  });
  
  // dp[i] means max height upto cuboid 'i' (row i).
  const dp = Array(cuboids.length);
  
  for (let i = 0; i < cuboids.length; i++) {
    // We choose the largest side of cuboid to be height to maximize it.
    dp[i] = cuboids[i][2];
    for (let j = 0; j < i; j++) {
      if (cuboids[j][0] >= cuboids[i][0] && cuboids[j][1] >= cuboids[i][1] && cuboids[j][2] >= cuboids[i][2]) {
        dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
      }
    }
  }
  
  return Math.max(...dp);
}

console.log(maxHeight([
  [1, 1, 1 ],
  [2, 3, 10],
  [2, 4, 1 ],
]));
// 15

    Demo

  • 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