Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

A tree's diameter must be like this: it has a node P as the center, with left radius being the longest path of P's left subtree and right radius being the longest path of P's right subtree.
So we divide the problem into two parts:
(1)traverse the whole tree and get the height of each subtree, meanwhile determine the diameter's center node P
(2)get the two radii of this diameter
Following is code in C++:

void getDiameter(vector<TreeNode*>& diameter, TreeNode* p)
{
	if(p == NULL) return;

	pair<TreeNode*, int> info = {0};		//record the diameter's center and length
	unordered_map<TreeNode*, int> heightMap;//record height of each node
	//traverse the tree to get the diameter's center and length
	getDiameterInfo(p, res, heightMap);	
	//get the whole diameter from left end to right end
	getLongestPath(diameter, info.first->left, heightMap, true);
	diameter.push_back(info.first);
	getLongestPath(diameter, info.first->right, heightMap, false);
}
void getDiameterInfo(TreeNode* p, 
	             	 pair<TreeNode*, int>& info, 
	             	 unordered_map<TreeNode*, int>& heightMap
	             	)
{
	if(p == NULL){
		heightMap[p] = 0;
		return;
	}
	//divide and conquer
	getDiameter(p->left, info, heightMap);
	getDiameter(p->right, info, heightMap);
	//get subtree's height
	int lheight = heightMap[p->left], rheight = heightMap[p->right];
	//check if the diameter with p being the center is longer
	heightMap[p] = max(lheight, rheight) + 1;
	if(lheight + rheight + 1 > info.second){
		info.first = p;
		info.second = lheight + rheight + 1;
	}
}
void getLongestPath(vector<TreeNode*>& path,
	                TreeNode* p,
	                unordered_map<TreeNode*, int>& heightMap,
	                bool preOrder
	                )
{
	if(p == NULL) return;

	if(preOrder){
		path.push_back(p);
		getLongestPath(path, heightMap[p->left] < heightMap[p->right] ? p->right : p->left, heightMap, preOrder);
	}
	else{
		getLongestPath(path, heightMap[p->left] < heightMap[p->right] ? p->right : p->left, heightMap, preOrder);
		path.push_back(p);
	}
}

- uuuouou April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findlongest(struct tnode *root,int a[],int ind,int level,int *max,int path[])
{
if(root==NULL)
{
if(level>*max)
{
int i=0;
for(i=0;i<ind;i++)
path[i]=a[i];
*max=level;
}
return;
}
a[ind]=root->val;
findlongest(root->left,a,ind+1,level+1,max,path);
findlongest(root->right,a,ind+1,level+1,max,path);
}

int main()
{
int i,num;
struct tnode *root=NULL;
for(i=0;i<N;i++)
{
scanf("%d",&num);
root=addnode(root,num);
}
int a[100],leftpath[100],rightpath[100];
num=0;
findlongest(root->left,a,0,0,&num,leftpath);
while(num>0)
printf("%d\t",leftpath[--num]);
printf("%d\t",root->val);
num=0;
findlongest(root->right,a,0,0,&num,rightpath);
for(i=0;i<num;i++)
printf("%d\t",rightpath[i]);
printf("\n");
getch();
return 0;
}

- Nitin April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution. O(n)

public void printDiameter(Node root) {

	List<String> maxDiameter = new ArrayList<String>();

	if (null != root) {
		root.getMaxRadius(maxDiameter);
	}

	for (String id : maxDiameter) {
		// print id
	}
}

public class Node() {

	String id;
	Node left;
	Node right;

	// return max radius (height or depth) of this subtree
	// conditionally record diameter of this subtree
	public List<String> getMaxRadius(List<String> maxDiameter) {
		// fetch child radii
		List<String> leftMaxRadius = null != left ? left.getMaxRadius(maxDiameter) : new ArrayList<String>();
		List<String> rightMaxRadius = null != right ? right.getMaxRadius(maxDiameter) : new ArrayList<String>();

		// test/set max diameter
		if (leftMaxRadius.size() + rightMaxRadius.size() + 1 > maxDiameter.size()) {
			maxDiameter.clear();
			maxDiameter.addAll(leftMaxRadius);
			maxDiameter.add(id);
			maxDiameter.addAll(rightMaxRadius);
		}

		// return max radius
		if (leftMaxRadius.size() > rightMaxRadius.size()) {
			leftMaxRadius.add(id);
			return leftMaxRadius;
		}
		else {
			rightMaxRadius.add(0, id); // add to front to preserve order
			return rightMaxRadius;
		}
	}

}

- Anonymous April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

int diameter(TreeJ tree)
	{
	   if (tree==null){
	     return 0;
	   }

	  int lheight = getMaxHeight(tree.left);
	  int rheight = getMaxHeight(tree.right);

	  int ldiameter = diameter(tree.left);
	  int rdiameter = diameter(tree.right);

	  return Math.max(lheight + rheight + 1, Math.max(ldiameter, rdiameter));
	}

- Anonymous June 10, 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