Microsoft Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 1 vote

Find the max depth and min depth. The difference between these two numbers shouldn't be more than 1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a DFS. Whenever we are backtracking in the DFS maintain the node's height. So we'll encounter a leaf and note it's height as 1 then we go to it's parent do a DFS from there again noting the height it's right child. While backtracking to it's parent we know if the height of the two subtrees, so check if the property is held, if no report, if yes note the height again and continue.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Koha - How will you compute the max and min depth? What would be the cost of each?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use breadth first traverse starting from the root. Put {node, distance from root} into queue during traverse. Remember the max and min distance for leaves only. In the end, if max-min>1, the tree is not balanced. The time is 0(N) and the space is 0(N)

Comment hidden because of low score. Click to expand.
0
of 0 vote

int computeHeight(NODE* pNode)
{
if(!pNode)
return -1;
int heightLeft = computeHeight(pNode->pLeft);
int heightRight = computeHeight(pNode->pRight);
int heightNode = 1 + ((heightLeft > heightRight) ? heightLeft : heightRight);
return heightNode;
}

bool isBalanced(NODE* pNode)
{
if(!pNode)
return true;
if(!isBalanced(pNode->pLeft))
return false;
if(!isBalanced(pNode->pRight))
return false;
int heightLeft = computeHeight(pNode->pLeft);
int heightRight = computeHeight(pNode->pRight);
int heightDiff = heightLeft - heightRight;
if((heightDiff != 0) && (heightDiff != 1) && (heightDiff != -1))
return false;
return true;
}

Comment hidden because of low score. Click to expand.
0

Slight modification to above code related to performance issue.

Suppose the tree is not balanced at any point need not necessary to compute the remaining nodes height.

int computeHeight(NODE* pNode)
{
if(!pNode)
return -1;
int heightLeft = computeHeight(pNode->pLeft);
if(heightleft==-2) return -2; //added by venki
int heightRight = computeHeight(pNode->pRight);
if(heightright==-2) return -2; //added by venki
int heightDiff = heightLeft - heightRight; //added by venki
if((heightDiff != 0) && (heightDiff != 1) && (heightDiff != -1)) //added by venki
int heightNode = 1 + ((heightLeft > heightRight) ? heightLeft : heightRight);
return heightNode;
}

bool isBalanced(NODE* pNode)
{
if(!pNode)
return true;
if(!isBalanced(pNode->pLeft))
return false;
if(!isBalanced(pNode->pRight))
return false;
int heightLeft = computeHeight(pNode->pLeft);
int heightRight = computeHeight(pNode->pRight);
int heightDiff = heightLeft - heightRight;
if((heightDiff != 0) && (heightDiff != 1) && (heightDiff != -1))
return false;
return true;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Code for the khoa's solution

int maxDeptth(node *node){
if(node == NULL) return 0;
else
return(MAX(maxDepth(node->left),maxDepth(node->right))+1);
}

int minDepth(node *node){
if(node == NULL) return 0;
else
return(MIN(maxDepth(node->left),maxDepth(node->right))+1);
}

bool IsBalanced(node * node){
return (maxDepth(node) - minDepth(node) >1)

}

Comment hidden because of low score. Click to expand.
0

Yup! Good solution.

Comment hidden because of low score. Click to expand.
0

it does not say binary.

Comment hidden because of low score. Click to expand.
0

Check above code for Typos and Copy and Paste errors

...

Doc

Comment hidden because of low score. Click to expand.
0

niceeee

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a recursive solution:

bool isBalanced(Node* r)
{
if (r->left && r->right)
{
bool a = isBalanced(r->left);
bool b = isBalanced(r->right);

if (a && b)
return true;
return false;
}

if (r->left)
{
if (!r->left->left && !r->left->right)
return true;
return false;
}

if (r->right)
{
if (!r->right->left && !r->right->right)
return true;
return false;
}

return true;
}

Comment hidden because of low score. Click to expand.
0

looks good..

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool IsBalanced(node *root)
{

if(root == NULL)
return true;

if(!IsBalanced(root->left))
return false;

if(!IsBalanced(root->right))
return false;

int heightL = root->Left?root->left->height:0;
int heightR = root->Right?root->Right->height:0;

if(abs(heightL - heightR) > 1)
return false;

root->height = max(heightL,heightR) + 1;
return true;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBalancedInternal(node* root,int depth,int* maxDepth)
{
if (!root)
{
return true;
}
if (root->left == NULL && root->right == NULL)
{
if ( abs( depth - (*maxDepth) ) > 1)
{
return false;
}
if ( depth > *maxDepth)
{
*maxDepth = depth;
return true;
}
}

return (isBalancedInternal(root->left,depth + 1,maxDepth) &&
isBalancedInternal(root->right,depth + 1,maxDepth));

}
bool isBalanced(node* root)
{

int maxDepth = 0;
return isBalancedInternal(root,0,&maxDepth);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Vamsi

Your code has an error basically design issue.You are not checking if the left or the right subtrees are balanced.Maybe the left subtree is unbalanced but the heights of both the subtrees maybe same.Suppose, left subtree has leaf nodes at level 3 and 7,then height of left subtree would be 7.Lets say the height of the right subtree be 7 as well.So your code will give me that the tree is balanced as the heights of both the subtrees are same.But the answer is false.The tree is not balanced!!...see the loop hole in your code !!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Lost I am afraid you did not really understand what Vamsi is doing. in your example, if there is a leaf node at 3 and 7, then the max depth will be>=7 and the minimum depth will be <=3, and the difference is >=4, then it is not balanced. it does not only look at the height different between left and right subtree, it checks the difference between the leaf with the minimum and maximum depth, thus the solution is correct

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think Vamsi's solution has a problem with the minDepth implementation.
I think it should be
int minDepth(Tree* root)
{
if(!root) return 0;
if(!root->left||!root->right) return 0;
return(1+min(minDepth(root->left),minDepth(root->right));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry some modification
int mindDepth(Tree* root)
{
if(!root) return -1;
if(!root->left||!root->right) return 0;
return(1+min(minDepth(root->left),minDepth(root->right));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

khexa's solution is not correct

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool IsBalanced(node* root)
{
if(!root) return false;
int level=0, max=MIN_INT; min=MAX_INT;
DoIsBalanced(root,level,&max,&min);
if(max-min>1) return false;
return true;
}

DoIsBalance(node* root,int level,int max,int min)
{
if(!root)
{
if(level>max) max=level;
if(level<min) min=level;
return;
}
DoIsBalance(root->left,level+1,max,min);
DoIsBalance(root->right,level+1,max,min);
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.