CollegeStash

  • Longest Palindromic Substring

    /**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  if (!s || s.length === 0)
    return '';
  let start = 0,
    end = 0;
  for (let i = 0; i < s.length; i++) {
    // There can be 2n - 1 centers for the palindromes. We can 
    // include each character and the space in between the       
    // characters.
    let l1 = expandAroundCenters(s, i, i);
    let l2 = expandAroundCenters(s, i, i + 1);
    let l = Math.max(l1, l2);
    if (l > end - start) {
      start = i - Math.floor((l - 1) / 2);
      end = i + Math.floor(l / 2);
    }
  }
  return s.substring(start, end + 1);
};

var expandAroundCenters = function(s, left, right) {
  while (left >= 0 &&
    right < s.length &&
    s.charAt(left) === s.charAt(right)) {
    left--;
    right++;
  }
  return right - left - 1;
}

// Time Complexity O(n ^ 2)
// Space Complexity O(1)

  • Smooth Animation

    The following is a method to perform smooth animation of an element from left to right given the duration and distance. In this example, the element is being animated from left to right at 60 fps for a duration of 5 seconds and a distance of 100px. The animation is cancelled midway at 3 seconds using cancelAnimationFrame().

    Javascript

    const animate = (element, duration/*seconds*/, distance) => {
  if (!element) {
    return;
  }
  element.style.position = 'relative';
  let start;
  let requestID;
  const durationMs = duration * 1000; // Milliseconds.
  const step = (timestamp) => {
    if (start === undefined)
      start = timestamp;
    const elapsed = timestamp - start;
    const fraction = Math.min(elapsed / durationMs, 1);
    element.style.transform = `translateX(${fraction * distance}px)`;
    if (elapsed < durationMs) { // Stop the animation after duration.
      requestID = requestAnimationFrame(step);
    }
  }
  requestID = requestAnimationFrame(step);
  return () => {
    element.style.transform = 'translateX(0px)';
    cancelAnimationFrame(requestID);
  };
}

const cancel = animate(document.getElementById('child'), 5, 100);

setTimeout(() => {
  cancel();
}, 3000);

    HTML

    <div id="parent">
  <div id="child">
  </div>
</div>

    CSS

    #parent {
  height: 200px;
  width: 200px;
  background-color: lightblue;
}
#child {
  height: 100px;
  width: 100px;
  background-color: lightgreen;
}
    Demo

    This can be further optimized using the FLIP technique

  • Random Pick Index

    Given an input array that consists of numbers that may consist of duplicates, return the position of the number that is picked. This position has to be a “Random Pick Index” if the picked number has duplicates.

    Example: Input: [1, 2, 4, 4, 4], Pick -> 4 then you can return 2, 3, or 4 randomly with equal probability. If 1 is the pick then 0 needs to be returned as there is only one occurrence at 0.

    /**
 * @param {number[]} nums
 */
var Solution = function(nums) {
  this.obj = {};
  for (let i = 0; i < nums.length; i++) {
    if (this.obj[nums[i]] === undefined)
      this.obj[nums[i]] = [];
    this.obj[nums[i]].push(i);
  }
};

/** 
 * @param {number} target
 * @return {number}
 */
Solution.prototype.pick = function(target) {
  var dupes = this.obj[target].length;
  return dupes === 1 ?
    this.obj[target][0] :
    this.obj[target][Math.floor(dupes * Math.random())];
};

/** 
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(nums)
 * var param_1 = obj.pick(target)
 */

  • DFS DOM (ES6)

    <div id="root">
  <div>
    <ul>
      <li>1</li>
      <li>2</li>
      <li>3</li>
    </ul>
  </div>
  <div>
    <ul>
      <li>1</li>
      <li>2</li>
      <li>3</li>
    </ul>
  </div>
</div>
    const root = document.getElementById('root');

const dfs = function(root, ret = []) {
  let obj = root.children;
  for (const val of root.children) {
    if (val.textContent === '1') {
      ret.push(val.tagName.toLowerCase());
    } else {
      dfs(val, ret);
    }
  }
  return ret;
};

console.log(dfs(root));
// ['li', 'li']

    Demo

  • Find Identical Node in DOM Tree

    <!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width">
    <title>DOM Traversal</title>
  </head>
  <body>
    <div id="rootA">
      <div>
        <div></div>
      </div>
      <div></div>
      <div>
        <div>
          <div id="nodeA"></div>
          <div></div>
        </div>
      </div>
    </div>

    <div id="rootB">
      <div>
        <div></div>
      </div>
      <div></div>
      <div>
        <div>
          <div id="nodeB">Node B</div>
          <div></div>
        </div>
      </div>
    </div>
  </body>
</html>

    const rootA = document.getElementById("rootA");
const rootB = document.getElementById("rootB");
const nodeA = document.getElementById("nodeA");

const path = [];
const findPath = () => {
  let currNode = nodeA;
  while (currNode !== rootA) {
    path.push(
      [...currNode.parentElement.children]
      .indexOf(currNode)
    );
    currNode = currNode.parentElement;
  }
};

const findB = () => {
  let currNode = rootB;
  while (path.length) {
    currNode = currNode.children[path.pop()];
  }
  return currNode;
};

findPath();

console.log(findB().innerHTML); // Node B

    Demo

  • Find Median from Data Stream

    Javascript (ES6)

    class RunningMedian {
  minHeap = new MinHeap();
  maxHeap = new MaxHeap();

  add = (val) => {
    maxHeap.add(val);
    minHeap.add(maxHeap.poll());
    if (maxHeap.size() < minHeap.size()) {
      maxHeap.add(minHeap.poll());
    }
  };

  median = () => {
    if (maxHeap.size() > minHeap.size()) {
      return maxHeap.peek();
    }
    return (minHeap.peek() + maxHeap.peek()) / 2;
  };
}

    Demo

    Java

    class MedianFinder {
 public PriorityQueue < Integer > maxHeap;
 public PriorityQueue < Integer > minHeap;

 /** initialize your data structure here. */
 public MedianFinder() {
  this.maxHeap = new PriorityQueue < > (Collections.reverseOrder());
  this.minHeap = new PriorityQueue < > ();
 }

 public void addNum(int num) {
  this.maxHeap.add(num);
  this.minHeap.add(this.maxHeap.remove());
  if (this.maxHeap.size() < this.minHeap.size()) {
   this.maxHeap.add(this.minHeap.remove());
  }
 }

 public double findMedian() {
  return this.maxHeap.size() > this.minHeap.size() ? this.maxHeap.peek() * 1.0 : (this.maxHeap.peek() + this.minHeap.peek()) * 0.5;
 }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

  • Merge Sorted Array

    /**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */

var merge = function(nums1, m, nums2, n) {
  let index = m + n - 1;
  m--;
  n--;
  while (m >= 0 && n >= 0) {
    if (nums1[m] >= nums2[n])
      nums1[index--] = nums1[m--];
    else
      nums1[index--] = nums2[n--];
  }
  while (index >= 0)
    nums1[index--] = m >= 0 ? nums1[m--] : nums2[n--];
};

const arr = [1, 3, 4, , , ];
merge(arr, 3, [1, 2, 4], 3);
console.log(arr);
// Output: [1, 1, 2, 3, 4, 4]

    Demo

  • Merge K Sorted Lists

    /**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */

var mergeKLists = function(lists) {
  if (!lists || lists.length === 0)
    return null;
  let last = lists.length - 1;
  while (last != 0) {
    let i = 0;
    let j = last;
    while (i < j) {
      lists[i] = mergeTwoLists(lists[i++], lists[j--]);
      if (i >= j)
        last = j;
    }
  }
  return lists[0];
};


var mergeTwoLists = function(a, b) {
  if (a == null)
    return b;
  if (b === null)
    return a;
  let result = a;
  if (a.val <= b.val) {
    result.next = mergeTwoLists(a.next, b);
  } else {
    result = b;
    result.next = mergeTwoLists(a, b.next);
  }
  return result;
};

    Demo

  • Merge Two Sorted Lists

    /**
* Definition for singly-linked list.
* function ListNode(val, next) {
*   this.val = (val===undefined ? 0 : val)
*   this.next = (next===undefined ? null : next)
* }
* / 
/*
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/

var mergeTwoLists = function(a, b) {
  if(a === null)
    return b;
  if(b === null)
    return a;
  let result = a;
  if(a.val <= b.val) {
    result.next = mergeTwoLists(a.next, b);
  } else {
    result = b;
    result.next = mergeTwoLists(a, b.next);
  }
  return result;
};

/// START TEST DATA ///
var a = {
  val: 1,
  next: {
         val: 2,
         next: {
                 val: 4,
                 next: null
                }
        }
      };

var b = {
         val: 1,
         next: {
                val: 3,
                next: {
                       val: 4,
                       next: null
                       }
                  }
          };
/// END TEST DATA ///

var answer = mergeTwoLists(a, b);
while (answer !== null) {
  console.log(answer.val);
  answer = answer.next;
}

// Output: 1 , 1, 2, 3, 4, 4

    Demo

  • Binary Tree Right Side View

    var root = {
   val: 1,
   left: {
           val: 2,
           left: null,
           right: {
                   val: 5,
                   left: null,
                   right: null
                  }
          },
  right: {
           val: 3,
           left: null,
           right: {
                   val: 4,
                   left: null,
                   right: null
                  }
          }
};
/*
  1
 /  \
2    3
 \    \
  5    4
*/

var node = function(node, depth) {
  this.node = node;
  this.depth = depth;
};

var rightSideView = function(root) {
  if (root === null)
    return [];
  var q = [];
  var ret = [];
  var level = 0;
  var prev;
  q.push(new node(root, 0));
  while (q.length) {
    var curr = q.shift();
    if (curr.depth > level) {
      ret.push(prev.node.val);
      level = curr.depth;
    }
    prev = curr;
    if (curr.node.left) {
      q.push(new node(curr.node.left, curr.depth + 1));
    }
    if (curr.node.right) {
      q.push(new node(curr.node.right, curr.depth + 1));
    }
  }
  ret.push(prev.node.val);
  return ret;
};

console.log(rightSideView(root));
// Output: [1, 3, 4]

    Demo