## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

"http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html"

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

This would not work. Diameter of tree is defined as longest path between two leaves passing through root node.

In order to find out two farthest node, it is not necessary to pass through root node.

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

@Jain: who said that diameter should pass through root node??

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

@Jain : have a careful look at the link. May be u learn what it says.

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

watch the solution of the video on youtube, it is very well explained there with example

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

Seems the mentioned solution is O(n^2). Are there any faster solution?

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

for each node in a tree,{
store (height of left sub tree+height of right sub tree)
and two childs which are the reason for these height (note: if one of the child is null then store node itself instead null)
}

for the node which has highest sum, retrive its two childs stored in above procedures.
those two nodes(childs) are situated at maximum distance.

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

We can take a global variable instead of storing each computation.
And the nodes can also be stored in some global variable.

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

I think that the solution would be:
1) Find the next leaf node of the tree. Build the path(string) to the leaf node by adding "0" if move to the left node and adding "1" if move to the right node. I.e. in the sample of the tree in the comment above the path to N9 node is "100"
2) Check the leaf nodes buffer. If there are no items there, add the current leaf node.
3) If there are the nodes in the leaf buffer, for each of them:
i=0
while(current leaf node path[i] == next buffer item[i])
i++
distance = current leaf node path.length - i + next buffer item.length - i;
if(distance > max) max = distance.
Example:
In the comment above the path to N9 node is "100", the path to N6 node is 11; increase i until the characters at i position are the same. i is 1 after this operation;
so the distance between these node is 3-1 + 2-1 = 3;

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

nice solution. really appreciate this approach.

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

Why not just do inorder traversal? The first and last element will be the ones that are further apart.

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

No inorder traversal will not solve.

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

Don't know the exact solution but it should be something like that :-
1. The two nodes, which are farthest, must be a leaf.
2. Amongst the two leaves, one should be from from the left subtree of root and the other from the right subtree.

I would like to proceed this way - find the deepest leaf of left sub tree of root.
Do the same for right sub tree of root - i.e. deepest leaf
The two nodes are our answer

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

wont work...what if the root dint have a right child and the entire tree is below left child?

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

Agree, so we do same at each node and maintain the Max count.

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

if the tree don't have left or right child then we will start from root itselft to the respective child......
hope you understand

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

Take a look at the second comment. The link to cs.duke.edu. Understand that code and thats all you need.

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

That is the gist indeed. Its a little more involved(than that) though, because you need to identify the participant nodes and not just compute the diameter of tree.

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

Andy now have a look. The link would work.

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

This is similar to finding the diameter of a tree:
diameter = MAX(LDIAMETER , RDIAMETER , RHEIGHT+LHEIGHT+1);

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

This is a variation of finding the diameter. Here is the code for the same.

``````#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

typedef struct treenode
{
struct treenode *left;
struct treenode *right;
int val;
}node;

node *node1='\0', *node2='\0';
int max = INT_MIN;

int FindNodes(node *tree, int *height, node **dnode)
{
int lh=0, rh=0, leftD=0, rightD=0;
node *lnode='\0', *rnode='\0';
if(tree=='\0')
{
*height=0;
*dnode='\0';
return 0;
}
leftD = FindNodes(tree->left, &lh, &lnode);
rightD = FindNodes(tree->right, &rh, &rnode);

int max1 = (leftD > rightD?leftD:rightD);
*height = 1 + (lh>rh?lh:rh);
int max2 = lh+rh+1;
if(lnode=='\0'&&rnode=='\0')
lnode = rnode = tree;
if(lh>rh)
*dnode=lnode;
else
*dnode=rnode;
if(max<lh+rh)
{
node1=lnode;
node2=rnode;
max = lh+rh;
}
return max1>max2?max1:max2;
}

main()
{
node *tree = '\0';
//construct tree with atleast two nodes.
int height = 0;
node *dnode = '\0';
int D = FindNodes(tree, &height, &dnode);
printf("Diameter is:%d\n",D);
printf("Distant Nodes: %d, %d\n", node1->val, node2->val);``````

}

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

What is node1, node2, max...they are not declared!

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

``````Farthest is not very clear.       In below tree if we compare N7-N9 vs N7-N6 which pair is farthest?
N1
/   \
N2    N3
/       /\
N4          N5 N6
/\           /\
N7 N8         N9 N10``````

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

distance b/w N7-N9 is 6 while in b/w N7-N6 is 5 hence N7-N9 is farther then N7-N6

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

Same as finding the diameter of a binary tree but in this case we have to return the nodes as well.

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

I think there should be some restrictions in this problem where the distance between two nodes is no repeat node.so my solution is :
0 : there is only one path between two nodes in a tree.
1: travel the tree and transform the tree to the mapping mtrix .
2: use floyed algorithm to compute the distance between any two nodes.
3: record the farthest distance.

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

Find Deepest leaf in the left subtree of root and the deepest leaf of the right subtree and add their distances from the root. This can be done in linear time.

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

Sometimes the longest path may exist in either the left subtree or the right subtree. It is not necessary that the path should go through the root.

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

guess this would work though i dint check completely

``````typedef struct pair{
Node n1;
Node n2;
int n1_dist;
int n2_dist;
}Result;

Result Farthest(Node n){
if(n==NULL){
Result *p=malloc(sizeof(Result));
p->n1=NULL;
p->n2=NULL;
n1_dist=0;
n2_dist=0;
return p;
}
if(n->left==NULL){
Result *p1=malloc(sizeof(Result));
p1->n1=n;
p1->n2=n;
n1_dist=0;
n2_dist=0;
}
else
Result *p1=Farthest(n->left);
else if(n->right==NULL){
Result *p2=malloc(sizeof(Result));
p2->n1=n;
p2->n2=n;
n1_dist=0;
n2_dist=0;
}
else
Result *p2=Farthest(n->right);

Result *p3=malloc(sizeof(Result));

if(p1->n1_dist>p1->n2_dist){
p3->n1_dist=p1->n1_dist+1;
p3->n1=p1->n1;
}

else{
p3->n1_dist=p1->n2_dist+1;
p3->n1=p1->n2;
}

if(p2->n1_dist>p2->n2_dist){
p3->n2_dist=p2->n1_dist+1;
p3->n2=p2->n1;
}

else{
p3->n2_dist=p2->n2_dist+1;
p3->n2=p2->n2;
}

if((p1->n1_dist + p1->n2_dist)>(p2->n1_dist + p2->n2_dist)){
if((p1->n1_dist + p1->n2_dist)>(p3->n1_dist + p3->n2_dist))
return p1;
else
return p3;
}

else if((p2->n1_dist + p2->n2_dist)>(p3->n1_dist + p3->n2_dist))
return p2;

return p3;
}``````

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

O(nlogn)

``````#include <iostream>
#include <algorithm>

using namespace std;

struct Node {
int value;
Node* left;
Node* right;

Node(int value, Node* left, Node* right) : value(value), left(left), right(right) {}
Node(int value) : value(value), left(0), right(0) {}
~Node() {
delete left, right;
}
};

Node* n(const int& x, Node* left, Node* right) {
return new Node(x, left, right);
}

Node* n(const int& x) {
return new Node(x, 0, 0);
}

template<class T, class K> struct Tuple {
T one;
K other;

Tuple(T one, K other) : one(one), other(other) {}
};

template<class T> struct LikeTuple : Tuple<T, T> {
LikeTuple(T one, T other) : Tuple<T, T>(one, other) {}
};

typedef Tuple<Node*, int> Height;

Height height(Node* root, Node* parent) {
if (root == 0) return Height(parent, 0);
Height left_height = height(root->left, root);
Height right_height = height(root->right, root);
if (left_height.other > right_height.other) {
left_height.other++;
return left_height;
} else {
right_height.other++;
return right_height;
}
}

Height height(Node *root) {
return height(root, 0);
}

typedef Tuple<LikeTuple<Node*>, int> FarthestNodes;

FarthestNodes farthest_nodes(Node* root) {
if (root == 0) return FarthestNodes(LikeTuple<Node*>(0, 0), 0);
FarthestNodes left_farthest = farthest_nodes(root->left);
FarthestNodes right_farthest = farthest_nodes(root->right);
Height l_height = height(root->left);
Height r_height = height(root->right);
int root_dia = l_height.other + r_height.other + 1;
if (root_dia > left_farthest.other && root_dia > right_farthest.other)
return FarthestNodes(LikeTuple<Node*>(l_height.one, r_height.one), root_dia);
else if (left_farthest.other > right_farthest.other)
return left_farthest;
else
return right_farthest;
}

int main(int argc, char** argv) {
Node* root = n(10,
n(5,
n(2,
n(0,
n(-1),
n(2, n(1), 0)),
0),
n(7,
n(6),
n(9, n(8), 0))),
n(12,
n(11),
n(15,
n(13, 0, n(14)),
0)));
FarthestNodes nodes = farthest_nodes(root);
cout << "Farthest nodes are: " << nodes.one.one->value << " <-> " << nodes.one.other->value << " and distance between them is " << nodes.other << endl;
delete root;
return 0;
}``````

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

Sample Tree:

``1``

``/      \``

``2          3``

``/    \``

``4      5``

``/        /``

``6       7``

``/       /``

``8      9``

The nodes farthest from each other are 8 and 9, taking six hops to get there.

Generate the following list for each leaf node in the tree (how to get there from root):

``8: left, left, left, left``

``9: left, right, left, left``

``3: right``

To get the distance between two nodes, you compare their lists starting from the left and remove all the instructions before they begin to differ. Then just add the size of the lists.

Distance between 8 and 9 is 6:

``8: left (remove), left (+1), left (+1), left (+1)``

``9: left (remove), right (+1), left (+1), left (+1)``

Distance between 8 and 3 is 5:

``8: left (+1), left (+1), left(+1), left (+1)``

``3: right (+1)``

It should be obvious where to go from here.

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

we can start from a leaf node and do a DFS so that we can get the distance of each node from the leaf node find the maximum of those.

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

Brief approach to the solution is, here any way its clear that farthest nodes will be the leaf nodes. so first traverse the tree using any of the tree traversal and keep the leaf nodes in list.
Next step is for each leaf node, find the distance between other nodes in the leaf list and keep track of the max length.
To find the length between two nodes, use the approach of finding the lowest common anscetor(LCA) between these node and sum up the length to each node from the LCA.

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

Brief approach to the solution is, here any way its clear that farthest nodes will be the leaf nodes. so first traverse the tree using any of the tree traversal and keep the leaf nodes in list.
Next step is for each leaf node, find the distance between other nodes in the leaf list and keep track of the max length.
To find the length between two nodes, use the approach of finding the lowest common anscetor(LCA) between these node and sum up the length to each node from the LCA.

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

1.If root contains left and right child,diameter will be the max distance.
2.If root is having only one child,
a.get the max height from root
b.go to node which has left right child and get the diameter for this node.
max of a or b will be answer.

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

Its very simple, count the number of leaf nodes, say it n. Make a table n * n. For each pair of node find the Lowest Common Ancestor and store it into the table. You just need to populate half the table ( either upper triangular matrix or lower). For e.g a cell in the table will contain the following string (LCA, depth of 1st leaf node from LCA, depth of second leaf node from LCA).

Once this table is populated you can just initialize max to 0. Iterate over the table and check the sum of depth1 and depth2 for each cell and appropriately modify the max variable if you find the sum > max. the answer is the in the cell from where the final value of the max comes from.

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

Firstly, we try to find the max distance by doing traversal. For each node Ni, max distance is max(1+heightOf(left(Ni))+heightOf(right(Ni))), and the exact Ni node (say M) with left sub-tree height value and right sub-tree height which gets max distance can be recorded. Then we do traversal again starting from M and find the two leaf nodes.

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

Would these nodes be first and last in in-order traversal of the tree?

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

two ends of inorder traversal of tree

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

void findHeight(sTree * root, int* height,int max,sTree** node)
{
if(root == NULL)
return;
max++;
//*height = max > *height?max:*height;
if(max > *height)
{
*height = max;
*node = root;
}
findHeight(root->lChild,height,max,node);
findHeight(root->rChild,height,max,node);

}
void findDia(sTree *root,sTree ** end,sTree** toend)
{
int Lheight = 0;
int Rheight = 0;
findHeight(root->lChild,&Lheight,0,end); // find height of left node
findHeight(root->rChild,&Rheight,0,toend);//height of right node
printf("dia = %d",Lheight+Rheight);

}

int main()
{
// asumtion a tree is already present On complexcity
sTree *end,*toend;
findDia(root,&end,&toend);
}

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

do a prefix take last element, a postfix and the first element of this is what you need,,

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

You can reuse the diameter method, but instead of returning int, you could return a custom class, say,

``class NodeM{ int len; Node n;``

}
basically allowing you to keep in mind which node returned the max height on either side. Let your diameter method return NodeM[]. So you have both nodes between which you had max distance.
You can optimize the diameter, which is exponential in complexity by calling diameter on left and right children, before calling height function. Making the solution linear.

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

Doesn't work.
Solution should be similar to finding diameter of the binary tree

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.

### 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.