Amazon Interview Question for Software Engineer / Developers


Country: India




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

Case 1: If the original root itself is choosen as the root and picked up, then the tree remains binary
Case 2: Otherwise, the original root will have one child. Internal nodes with k children become nodes with k+1 children, where 1<=k<=2. Leaf nodes will have zero or one(in case a leaf is picked as the root) children.

- Murali Mohan January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Case 2 could rather be split into case 2 and case 3 for a clearer exposition.

Case 2: If an internal node is chosen as a root, the original root will have one child. The nternal node chosen to be the root will have one more child than before. Leaf nodes will have zero children

Case 3: If a leaf node is chosen as a root, the original root will have one child. The chosen leaf node will have one child and all other leaf nodes have 0 children. All internal nodes will have the same number of children as before.

- Murali Mohan January 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

it would be a splay tree its like we are accessing a node that will become root and remaining tree will be adjusted as a binary tree by single or double rotation

- Vaibhavs January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the rotations would come into play only if the resulting tree will have to be balanced again to retain any properties. If, for instance, there is a constraint that the resulting tree must be a valid binary tree, then rotations will be required in order to ensure than every node has at most 2 children.

The worst that can happen is when an internal node that has two children is chosen, in which case this node will now have 3 children - 2 of its original children and the root (along with the entire left/right subtree attached to the root). So we have some kind of 2-3 tree, of course, satisfying none of the cornerstone conditions which actually makes these kind of trees useful.

- copyconstructor January 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@copyconstructor- If we choose internal node then also we have the rotations rules(single or double rotation) defined for splay tree which will maintain the binary tree and we will not have the 2-3 kind of structure.
Please let me know if I am wrong at any point.

- Vaibhavs January 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In my perspective it ll become a unbalanced tree with left subtree containing more nodes than right or vice verse. Any suggestions ??

- tg9963 January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one more case: if it will choose internal node which has 2 child than this won't be Binary tree.... than root will have 3 child...

- Santosh Dhakad January 11, 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