Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

Psuedocode for Predecessor of Tree

Tree_Maximum(node)
{
	while (node != null)
	{
		node = node.right
	}

	return node
}

Tree_Predecessor(x)
{
	if (x.left != null)
		return Tree_Maximum(x.left);

	y = x.p	// p, parent of x

	while (y != null && x.left == y)
	{
		x = y;
		y = y.p
	}
	return x;
}

- Piyush March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question doesn't specify, but I'll assume that you receive a pointer to the root of the BST and a number whose predecessor wants to be found.

The idea is to try and search for the right-most child of the left branch of the node containing the given number (you'll have to search for that node first), if the node doesn't have a left branch, then you go up in the tree until you find the first parent node with smaller or equal value of the number. If no parent node meets that condition then there is no predecessor number which may happen iff the node containing the number is the left-most node of the tree.

Implementation is an iterative approach since recursive one needs to handle a few extra cases.

bool try_get_predecessor(TreeNode* root, int number, int& predecessor)
{
    if (root == NULL)
    	return false;

    stack<TreeNode*> previous;
    TreeNode* current = root;

    while (current != NULL)
    {
        if (current->value == number)
        {
            if (current->left == NULL)
            {
                if (previous.empty())
    				return false;

                TreeNode* parent = previous.top();
                while (!previous.empty() && parent->value > number)
                {
                    previous.pop();
                    parent = previous.top();
                }

                if (parent->value > number)
    				return false;

                return parent->value;
            }
            else
            {
                TreeNode* largest_pre = current->left;
                TreeNode* next_pre = largest_pre;
                while (next_pre != NULL)
                {
                    largest_pre = next_pre;
                    next_pre = next_pre->right;
                }

                return largest_pre->value;
            }
        }

        previous.push(current);

        if (current->value > number)
            current = current->left;
        else
            current = current->right;
    }

    return false;
}

- meh March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

typo:

Instead of

return parent->value;

It should be

predecessor = parent->value;
return false;

- meh March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

typo of typo (shit):

Should return true.

- meh March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Case 1: Node is left most node of BST.
Return NULL
Case 2: Node has left sub tree.
In this case it is Maximum Node in the Left Sub-Tree. i.e., the right most node in the left sub-tree
would be the in-order predecessor.
Case 3: Node has no left sub-tree.
In this case in-order predecessor will be the node where we took the latest right turn.

C++ version:

NODE * find_predecessor(NODE * root, NODE * node)
{
    NODE * temp = root, *parent = NULL;
    if (node->left != NULL){  // Max of the Left Sub-Tree
       temp = node->left;
       while (temp->right != NULL) 
			temp = temp->right;
       return temp;
    }
 
    while ( temp != node ){ // Find the Ancestor where we took latest Right Turn
       if (node->data < temp->data){
         temp = temp->left;  
       }
       else {
         parent = temp;
         temp = temp->right;
       }
    }
    return parent;
}

- R@M3$H.N March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is wherever we parse the right subtree while searching thats the in order predecessor. And whenever we parse the left subtree we have to remember for which parent we parsed the right subtree.

node = root
pre = NULL
found = False
while True:
	if el < node.value:
		node = node.left
		continue
	else if el > node.value:
		pre = node
		node = node.right
		continue
	else if node == NULL:
break
else:
		found = True
		break
if found == True:
	if pre != NULL:
		print pre
	else:
		print 'no predecessor exists'
else:
	print 'element not found'

Time complexity: O(logn)
Space complexity: O(1)

- kr.neerav March 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

seems right, excellent

- samuel March 26, 2014 | 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