Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

for BST:
- Do the inorder traversal on both the trees.
- This will yield sorted sequence
- compare the elements.

- Ran January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ran
i think to compare the values we need to store the value in some array (space required is 2N)........in BST ..........am i correct ????
and for binary trees hash the values of one tree and check for other

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

- We can keep a flag store/compare, so the space required is N
* for the first tree (flag is 'store') we can store the elements in an array
* for the second tree (flag is 'compare') we can just compare with the stored elements

- Yes, for Binary tree we can hash the values.

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

2 different BSTs can have the same inorder ourput.
You'll have to compare the structure explicitly.
Recursively would be easier.

- kill February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

I am assuming two trees are same if all the nodes are same with same left/right childs.

Now start with root of both.
Compare roots IF equal, compare left and right and do this recursively.

boolean isSame(Node root1, Node root2){
    if( (root1==null && root2!=null) || (root2==null && root1!=null))
        return false;
   if(root1 == null && root2 == null)
        return true;
if(root1.data == root2.data)
    return(isSame(root1.left,root2.left) && isSame( root1.right,root.right));

   return false;
}

- loveCoding January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

whistle.

- bdeesh February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@bdeesh what is that?

- loveCoding February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

kudos.

- bdeesh February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Two trees could give the same inorder traversal and still be not identical. Read up on "Tree rotation".

- Ganesh February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Combining one of Pre-Order & Post-Order Traversal, with In-Order traversal produces a unique tree.

In-order traversal of any BST with same elements will always return same sorted sequence of elements (does not matter what is the construction of tree)

So, with BST we need any one of Pre-Order & Post-Order traversal (In-Order traversal is implicitly those elements in sorted manner)

However, with a binary tree, we would need anyone of In-order & post-order traversal, and In-order traversal.

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

I agree with you. we cannot determine a tree structure unique only using inorder. we need to combine pre-order/ post-order with in-order to produce a unique tree.

In order to solve the problem we need to store inorder sequence in a array and then preorder/postorder in one more array. Then compare both these arrays against second tree.

time complexity would be O(n).
but space complexity would be O(2n).

- phoenix October 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

do an in order traversal comparing the vale of key as well depth of key. depth will tel difference in structure and value will tel difference in numbers

- V February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The first solution is good but it requires extra space for the result of inorder traversal. If the nodes in the tree has a link to their parent, then we can do this in O(N) time and O(1) space. It should be asked from interviewer.

- amshali February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you're allowed extra space, couldn't you just add each node value of the first tree to a hash map? You can add it first with boolean value false, and then with the second tree, you can change them to true as you're traversing it. If you find an element that is not in the hash( or find that a number has been repeated) you can break and return false. If the tree traversal is completed, then you can check the hash to see if any of the values in the hash are still mapped to false. The time complexity should be O(n)...this should work if the given tree isn't a BST as well

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

[EDIT] Wouldn't track duplicates, but you can use count instead of boolean if thats the only issue. thoughts anyone?

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

[EDIT] Wouldn't track duplicates, but you can use count instead of boolean if thats the only issue. thoughts anyone?

- Anonymous March 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

bool IsStructureSame(node* root1,node* root2)
{
bool bIsSame = false;
if(root1 != nullptr && root2 != nullptr)
{
if(root1->data == root2->data)
{
if(IsStructureSame(root1->pLeft,root2->pLeft))
{
if(IsStructureSame(root1->pRight,root2->pRight))
bIsSame = true;
}
}
}
else if(root1 == nullptr && root2 == nullptr)
bIsSame = true;
return bIsSame;
}

- Anonymous January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 vote

The In-order and post-order of the two trees should be identical. Otherwise, they are NOT identical. Both algorithms are O(N) where N is the size of the BST.

- Masoud January 29, 2012 | 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