## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

2.(BST property)find the node that is in between the value 1 and value 2 by traversing
node BST(rootnode)
{
while(1)
{
if(rootnode.data<value1 && rootnode.vdaata<value2)
rootnode=rootnode.right;
else if(rootnode.data<value1 && rootnode.vdaata<value2)
rootnode=rootnode.left;
}}
return rootnode;

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

I understand that the 'else if ' is checking for values less than rootnode. No problems. Also, the recursion will terminate if(root.data > value1 && root.data < value2). Again,
if(root.data < value1 && root.data > value2)

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

10 and 17 are children of 10 and 40 and 60 are children of 50 :-)

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

Is this a BST? the position of 15 seems to be wrong. If it's not a BST, we can pick a node as root, then use BFS to traversal

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

Lets consider for allowing duplicates, 15 is in the right position. (Even the interviewer was stumped when he was creating a tree with duplicates for demonstration)

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

1. Calculate depth of both nodes(lets say A and B) from root node.
2. Start with node having lowest depth(lets say B) among those two.

``````while (B->parent!=root)
{
while(A->Parent!=NULL)
{
if( B-->Parent == A-->Parent)
{
if(B->Parent->Parent == A->Parent->Parent)
LCP = B->Parent;
exit();
}
A=A->Parent;
}
A= Initial value of A.
B=B->Parent;
}``````

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

use Tarjan or RMQ algorithm to get better performance

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

``````// This code will have the following complexities...

// O(log n) time complexity for finding a particular element.
// O(log n) time complexity for checking if an element exists.
// O(1) constant space complexity since we are not using any extra space or buffer.

// Assumptions:
// A binary search tree is given along with 2 elements. (tree need not be a complete BST)

// We need to find a node which is the lowest common ancestor of the given 2 elements.

// Definition of a node.
struct node
{
int data;
struct node *left, *right;
};

// Define a method which finds out if an element exists in the tree. O(log n) operations...
int exists(struct node *rt, int x)
{
struct node *p=rt;

while(p!=NULL)
{
if(p->data == x)
return 1;

if(x<=p->data)
p=p->left;
else
p=p->right;
}

// If execution reaches this point, it means element was not found.
return 0;
}

// Find the LCA... O(log n) operations.
// Returns a pointer to the least common ancestor.
struct node * find_LCA(struct node *rt, int x, int y)
{
struct node *p=rt;

while(p!=NULL)
{
if(x<=p->data && y<=p->data)
{
// Move left.
p=p->left;
}
else if(x>p->data && y>p->data)
{
// Move right.
p=p->right;
}
else
{
/* Means that we have reached the lowest point in the tree such that the value
in node p will have a value greater than one element but lesser that the other.
So, all we need to do now is to confirm if those 2 elements actually exist in the tree
considering p as the root. If they do, we have found our least common ancestor (which is p)

if(exists(p,x) && exists(p,y))
return p;
}
}

// If execution reaches this point, it means the LCA was not found. Return NULL.
return NULL;
}``````

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

tree* LCA(tree *root, int lvalue, int rvalue, int index)
{
static int lcaindex = 0;
static tree* lcaroot = root;

if(root == NULL)
return NULL;
else if((findnode(root->left,lvalue) && findnode(root->right, rvalue)) || (findnode(root->left,rvalue) && findnode(root->right, lvalue))
{
if(index > lcaindex)
{
lcaindex = index;
lcaroot = root;
}

}
else
{
LCA(root->left,lvalue,rvalue,index++);
LCA(root->right,lvalue,rvalue,index++);
}

return lcaroot;
}

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.