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
interview

Verifying an Alien Dictionary (Js)

/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
const isAlienSorted = function(words, order) {
  
const isInOrder = {};
  for (let i = 0; i < order.length; i++) {
    isInOrder[order.charAt(i)] = i;
  }

  search: for (let i = 0; i < words.length - 1; i++) {
    const wordBefore = words[i];
    const wordAfter = words[i + 1];
    const minWordLen = Math.min(wordBefore.length, wordAfter.length);
    for (let k = 0; k < minWordLen; k++) {
      if (wordBefore.charAt(k) !== wordAfter.charAt(k)) {
        if (isInOrder[wordBefore.charAt(k)] > isInOrder[wordAfter.charAt(k)]) {
          return false;
          }
        continue search;
      }
    }
   if (wordBefore.length > wordAfter.length) {
     return false;
     }
  }
  return true
};

console.log(isAlienSorted(['ace', 'ad'], 'abcdefghijklmnopqrstuv')); // true

Demo

Categories
interview

Filter objects (ES6)

// There could potentially be more than 3 keys in the object below.
const items = [{
    color: 'red',
    type: 'tv',
    age: 18
  },
  {
    color: 'silver',
    type: 'phone',
    age: 20
  },
  {
    color: 'yellow',
    type: 'truck',
    age: 10
  },
  {
    color: 'blue',
    type: 'shirt',
    age: 5
  },
];

const excludes = [{
    k: 'color',
    v: 'silver'
  },
  {
    k: 'type',
    v: 'tv'
  },
  {
    k: 'color',
    v: 'red'
  }
];

// SOLUTION

const excludesMap = excludes.reduce((acc, curr) => {
  (acc[curr.k] || (acc[curr.k] = {}))[curr.v] = true;
  return acc;
}, {});

/*
color: red: true,
       green: true ... 
type: tv: true
       truck: true, ...

*/

const exclude = (items, excludes) => items.filter(item => {
  for (const [key, value] of Object.entries(item)) {
   if(excludesMap[key]?.[value])
      return false;
  }
  return true;
});

console.log(exclude(items, excludes));
/*
  [{
    age: 10,
    color: "yellow",
    type: "truck"
  }, {
    age: 5,
    color: "blue",
    type: "shirt"
  }]
*/

Demo