Author: Shiva Charan Devabhaktuni

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;
    }
}
Categories
Uncategorized

Largest 1-Bordered Square

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int[][] h = new int[grid.length][grid[0].length];
        int[][] v = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    h[i][j] = 0;
                    v[i][j] = 0;
                } else {
                    h[i][j] = j > 0 ? h[i][j - 1] + 1 : 1;
                    v[i][j] = i > 0 ? v[i - 1][j] + 1 : 1;
                }
            }
        }
        int max = 0;
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                int small = Math.min(v[i][j], h[i][j]);
                while (small > max) {
                    if (v[i][j + 1 - small] >= small && h[i + 1 - small][j] >= small) {
                        max = Math.max(max, small);
                    }
                    small--;
                }
            }
        }
        return max * max;
    }
}
Categories
Uncategorized

Longest Common Prefix using Binary Search (ES6)

const arr = ["hello", "helloworld", "helloworld1"];

const allContains = (inp, start, end) => {
for(let i=0; i<inp.length; i++) {
	for(let j=start; j<=end; j++) {
		if(inp[0].charAt(j)!==inp[i].charAt(j)) {
			return false;
    	}
	}
}
return true;
};

const findSubstring = (inp) => {
let min = Number.MAX_VALUE;
  for(let i=0; i<inp.length; i++) {
  	 min = Math.min(inp[i].length, min);
  }
let low = 0, high = min-1;
let prefix = '';
 while(low<=high) {
 	let mid = low + Math.round((high-low)/2);
  	if(allContains(inp, low, mid)) {
   		prefix += inp[0].substring(low, mid+1);
  		low = mid+1;
  	} else
  	high = mid-1;
		}
return prefix;
};

console.log(findSubstring(arr));

// Output: hello
// Runtime complexity: O(m*log(n)) 
// m- length of input array or list and n is length of 
// smallest string.

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