Amazon Interview Question for Software Engineer / Developers






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

Detailed description of the above solution is here:

crackinterviewtoday.wordpress.com/2010/03/11/diameter-of-a-binary-tree/

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

gud explaination here

- dev September 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No doubt good explanation.
However they are recursively traversing the tree twice.
Same recursion, gathering different data. Should be able to do it in one recursion.

- JSDUDE June 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int diameter = 0;
int findDiameter(struct tree * node)
{
	int dim ,l_len,r_len;
	/* If null node came then return 0 */
	if(node == 0)
		return 0;
	/* Initialize all the temp length variables by 0 */
	dim = l_len = r_len = 0;
	/* Recursive call for left & right subtree */
	l_len = findDiameter(node->left);
	r_len = findDiameter(node->right);
	/* Calculate the depth at this level */	
	dim = r_len + l_len + 1;
	/* If the current level diameter is bigger then previous */
	/* Then save the current diameter as biggest one */
	if(dim > diameter)
		diameter = dim;
	/* Return the depth, till current node */
	return (MAX(l_len,r_len) + 1);
}

- Ashutosh March 31, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int diameterOfBinaryTree(Node node)
{
if (node == null)
{
return 0;
}

int leftHeight = heightOfBinaryTree(node.left);
int rightHeight = heightOfBinaryTree(node.right);

int leftDiameter = diameterOfBinaryTree(node.left);
int rightDiameter = diameterOfBinaryTree(node.right);

return Math.max(leftHeight + rightHeight + 1,
Math.max(leftDiameter, rightDiameter));
}

working code...visit:
h**p://crackinterviewtoday.wordpress.com/2010/03/11/diameter-of-a-binary-tree/

- Anonymous April 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int diameter (Node *root) {
if(root){
int d1 = 1+diameter(root->left);
int d2 = 1+diameter(root->right);
if( d1+d2 > max_dia ) {
max_dia = d1+d2;
}
return max( d1, d2 );
}
return 0;

}
int max(int d1, int d2){
if (d1 > d2 ) return d1;
else if(d2 > d1) return d1;
else return d1;
}

- Anonymous May 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void traverse(struct node *t, int depth, int *first, int *second)
{
if(t==NULL) return;
if(t->left==NULL && t->right==NULL) { //Hit a leaf
if(depth>*first) {
*second = *first;
*first = depth;
}
else if(depth<*first && depth>*second) *second = depth;
return;
}
traverse(t->left, depth+1, first, second);
traverse(t->right, depth+1, first, second);
}

int main()
{
int *first, *second;
*first = *second = 0;
traverse(root, 1, &first, &second);
print *first + *second;
}

- Catalan May 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

- kiwi June 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Guys, This question threw me out from AMAZON, second interview round.......
but i make it on next day.......
// Assume a function height_tree(node *root) will
//return sum of height of left sub tree and height of right sub tree+2;

//I am counting no of edges...

int tree_bredth(node *root)
{

int i,j,k;
i = 0;
j = 0;
k = 0;

if(root = NULL)
return(0);
i = height_tree(root->left);

j = height_tree(root->right);

k = i+j+2;

return(max(k,tree_bredth(root->left),tree_bredth(root->right)))


}

- nagpal_dce August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For and O(n) algo visit "http: // t.co / lum8dAM"

- Anonymous September 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check this

int TreeDiameter(Tnode *root)
{
    static int max,diameter;
    static Tnode *tmp=NULL;
    if(root==NULL)
        return 0;
    if(tmp==NULL)
        tmp=root;
    int leftmax=TreeDiameter(root->left);
    int rightmax=TreeDiameter(root->right);
    if(diameter<(leftmax+rightmax))
        diameter=leftmax+rightmax;
    if(leftmax >= rightmax)
    {
        max=leftmax;
    }
    else
    {
        max=rightmax;
    }
    if(tmp==root)
        return diameter;
    return 1+max;
}

- ananthakrishnan.s.r July 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}

int Diameter(struct node *R,int *height)
{
int ld=0;
int rd=0;
int rh=0;
int lh=0;

if(R==NULL)
{
*height=0;
return 0;
}
ld=Diameter(R->left,&lh)+1;
rd=Diameter(R->right,&rh)+1;
*height=(lh>rh?lh:rh)+1;
return(max(lh+rh+1,max(ld,rd)));
}

- geeks July 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int diaMeter (struct node* node)
{
if (node == NULL)
return 0;
/* get the height of left and right sub-trees */
int lheight = maxDepth(node->left);
int rheight = maxDepth(node->right);
/* get the diameter of left and right sub-trees */
int ldiameter = diaMeter(node->left);
int rdiameter = diaMeter(node->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));

}

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

Python code

## General binary tree node class. @property is not useful right now.
class Node(object):
	def __init__(self, value=None, left=None, right=None):
		self.__left = left
		self.__right = right
		self.__value = value 

	@property
	def right(self):
		return self.__right
	
	@right.setter
	def right(self, value):
		self.__right = value

	@right.deleter
	def right(self):
		del self.__right
	
	@property
	def left(self):
		return self.__left
	
	@left.setter
	def left(self, value):
		self.__left = value

	@left.deleter
	def left(self):
		del self.__left

def get_diameter(node):
	if not node:
		return (0, 0)

	if not isinstance(node, Node):
		raise Exception(" Invalid param type ")
	
	(left_height, left_diameter) = get_diameter(node.left)
	(right_height, right_diameter) = get_diameter(node.right)
	
	current_diameter = 0
	if node.right and node.left:
		current_diameter = left_height + right_height + 1


	return (max([left_height, right_height]) + 1, max([left_diameter, right_diameter, current_diameter]))

# Case 2: Diameter is not through root
#	
#		      1
#		2	   
#	       4  5        	
#            8
#           9		   
root = Node(1)
root.left = Node(2)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(8)
root.left.left.left.left = Node(9)

print "case 1 : Height : %s Diameter : %s" %  get_diameter(root)		


#     case 2: Diameter through root
#		      1
#		2	    3
#	       4  5        6 7	
#            8		    10
#          9               11   
root.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(10)
root.right.left.right.left = Node(11)
print "case 2 Height : %s Diameter : %s" %  get_diameter(root)

- AnupamSharma September 20, 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