Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

traverse the binary tree and store elements in array. (n)
sort the array using merge sort. (nlogn)
build the bst using the array.
complexity nlogn.

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

Why sort the array? If you're going to make a balanced tree, you can skip that step. If it's just a BST and you want to make sure it's balanced even without balancing mechanisms, then sorting it would be appropriate, of course.

- eugene.yarovoi November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we have to change the same tree to the BST (clearly mentioned) , not to store the values some where else and create a new tree

- RJ65 November 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Okay, so after a lot of thinking, I guess I could finally crack it ..

The idea is ... if we have two BSTs, we can merge them in-place, by just changing the pointers.

A tree with a single node is a BST.

1) Travel to the left most leaf node, keeping a pointer to its parent. make this node as new root of the BST that we are going to build. and set parent->left = null;

We can take any leaf node. I'm not checking of diff cases, where say is tree is right skewed. If someone can take the initiative of adding that code .. I'l be grateful :-)

node* getNewRoot(node* root){
node* parent = root;
node* newRoot = root->left;
while(!((newRoot->left==null)&&(newRoot->right ==null))) {
parent = newRoot;
newRoot = newRoot->left;
}

parent->left = null;
return newRoot;
}


2) Traverse the remaining binary tree in port-order. and keep inserting nodes in the BST with newRoot as root. The key is, after you insert a node in the BST, set its left and right pointers to null, so that this node is 'removed' from the old tree.

void convertIntoBST (node* curr){
if(!curr)
return;

convertIntoBST(curr->left);
convertIntoBST(curr->right);
InsertintoBST(newRoot, curr);
curr->left=null;
curr->right=null;
}


void InsertIntoBST(node* root, node* curr){
while(!((root->left == null)&&(root->right == null))) //iterate until root is not leaf node
{

if(root->val > curr->val)
root = root->left;

else
root = root->right;
}

if(root->val > curr->val)
root->left = curr;
else
root->right = curr;

}

This converts the same binary tree into a BST, by changing the pointers. No new node is created.
How ever time complexity is larger than O(n). Can someone tell what ?

- P November 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tree with single node is NOT BST... for any node left data
will be smaller and right data will be greater than the
node data, this is BST.
Binary Tree means, every node will have at most 2 nodes but
that can be greater or smaller.

- Anonymous November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hmmm okay, I might have messed up with the terminologies, but the solution still holds good ..

- P November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(n2) worst case

- cant_think_ November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any better solutions? Bcoz this takes O(n) space complexity

- Rigel November 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what time complexicity interviewer was looking for? and space is O(1).

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

I also gave it a lot of thought, the soultion is rather very simple. just pick a node from original tree and keep on detaching nodes from first tree and adding to new BST. Though it is O(n2) worst case

- cant_think_ November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if we do it on the principle ok heapify , then also worst case in O(n2)

- cant_think_ November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert the tree into a doubly link list , sort the link list and covert it back into a BST . Order(nlogn)

- RJ65 November 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If i just think on this for 2 minutes this is a classic POST ORDER problem: THis should work here.

1) Make a recursive function int Find_MAX(tree* p,int x, bool op).
2) Make a recursive function int Find_MIN(tree* p,int x, bool opration).
3) Pass node val to Find_MAX(p->left, p->val) and inside find_max check if input x is less than current node's val. If yes send it furthur to Find Max. Else keep retval as x for now.
4) after getting MAX from Left subtree find Min from right subtree.
5) finally compare min from right subtree and retval from prev and return the bigger value if this operation was to a left child(can be found using bool opration) else return smaller value.
6) Make node as return value

- ProudAmerican December 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i didn't understand your logic. Please elaborate.

- Anonymous January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i didn't understand your logic. Please elaborate.

- Anonymous January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i didn't understand your logic. Please elaborate.

- anonymous January 12, 2012 | 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