Amazon Interview Question for Software Engineer / Developers


Country: United States




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

Every node is visited exactly twice. Once while going down and the other time while the calls are being returned. That is why the time complexity is O(N).

In general if the number of times an algorithm visits the tree node is upper bounded by some constant "k", then the running time is O(N).

For further practice, try to solve problem no 12.2-7 in the CLRS book(3rd edtn)

- Hingle McCringleBerry October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for replying. May I know what is the Big O of the following solutoin for same problem and why?

public boolean isBalanaced(Node root){

if(root == null) return true;
int heightDiff = getHeight(root.left) - getHeight(root.right);
if(Math.abs(heightDiff > 1)){
return false;
}else{
return isBalanced(root.left) && isBalanced(root.right);
}
}

private int getHeight(Node root){
if(root == null) return 0;
else{
return Math.max(getHeight(root.left) + getHeight(root.right)) + 1;
}

- sivaji8 October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you traverse for the given data and say me the values for each variables at each stage. Please. Please Please.

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

Check for the height difference of right and left sub tree. If it is more than 1 than tree is not balanced.

- GT1 October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'd have given a different algorithm. The recursion you've shown is clumsy and has a lot more code than needed.

The rule for balance: |# of levels on left - # of levels on right| <= 1

We only need two methods, the starting method, and the recursion. I'll be using java here.

public boolean isBalanced(Node root){
   int left = balance_check(root.left);
   int right = balance_check(root.right);
   return (Math.pow(left - right, 2) <= 1);
}

public int balance_check(Node root){
   if(root == null) return 0;
   return 1 + (Math.max(balance_check(root.left), balance_check(root.right));
}

The first function simply calls the recursion to create a left and right value, then compares the square of their difference (which will always be positive) to 1 and returns the boolean of the equation.

The recursion will return 0 is it is given a non-existent node. Otherwise, it will give back 1 + the largest value found recursively of its two children. At the bottom level, a leaf node will have 0 left, 0 right, and thus return only a value of 1. The node above that, assuming both its children are leaf nodes, will return 2. The node above that, which let's say has 2 from the left and 3 from the right, will return 4, etc etc. This way we have the maximum depth of each side. Dynamic programming would put this equation as

OPT(x) = { 1 if x is a leaf, 
                 1 + max(OPT(x.left), OPT(x.right)) if x is internal
               }

It will run in O(N) time, since each node will be visited only once by the above layers.

- Javeed October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its O(N log N).Since each node is touched once per node above it.

- bimpa October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks. Btw I know your solution already. I just can't understand the code I have posted. Could you walk me through for a given data

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

Get leaf node at max depth and get leaf node at minimum depth, if difference is greater than 1 then tree is not balanced.

Inorder/preorder/postorder any of the 3 traversal can be modified to get maxdepth and mindepth.

below is the code for maxdepth similary min depth can be found.
ms-amazon.blogspot.co.uk/2012/08/calculate-depth-of-binary-tree.html

complexity : O(n)

- varun October 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-1 is returned while recursing down the tree. This happens as soon as a subtree is found to be not balanced. Essentially you do not repeat the recursion for each and every node. Hence O(N)

- GK October 19, 2013 | 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