Microsoft Interview Question for Program Managers






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

Here's the complete code

int maxDepth(Tree* root)
{
if (root == NULL) return 0;
else
{
int ldepth = maxDepth(root->left) + 1;
int rDepth = maxDEpth(root->right) + 1;

return ((ldepth>rDepth) ? ldepth:rdepth);
}
}

int minDepth(Tree* root)
{
if (root == NULL) return 0;
else
{
int ldepth = minDepth(root->left) + 1;
int rDepth = minDEpth(root->right) + 1;

return ((ldepth>rDepth) ? rdepth:ldepth);
}
}
bool isDiffMoreThanTwo(Tree* root)
{
return ((maxDepth(root) - minDepth(root)) >=2 );
}

- Amit Priyadarshi August 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the algorithm can be modified a little bit to be interrupted as soon as we find that any (Min + 1) < Max.

- Aleksey.M November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple DFS with keeping min and max lengths.

- gevorgk May 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Firstly, we need to enlist all the leaf nodes and their levels in the tree. In order to do this, do a Level order Traversal on the Tree (using queue) and store all leaf node and their levels into a 2d array (by verifying if the node doesn't have child nodes and maintaining a level variable in the recursive level order traversal).
2. Now that we have 2d array of all leaf nodes and its level, we need to find all array elements, wherein difference of levels is 2 or more. O(n square) time complexity we can find all nodes differing by 2 or more. Any better approach, please share.

The level order traversal in binary tree can be brought about by

void LevelOrderTraversal(Tree myBinTree) {
  Queue myQ = new Queue();
  Tree myTree = myBinTree;
  int level = 0;
  while(myTree != null) {
    if(myTree.leftChild == null && myTree.rightChild == null)
      Insert <myTree, level> into the 2d array
    if(myTree.leftChild != null)
      myQ.add(myTree.leftChild);
    if(myTree.rightChild != null)
      myQ.add(myTree.rightChild);
    myTree = q.delete(myTree); //deletes the current node and returns the next node in Q
    level++;
}

//Have to code the algo to find the nodes differing by >1 levels.

- cuppanomics May 11, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You just making simple things complicated.
Do DFS of tree calucating minimum and maximum depth in parralel. Stop when max - min >= 2.
Solution is O(n) (well, we can do it in n^2, n^3 and so on :) )

- gevorgk May 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats Right !!

- Anonymous May 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@gevorgk: "Depth First Search of Binary tree"... Can you please elaborate on which kind of traversal do you intend to do. A pseudo code/algo would be great.. Didn't actually get it completely...
And how are you enlisting all the leaf nodes which differ by >1 level difference?

- cuppanomics May 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

seee below...

- gevorgk May 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

gevorgk,
Depth first search won't work. because for nodes which has only one child min-depth will be that from no-child side but there is no leaf there.
I think a good approach would be to traverse Breadth first and keep track of levels by maintaining child count for a level added in queue. check each node while popping it whether it's leaf note down max and min levels of leafs.
you can quit the traversal in middle if question is to find out whether a certain difference of depth for leaves exist in tree

- vishal Sharma May 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ok, let me exlplain better. Question says wether there a ANY 2 leaf nodes, which differ by more than 1 level.
We will find the leaf with Min depth, and leaf with max depth. If the deifference is more than 1 - it means that we have at list one such pair. If difference is less than or equal to 1 - it means than there will be no such pairs, because the difference between min and max is largest one.

- gevorgk May 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys, How about this. We use a global variable array of size two to keep tracking of min and max depth. Then we recursively DFS this Binary tree (don't forget to count the depth). When we hit the leaf node update min max can check max-min >=2. When it does flag the boolean so that we can eliminate unnecessary search. Then it O(N) in time with a use of O(2) array.

int depth[] = {0,0}; //global variable O(2)

bool check_leaf(Node &n_,int dep)
{
//base case
if(n_.Left == NULL && n_Right == NULL)
{
if(dep > depth[0])
depth[0] = dep;
else if(dep < depth[1])
depth[1] = dep;
if(depth[0] - depth[1] >= 2)
return true;
else
return false;
}else
{
if(n_.Left != NULL) //Not a leaf node
if(check_leaf(n_.left,dep++))
return true; //stop unnecessary search
if(n_.Right != NULL) //Not a leaf node
if(check_leaf(n_.left,dep++));
return true; //stop unnecessary search
return false;
}
}

- saimok May 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another idea is to find the height of the left tree, find the height of the right tree. If the difference is more than 1, we return an error. The pseudo code will be some thing of this sort.

// Function return -1 if the difference is more than 1 level
// Function returns height of the tree other wise
// Assumptions : a properly constructed binary tree

int height(struct node** head)
{
// If head is equal to 0 return 0
//else t1 holds the height of the left tree t2 holds the height of the right tree
// if either of them is -1 that means some where down below there exits a sub tree with difference of more than 1 level. return -1
// if the difference is 0 or 1. then return the max height between either of the sub trees + 1
// else if the difference is 2 , return -1
}

- abhimanipal May 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxormin (int a, int b, int choice)
{
if (choice==0) return (a>b)?a:b;
if (choice==1) return (a<b)?a:b;
}

void height(node *root , int choice)
{
int maxht, minht;
if(root==NULL) return 0;

maxht= 1+maxormin(height(root->rlink),height(root->llink),0);
minht = 1+maxormin(height(root->rlink),height(root->llink),1)

if(maxht-minht > 1)
{
printf("yes > 1");
exit(0);
}
}

- Anonymous May 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The exit condition in function height should be if(root->llink==NULL && root->rlink==NULL) return 0.

- dullboy July 09, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private void TraverseWithHeight (Node* t, int * min, int * max, int * height)
{
if(t == null) return;
if(t->left == NULL && t->Right == null)
{
If(height < min) min = height;
If(height > max) max = height;
Height --;
return; //leaf
}
Else
{
Height ++;
if (t->left != NULL)
TraverseWithHeight( t->left , min, max, height);
else
TraverseWithHeight( t->right , min, max, height);

}
}

- Qhu July 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cant we use hashing???
we`ll use a single dimensional array and use the hash value of the node as index..
in the array store the height of the node.
then it just is matter of finding 2 indices with diff greater than 1.
can be done in o(n) time and o(n) space??

- Anonymous August 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bool tree_diff_level(node *root)
{

Min = Min_height(root);
Max = Max_height(root);

If(max > min)
Return(true);
Else
Return(false);


}
Min_height(node *root)
{

If(root == NULL)
Return(0);
Return(min(Min_heigh(root->left), Min_height (root->right)),+1);

}


Max_height(node *root)
{

If(root == NULL)
Return(0);
Return(max(Max_heigh(root->left), Max_height (root->right)),+1);

}

- nagpal_dce August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

excellent

- acid November 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brilliant...:)

- KK August 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int checkDepth (Node *node)
{
    if (node == 0)
        return 0;
    
    int left_len, right_len, difference;
    left_len = right_len = difference = 0;

    left_len = checkDepth (node->left);
    right_len = checkDepth (node->right);

    difference = abs (left_len - right_len);
    if (difference > 1)
    {
        printf ("The tree has a difference of more than one");
        exit (0);
    }
    else
        return (MAX(left_len, right_len)+1);
}

- Siraj December 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean check(Node root){
      return check(root,0) <= 1;
}

private static int check(Node node,int level){
      if(node == null)
           return level;

      if(node.left != null && node.right != null)
           return level;

      int left = check(node.left,level+1);
      int right = check(node.right,level+1);

      return Math.abs(left-right); 
}

- Anonymous March 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean check(Node root){
      return check(root,0) <= 1;
}

private static int check(Node node,int level){
      if(node == null)
           return level;
      if(node.left == null && node.right == null)
           return level;
      int left = check(node.left,level+1);
      int right = check(node.right,level+1);

      return Math.abs(left-right); 
}

- Anonymous March 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse each node using BFS
If CurrentNode.HasChildren() == false then // leaf node
	Add_Node_To_Array_After_Level_Check(CurrentNode)
End If
Print all elements in the NodeList as they have a level difference more than 1	
	
function Add_Node_To_Array_After_Level_Check(Node)
	{
	for(index = NodeList.Length-1 to 0)
		{
			if(Node.Level - NodeList[index].Level>1)
			{
				NodeList.Add(Node);
				break;
			}
		}

}

- supratim.sengupta October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done in Scala easily:

object scratchie2 {
  class Tree(val left: Tree, val right: Tree)

  val root1 = new Tree(null, null)                //> root1  : com.test.scratchie2.Tree = com.test.scratchie2$Tree@5efd2ebd
  val root2 = new Tree(new Tree(null, null), null)//> root2  : com.test.scratchie2.Tree = com.test.scratchie2$Tree@5858ba4b
  val root = new Tree(new Tree(null, null), new Tree(null, new Tree(new Tree(null, null), null)))
                                                  //> root  : com.test.scratchie2.Tree = com.test.scratchie2$Tree@292ebf3d
  def isBalanced(tree: Tree): Boolean = {
    if (tree.left == null && tree.right == null)
      true
    else if (tree.left != null && tree.right != null) {
      isBalanced(tree.left) && isBalanced(tree.right)
    } else if (tree.left != null && tree.right == null) {
      tree.left.left == null && tree.left.right == null
    } else {
      tree.right.left == null && tree.right.right == null
    }

  }                                               //> isBalanced: (tree: com.test.scratchie2.Tree)Boolean

	isBalanced(root1)                         //> res0: Boolean = true
	isBalanced(root2)                         //> res1: Boolean = true
  isBalanced(root)                                //> res2: Boolean = false

}

- Zinger December 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is just the code, use it in a worksheet or a class:

object scratchie2 {
  class Tree(val left: Tree, val right: Tree)

  def isBalanced(tree: Tree): Boolean = {
    if (tree.left == null && tree.right == null)
      true
    else if (tree.left != null && tree.right != null) {
      isBalanced(tree.left) && isBalanced(tree.right)
    } else if (tree.left != null && tree.right == null) {
      tree.left.left == null && tree.left.right == null
    } else {
      tree.right.left == null && tree.right.right == null
    }

  }                                               
}

- Zinger December 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do level order traversal - Check when encounter a leaf - Maintain min and max Leaf node level

O(n) time

- Gaurav April 28, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More