Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

int diameter(struct node * tree)
{
/* base case where tree is empty */
if (tree == 0)
return 0;

/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);

/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);

/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}

- k2 April 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

height() is a standard function to determine the height or depth of a tree.

- k2 April 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Diameter is the maximum distance from one leaf node to another.
It is the maximum path length which can either pass through root of the subtree at that point or may not , as it may entirely lie in the left/right subpart of the tree. So basically it is the maximum of left-diamter, right-diameter and the height of the tree(case when diameter passes through the current root).

diamter = max(height ,max (leftDiameter , rightDiamter) )

pass the parameter of height to avoid extra calls during recursion and then update the current height. Return the maximum of diamter from that node.

int diameter(node * root, int *height){
         if(root == NULL) { height = 0; return 0;}
        int  leftHeight =0 , rightHeight = 0;
        int leftDiamter = diameter(root->left , &lh);
        int rightDiameter = diameter(root->right, &rh);
        *height = max(leftHeight, rightHeight) + 1 ;
        return max(  (max ( leftDiamter , rightDiameter ) , height );
   }

Time Complexity = O(n) // as only 1 visit to all the nodes.

- scofield April 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

its o(n^2) complexity

- abc April 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

last line shall be return max( (max ( leftDiamter , rightDiameter ) , lh + rh + 2);

- def February 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int dia(node *r,int *diam)
{
if(r==NULL)
return 0;
cout<<"in\n";
int ld,rd;
ld=rd=0;
int lh,rh;
lh=rh=0;
lh=dia(r->left,&ld);
rh=dia(r->right,&rd);
*diam=imax(ld,rd,lh+rh+1);
return lh>rh?lh+1:rh+1;
}
// it returns height of root and diameter can be found in the argument (pass by pointer) diam
/* initial call should be
int diam=0;
dia(root,&diam);
cout<<diam;
*/

- epsilon May 15, 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