Coding Interview Questions Set 2


For first 3 questions and answers please refer to  Coding Interview Questions Set 1.
Let's begin with set 2,

4)For a given binary tree find the depth/height of a binary tree.
Solution:

var depth= function(root) {
    if(root === undefined || root===null){
        return 0;
    }
    return Math.max(depth(root.left),depth(root.right)) + 1;
};

Logic:
Divide and conquer.

5)In a given array move all the 0 's to the end without disturbing order of non-zero elements. 
Solution:
var moveZeroes = function(nums) {     
    for(var i = nums.length;i--;){
        if(nums[i]===0){
            nums.splice(i,1)
            nums.push(0);
        }
    }
};

Logic:
Remove each 0 and add 0 at the end of the array.

6)Calculate the sum of 2 integers without using + and - operator.
Solution:
var add = function(a, b) {
    let carry;
    while(b) {
        carry = a & b;
        a ^= b;
        b = carry << 1;
    }
    return a;
};


Logic:
Example a=5 and b=1
The AND will only return 1 when both are 1
Step a)
& operator
101
001

001(that's 1 carry)

Step b)
^ operator
101
001

100(that's 4)

but 5+1 = 6, not four.
That's because we have a carry.
In binary, xor or ^ will add digits (but doesn't care about overflow/carry).
The ^ will return 1 when both are different
So a=4;

Step c)
Now we re-declare b as carry << 1, so it becomes 010 or 2,
i.e 001<<1=010

Again repeat step a,b, and c until b becomes 0.

step a) with updated values of a and b,
100
010

000(That's 0 carry)

Step b)
100
010

110 (That's 6)
So a=6;

Step c)
000<<1 =0;
So here b becomes 0;
We return value of a that is 6 as the answer.

I hope you like this article.
Please stay connected for coding interview questions set 3.
 
You can also follow me on Twitter or Linkedin for the latest updates.

Written By:

Saurabh Joshi

Comments

Popular Posts