Category: interview

Categories
interview

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

Categories
interview

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

Categories
interview

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.

Categories
interview

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

Categories
interview

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)
Categories
interview

Smooth Animation

The following is a method to perform smooth animation of an element from left to right given the duration and distance. 60 frames per second (fps) is the approximate frame rate for this . In this example, the element is being animated from left to right at 60 fps for a duration of 2 seconds (2000 ms) and a distance of 100px.

Javascript (ES6)

const animate = (element, duration/*seconds*/, distance) => {
  let start;
  const durationMs = duration * 1000;
  const speed = distance / durationMs;
  const step = (timestamp) => {
    if (start === undefined)
      start = timestamp;
    const elapsed = timestamp - start; // milliseconds
    element.style.transform = 'translateX(' + Math.min(speed * elapsed, distance) + 'px)';
    if (elapsed < durationMs) { // Stop the animation after duration
      window.requestAnimationFrame(step);
    }
  }
  window.requestAnimationFrame(step);
}
animate(document.getElementById('child'), 1, 100);

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

Categories
interview

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)
 */
Categories
interview

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

Categories
interview

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

Categories
interview

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();
 */