## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

distance from node1 to common ancestor + distance from node2 to common ancestor

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

They are asking for maximum path not minimum path.

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

@Nitin : In a tree there a unique path between 2 nodes..

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

If it's a bst then there must be one unique path between any two of nodes. the complexity of searching in BST is log(n) .

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

i think logn complexity is for balanced bst..for ordinary BST,the worst case must be o(n)

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

``````void Bst::Path(int  &i_source , int  &i_destination ){ // give two node value for searching path
node *temp=FindBreak( root , i_source , i_destination );
if( temp->i_value == i_source && temp->i_value == i_destination ){
std::cout<<temp->i_value<<std::endl;
}
Push( temp , i_source );
Push(temp , i_destination);
PrintMap();
}

node *Bst::FindBreak( node *temp, int &i_source , int &i_destination ){ // find the breaking node after which source & destination nodes became ( left , righ ) of break point node
//node *temp=root;
while ( temp!=NULL ){
int i_change=0;
while ( temp->i_value >i_source & temp->i_value>i_destination ){
std::cout<<"left\n";
temp=temp->l_child;
i_change=1;
}
while( temp->i_value <i_source & temp->i_value<i_destination ){
std::cout<<"Right\n";
temp=temp->r_child;
i_change=1;
}
//std::cout<<temp->i_value<<std::endl;
if ( i_change == 0 ) return temp;
FindBreak ( temp , i_source , i_destination);

}
}

void Bst::PrintMap(){
std::cout<<"The path is -------- \n";
for ( Track::iterator ii=m_track.begin() ; ii!=m_track.end() ; ii ++ )
std::cout<<ii->first<<"-->";
std::cout<<"END"<<std::endl;
}

void Bst::Push ( node *temp , int &i_search ){
while( temp!=NULL ){
m_track[ temp->i_value ]=temp->i_value;
if( temp->i_value == i_search )
return ;
else {
m_track[ temp->i_value ]=temp->i_value;
if ( temp->i_value > i_search ) temp=temp->l_child;
else temp=temp->r_child;
}
}
return ;
}``````

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

Can you please explain the algorithm what exactly you are doing and also the code for it in C if possible.

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

1. Find the lowest common ancestor of two nodes value
2. then from lowest common ancestor node find the path of source and destination ( simple traversal ) and store the all traversed node in some DS by sorted order .

I can provide you c++ code.

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

Maximum path will be in case when bst is in a form of linked list. So it will be a number of hops (by left or right branch) between these two nodes.

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

The idea here is to find the lowest common ancestor of the given nodes and then print the path from first given node to second given node through the LCA.

The code is

``````#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>

using namespace std;

struct node {
int data;
struct node *left;
struct node *right;
};

void printPath(int num,struct node *LCA)  {
if(num==LCA->data)  {
cout<<LCA->data<<" ";
return;
}

struct node *temp=LCA;
if(num<LCA->data)
LCA=LCA->left;
else
LCA=LCA->right;

printPath(num,LCA);
cout<<temp->data<<" ";

}

void findMaxPath(int num1,int num2,struct node *root) {
struct node *num1LCA=root;
struct node *num2LCA=root;
struct node *LCA=root;

while(num1LCA==num2LCA) {
if(num1 < num1LCA->data)
num1LCA=num1LCA->left;
else
num1LCA=num1LCA->right;

if(num2<num2LCA->data)
num2LCA=num2LCA->left;
else
num2LCA=num2LCA->right;

if(num1LCA==num2LCA)
LCA=num1LCA;
}

cout<<"Path from node1 to root\n";
printPath(num1,LCA);
cout<<"\nAnother path starting from node 2 to root\n";
printPath(num2,LCA);
return;
}

// FUNCTION TO INSERT NODES IN THE BINARY TREE
void insertNode(struct node **root,int data)  {

// CREATES THE ROOT NODE
if(*root==NULL)  {
(*root)=(struct node*)malloc(sizeof(struct node));
(*root)->data=data;
(*root)->left=NULL;
(*root)->right=NULL;
return;
}

// FOR CREATION OF OTHER NODES
if(data < (*root)->data) {
insertNode((&(*root)->left),data);
}
else    {
insertNode((&(*root)->right),data);
}
return;
}

// DRIVER FUNCTION
int main()  {

struct node *root=NULL;

// TAKES THE INPUT FOR INSERTION
do  {
int data;
scanf("%d",&data);
if(data!=-1)    {
insertNode(&root,data);
}
else    {
break;
}
}while(1);

findMaxPath(10,14,root);

return 0;

}``````

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

store all ancestors in a stack for both elements(inclusive of themselves) and pop until the ancestors match. then get the path of each to that ancestor

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

unless you have duplicate nodes there cannot be more than one path between nodes in the BST

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

``````// (x, y)
int maxPath(TreeNode* root, int x, int y)
{
if (root->data == x) return 1 + distance(root->right, y);
else if (root->data == y) return 1 + distance(root->left, x);
else if (root->data < x) return maxPath(root->right, x , y);
else if (root->data > y) return maxPath(root->left, x, y);
else return 2 + distance(root->left, x) + distance(root->right, y);
}

int distance(TreeNode* root, int key)
{
else if (root->val == key) return 0;
else if (key > root->right) return 1 + distance(root->right, key);
else return 1 + distance(root->left, key);
}``````

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

int maxPath(int a, int b){
return maxPath(BST.root,a, b);
}

int maxPath(BST node,int a, int b){
if(a<node.val && b<node.val)
return maxPath(node.left,a, b);
else if(a>node.val && b>node.val)
return maxPath(node.right,a, b);

return height1(node,a)+height1(node,b);
}

int height1(BST node, int a){
if(node.val == a)
return 0;
if(node.val<a)
return 1+height1(node.right,a);
return 1+height1(node.left,a);
}

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

Maximum distance between 2 nodes in a binary tree is nothing but the "diameter of the tree".

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

Add the depths of both the nodes.

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.