## Amazon Interview Question Software Engineer / Developers

• 0

Given a BST and 2 numbers a,b, find the number of hops to reach from a to b.

Country: India
Interview Type: In-Person

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

``````LCA(root,a,b)
{
if(a==root || b==root) return root;
if(a->data < root->data && b->data < root->data)
return LCA(root->left,a,b);
if(a->data > root->data && b->data > root->data)
return LCA(root->right,a,b);
return root;
}

CountHops(root,a,b)
{
if(!root || !a || !b) return INT_MIN;
temp=LCA(root,a,b);
hopa=-1;hopb=-1;
p=temp;
while(p!=a)
{
if(a->data < p->data)
p=p->left;
else
p=p->right;
hopa++;
}
p=temp;
while(p!=b)
{
if(b->data < p->data)
p=p->left;
else
p=p->right;
hopb++;
}
return hopa + hopb + 1;
}``````

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

very gud one....easy too..

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

good one. LCA function is superb.

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

LCA function is incomplete. it does not cover all cases.
2 cases where root->left->data !=NULL && root->left->data==a->data or b->data
return root->data;
similarly for root->right->data

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

Find the node at which a and b are split into right and left sub trees.Find the depth of that node.Find the depth of a and b.
Ans : depth(a)+depth(b)-2 depth(node at which a and b split)

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

You don't need to calculate depth from the tree root. Calculate the depth from the lowest common ancestor itself; then Ans: depth'(a) + depth'(b), where depth' is the depth from the LCA.

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

Find the lowest common ancestor for the two given numbers. After that count the number of nodes between lowest common ancestor node & a and lowest common ancestor node & b.

answer = number of nodes to reach a+ number of nodes to reach b + 2

Eg.

Suppose the tree is as given below. a= 8. b= 26.

``````6
/          \
5             10
/           /        \
3             7        13
\            \       /     \
4            8      12     26``````

The lowest common ancestor would be:10

number of nodes to reach a=8 : 1
number of nodes to reach b=26 : 1

answer = 1+1 +2 = 4

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

There are several cases to consider:a left child,b right child;a right child ,b right child ;a left child,b left child ;a right child ,b left child.

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

def get_nodes(root, a, b):
r = find_common_root(root, a, b)
if r-> val not equal a or b:
return num_nodes(r, a) + num_nodes(r, b)
if r-> val == a:
return num_nodes(r, b)
else:
return num_nodes(r, a)

def find_common_root(root, a, b):
if (root-> val < a and root-> val > b) or (root-> val == a) or (root-> val == b):
return root
if root-> val < a and root-> val < b:
find_root(root-> left, a, b)
else:
find_root(root-> right, a, b)

def num_nodes(r,x):
if r-> val == x:
return 0
if r-> val > x:
return 1 + num_nodes(r-> left, x)
else:
return 1 + num_nodes(r-> right, x)

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

but in the function find_common_root(root,a,b)

``````if(root->val<a and root->val<b)
find_root(root->right,a,b);``````

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

if both the nodes are on the same side of the common ancestor , then we need to subtract the. depth

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

// tree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "stdlib.h"
#include "stdio.h"
#include "string.h"

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

struct node *root;

void insert(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=(struct node *)malloc(sizeof(struct node));
(*root)->data =data;
(*root)->left =NULL;
(*root)->right =NULL;
}
else
{
if(((*root)->data) > data)
insert(&((*root)->left),data);
else
insert(&((*root)->right),data);
}
}

struct node * anc(struct node *root,int a,int b)
{
if((a==(root->data)) || (b==(root->data))) return root;
if((a < (root->data)) && (b < (root->data)))
return anc(root->left,a,b);
if((a > (root->data)) && (b > (root->data)))
return anc(root->right,a,b);
return root;
}

int hops(struct node *root,int a ,int b)
{
int count=0;
struct node*temp=NULL,*temp1=NULL;
temp=anc(root,a,b);
temp1=temp;
while(temp->data!=a)
{
if(temp->data >a)
temp=temp->left;
else
temp=temp->right;

count++;
}

while(temp1->data!=b)
{
if(temp1->data >b)
temp1=temp1->left;
else
temp1=temp1->right;

count++;
}
return count;
}

int main()
{
root=NULL;

int arr[10]={4,5,6,7,8,1,2,3,9,10};
int i=0;
struct node *temp=NULL;
while(i<10)
{
insert(&root,arr[i]);
i++;
}
temp=anc(root,7,10);

printf("%d",temp->data);

printf("\nhops==%d",hops(root,4,10));

return 1;
}

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

Assumption is that both the nodes/keys are present in the tree, the basic idea is same that we are trying to find the node from where split occurs and then we calculate the depth of the two nodes.

``````int find_depth(struct node* root, int val)
{
if(!root) return 0;
if(root->data == val) return 0;
if(root->data < val)
return 1+find_depth(root->left, val);
else return 1+find_depth(root->right, val);
}

int find_hops_bst(struct node* root, int a, int b)
{
if(!root) return 0;

if(root->data == a)
return find_depth(root, b);

if(root->data == b)
return find_depth(root, a);

//nodes on opposite side of the current root
if( (root->data > a && root->data < b) ||  (root->data > b && root->data < a) )
return find_depth(root, a) + find_depth(root, b)-1;
else{
if (root->data > a)
return find_hops_bst(root->left, a , b);
else
return find_hops_bst(root->right, a , b);
}
}``````

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

This won't work when the tree is like this ....

9
/ \ 13
5
/
2
/
1

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

``````void hopcount(int element1,int element2,struct tree *root)
{
if((element1<root element && element2<root->element )|| (element1>root->element && element2>root->element))
printf("Hop Count=%d",abs(height(element1,root)-height(element2,root)));
else
printf("Hop count=%d",height(element1,root)+height(element2,root));
}

int height(int element,struct tree* root)
{
static int h=0;
if(root->ele==element)
return c;
else if(root->ele>element)
h=height(element,root->lchild,c+1);
else
h=height(element,root->rchild,c+1);
return h;
}``````

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

``````void hopcount(int element1,int element2,struct tree *root)
{
if((element1<root element && element2<root->element )|| (element1>root->element && element2>root->element))
printf("Hop Count=%d",abs(height(element1,root)-height(element2,root)));
else
printf("Hop count=%d",height(element1,root)+height(element2,root));
}

int height(int element,struct tree* root)
{
static int h=0;
if(root->ele==element)
return c;
else if(root->ele>element)
h=height(element,root->lchild,c+1);
else
h=height(element,root->rchild,c+1);
return h;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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