## 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);
}
}``````

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;
}

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;
}
}

}``````

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));
}``````

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