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

Categories
interview

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

Categories
interview

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

Categories
interview

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

Categories
interview

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

Categories
interview

Continous Subarray Sum

/**
@param {number[]} nums
@param {number} k
@return {boolean}
*/
const checkSubarraySum = (nums, k) => {
  const map = { 0: -1};
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]; 
    if (k != 0)
      sum %= k;
    if (map[sum] >= -1) {
      if (i - map[sum] > 1)
        return true;
    } else
      map[sum] = i;
  }
  return false;
};
// Time Complexity O(n)
// Space Complexity O(n)

console.log(checkSubarraySum([23, 2, 4, 6, 7], 6));
// Output: true

/**
@param {number[]} nums
@param {number} k
@return {boolean}
*/
const checkSubarraySumBruteForce = (nums, k) => {
  for (var start = 0; start < nums.length - 1; start++) {
    var sum = nums[start];
    for (var end = start + 1; end < nums.length; end++) {
      sum += nums[end];
      if (sum === k || (k !== 0 && sum % k === 0))
        return true;
    }
  }
  return false;
};
// Time Complexity O(n2)
// Space Complexity O(1)

console.log(checkSubarraySumBruteForce([23, 2, 4, 6, 7], 6));
// Output: true

Demo

Categories
interview

Multiply Strings

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
  num1 = num1.split('').reverse().join('');
  num2 = num2.split('').reverse().join('');
  var result = [];
  for (let i = 0; i < num1.length + num2.length; i++) {
    result[i] = 0;
  }

  for (let i = 0; i < num1.length; i++) {
    for (let j = 0; j < num2.length; j++) {
      result[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
    }
  }

  var str = '';
  for (let i = 0; i < result.length; i++) {
    var curr = result[i] % 10;
    var carry = Math.floor(result[i] / 10);
    if (i < result.length - 1)
      result[i + 1] += carry;
    str = curr + str;
  }

  while (str.charAt(0) === '0' && str.length > 1) {
    var n = str.length;
    str = str.substring(1, n);
  }

  return str;
};

console.log(multiply('2', '3'));
// Ouput: "6"

// var multiply = function(num1, num2) {
//  num1 = parseInt(num1, 10);
//  num2 = parseInt(num2, 10);
//  return (num1*num2)+'';
// }

Demo

Categories
interview

Lowest Common Ancestor of a Binary Tree

/**
Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
/ /*
@param {TreeNode} root
@param {TreeNode} p
@param {TreeNode} q
@return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
  if (root === null)
    return root;
  if (root === p || root === q)
    return root;
  var left = lowestCommonAncestor(root.left, p, q);
  var right = lowestCommonAncestor(root.right, p, q);
  if (left !== null && right !== null)
    return root;
  return left === null ? right : left;
};
// if only one of the Nodes is present in the given Binary Tree, then it is returned,
// you can traverse through the returned Node and check if the other one is present.

Demo

Categories
interview

Number of subsets

For a given list of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K.

Example 1:

nums = [2, 4, 5, 7]
k = 8
Output: 5
Explanation: [2], [4], [2, 4], [2, 4, 5], [2, 5]

Code:

var nums = [2, 4, 5, 7];

var findNum = function(nums, k) {
  nums.sort((a, b) => a - b);
  var count = 0;
  var low = 0;
  var high = nums.length - 1;
  while (low <= high) {
    if (nums[low] + nums[high] > k) {
      high--;
    } else {
      // Total subsets for set of n =  2^n
      count += 1 << (high - low);
      low++;
    }
  }
  return count;
}

console.log(findNum(nums, 8));
// Runtime complexity O(nlogn)
// Output: 5

Demo

Categories
Uncategorized

Shortest Distance to a Character

class Solution {
    public int[] shortestToChar(String S, char C) {
        int n = S.length();
        int prev = Integer.MIN_VALUE/2;
        int[] store = new int[n];
        for(int i = 0; i < n; i++) {
            if(S.charAt(i) == C) {
                store[i] = 0;
                prev = i;
            }
            else 
                store[i] = i - prev; 
        }
        prev = Integer.MAX_VALUE/2;
        for(int i = n-1; i >= 0; i--) {
             if(S.charAt(i) == C)
                prev = i;
            else 
                store[i] = Math.min(store[i], prev - i); 
        }
        return store;
    }
}