Microsoft Interview Question for SDE1s


Country: United States
Interview Type: In-Person




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

To fi nd the postorder predecessor of node u:
If u has a right child, r, then pred(u) is r.
Otherwise If u has a left child, l, then pred(u) is l.
Otherwise if u has a left sibling, ls, then pred(u) is ls
Otherwise if u has an ancestor, v, which is a right child and has a left sibling,
vls, then pred(u) is vls
Otherwise, pred(u) is unde fined.

- Prasanna May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution --
two points
a) "Otherwise if u has a left sibling, ls, then pred(u) is ls" : -- In typical scenario, a Binary Tree doesn't keep information about their sibling, so this is an extra information the BTree nodes has to keep.
b) "Otherwise if u has an ancestor, v, which is a right child and has a left sibling, vls, then pred(u) is vls " -- this needs a O(N) processing time.

However, your first 2 points actually cover all the nodes except the leaf nodes. So, perhaps we should first do the first 2 check and if we found that the node is a Leaf node we will do a O(N) post order tree traversal.
what do you think ?

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

Last two points are not correct. If by sibling you mean the node that is in same level and comes before this node in level order traversal consider this tree

12
                /     \
              10     11
             /      \
          6         9
       /     \           \
    2      5            8
    /      /  \              \
  1     3    4             7

Here sibling of node 3 is 1. But pred is 2. I think for any target node, if v is a ancestor which has a left child, lc, then lc will be the pred

- Sugarcane_farmer May 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

The simplest way is to save the predecessor in a variable, and then update it while traversing the BT with post-order.
1) set predecessor = null
2) traverse BT with post-order
3) if current_node == input_node {
return predecessor;
} else {
predecessor = current_node
}
4) goto step 3)

- SkyClouds May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution works for the given problem, but if I say the given tree is balanced, your algorithm will run in O(n) time while Prasanna's algorithm will run in O(logn).

- Epic_coder May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Epic_coder, I think you should say binary search tree :)

- SkyClouds May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Epic_coder i think there will be a logn extra space required for storing the pointers to parents of each node in Prasanna's algo.

- Ashish May 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome simple logic dude :)

- coder June 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if input node is "root" of a tree, wont you return "null" as you wont even traverse tree

- confused_banda December 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@epic_coder instead of storing pointers to parent v can use a recursive soln which 'll be storing pointers in in-built stack . but again it requires o(log n) space for recursion but code will look simple with recursion.

- poorvisha April 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Logic
1. if non leaf node and it has a right child return right child as pred
2. if non leaf node and it has a left child but no right child return left child as pred
3. if leaf node, iterate from root and track current pred at that instance
3.1 if in a root and target is the right child then a left child is the pred for the right child.
3.2 go to left sub-tree, current is still the current pred
3.3 go to right sub-tree, root-left is the current current pred for the right sub-tree
3.4 if the target is root-left, return current
(Note : 3.4 can be between 3.1 and 3.2. I have put it at the last to have a better understanding and because of which you might go few extra iterations :) )

(struct tree *) pred(struct tree *head, struct tree *target) {
    if (target == head) 
        return NULL;
    if (target->right != NULL) 
        return target->right;
    else if (target->left != NULL) 
        return target->left;
    else 
        return find_pred_recurse(head,NULL,target);
}

(struct tree*) find_pred_recurse(struct tree *head, struct tree *current, struct tree*target) {
    if ( head != NULL) {
        if (head->right == target)
            return head->left;
        find_pred_recurse(head->left,current,target);
        find_pred_recurse(head->right,head->left,target);
        if (root->left == target)
            return current;
    }
}

- Time Pass June 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I liked your approach. but the code don't work for 2 reasons.
1. if (head->right == target)
return head->left; // head left is the right value to return but due to recursion when it pops the oldest stat from stack, you will lose the value and end up returning wrong answer (ancestor node). check my code below for this fix.

2. construct this tree and check it. tree input(7,4,10,5,3,8,14,9,13,16) where its post-order traversal out put is (3,5,4,9,8,13,16,14,10,7). try to get the predecessor of 9. your approach will fail. so does mine.

* Your function signature ???

void pred(node *root, node * &pre, node *nd){
		if (root == NULL)
			return;
		if (nd->right != NULL){
			pre = nd->right;
			return;
		}
		if (nd->left != NULL){
			pre = nd->left;
			return;
		}
		getPostorder(root, NULL, nd, pre);
	}
	void find_pred_recurse(node *root, node *parent, node *nd, node *&pre){
		if (root != NULL){
			if (root->right == nd){
				pre = root->left;
				return;
			}
			find_pred_recurse(root->left, NULL, nd, pre);
			find_pred_recurse(root->right, root->left, nd, pre);
			if (root->left == nd){
                                pre = parent
				return;
}
		}
	}

- solxget May 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

- Solomon January 19, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

- Solomon January 19, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

- Solomon January 19, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

do Preorder traversal.
if found key{
if node have right child, right child is Post Pred, if only left child, postPrd = left child.
if node is leaf node, just return PostPred variable is holding the right Postpredcessor from the second recursion call which below
}
if(value < root->data)
recursively call the left sub tree
else if (value > root->data){
check if root have left child, if so set postorderPred to root->left.
}

- Solomon January 19, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Prasanna: Nice solution..Can you also provide code with this?

- Anonymous May 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the code for Prasanna's algorithm

Node* par_array[100];/*array stores the parents of the node in the call stack which takes up log N space complexity, for simplicity here I am not using dynamic array*/
Node* pred(Node* curr, int item, int level=0){
	
	if(curr==NULL) return NULL;

	else{
		if(curr->data == item){
			if(curr->right!=NULL)		return curr->right;

			else if(curr->left!=NULL)	return curr->left;

			else if(!par_array.isEmpty()){
				Node* par;
				while(level>=0){
					par = par_array[level-1];
					if(par->left!=NULL) return par->left;
				}
				if(level < 0) return NULL;
			}

			else 	return NULL;
		}
		
		return pred(curr->left, item, level+1);
		return pred(curr->right, item, level+1);
	}
}

- Ashish May 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ashish and others, please provide code for getting the parents of the item node stored in an array, par_array. Thanks.

- Sriramulu Appana May 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* postOrderPred(node* root,int val,int *found){
if(!root) return NULL;
if(val<root->data)
return postOrderPred(root->left,val,found);
if(val>root->data){
node* t;
if(t=postOrderPred(root->right,val,found))
return t;
if(*found && root->left)
return root->left;
}
else{
*found=1;
if(root->right)
return root->right;
if(root->left)
return root->left;
}
return NULL;
}

- Priyanka June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple straightforward code using recursion. However, it could be become tricky if interviewer only wants iterative code

void postorder(TreeNode* root, TreeNode* key, TreeNode* ans, TreeNode* prev)
{
    if (root != NULL)
    {
            postorder(root->left, key, prev, ans);
            postorder(root->right, key, prev, ans);
            if (root == key) { ans = prev; return ; }
            else { prev = root ; } 
    }
}
TreeNode* precessor(TreeNode* node, TreeNode* key)
{
      TreeNode* ans(NULL), prev(NULL);
       predecessor(node, key, ans, prev);
       return ans;
}

- Anonymous July 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

signature for postorder is wrong

void postorder(TreeNode* root, TreeNode* key, TreeNode*& ans, TreeNode*& prev) ;

- Anonymous July 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

PBTree GetPostOrderPredecessor(PBTree pRoot, PBTree pNode)
{
    PBTree pPred = NULL;
    PBTree pRightSubtree = NULL;
    CStack<PBTree> stack;
    bool fFound = false;

    if (pRoot && pNode)
    {
        if (pNode->Right)
        {
            pPred = pNode->Right;
        }
        else
        {
            if (pNode->Left)
            {
                pPred = pNode->Left;
            }
            else
            {
                // complex case for leaf
                stack.Push(pRoot);

                while (!stack.IsEmpty())
                {
                    while (pRoot->Left)
                    {
                        stack.Push(pRoot->Left);
                        pRoot = pRoot->Left;
                    }

                    while (!stack.IsEmpty())
                    {
                        pRoot = stack.Pop();

                        if (pRoot->Right != NULL && pRoot->Right != pRightSubtree)
                        {
                            stack.Push(pRoot);
                            stack.Push(pRoot->Right);
                            pRoot = pRoot->Right;
                        }
                        else
                        {
                            if (pRoot != pNode)
                            {
                                pPred = pRoot;
                            }
                            else
                            {
                                fFound = true;
                                break;
                            }
                            pRightSubtree = pRoot;
                        }
                    }

                    if (fFound)
                    {
                        break;
                    }
                }
            }
        }
    }

    return pPred;
}

- AK November 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void pred (node*node)
{
if (node==NULL)
return ;

int old=node->data;
pred(node->left);
pred(node->right);
if(node->data==inputdata)
cout<<old;
}

- ourjay June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Post-order predecessor is nothing but its left child. (last post order visited element in left sub tree)

struct BinaryTree *PostorderPredecessor(struct BinaryTree *node) {
return node->left
}

- pirate May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No. right children of the given node - if right sub tree exist. otherwise left node is the answer.

- Vin May 05, 2013 | Flag


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