## Amazon Interview Question for Applications Developers

Country: India
Interview Type: In-Person

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

This will make use Inorder and Postorder Traversal.
LCA ALGO(Int x, Int y)
1. Perform Inorder Traversal
2. Perform Postorder Traversal
3. Let A be the list of all elements between x and y in inorder traversal,
4. In the postorder traversal, find which element in A comes last that element is Least Common Ancestor.
* Since in inorder Left->Root->right and in Postorder Left->Right->Root

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

Small correction: This is a BST

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

While finding lowest common ancestor for the two nodes,maintain the minimum value.
while going left set that to minimum.when found the lca return minimum.

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

``````int leastCommanAncestor(struct node* root, int n1, int n2)
{

if(root == NULL || root->data == n1 || root->data == n2)
return -1;

if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;
if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}``````

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

``````void min_common_ancestor(Node* n, int a, int b, bool& has_a, bool& has_b, int& min_ca) {
if (!n) return;
if (n->val == a) { has_a = true; return; }
if (n->val == b) { has_b = true; return; }

min_common_ancestor(n->left, a, b, has_a, has_b, min_ca);
min_common_ancestor(n->right, a, b, has_a, has_b, min_ca);

if (has_a && has_b) min_ca = min(min_ca, n->val);
}

int min_ca = numeric_limits<int>::max();
min_common_ancestor(root, a, b, false, false, min_ca);``````

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

Better formatted:

``````void min_common_ancestor(Node* n, int a, int b, bool& has_a, bool& has_b, int& min_ca) {
if (!n) return;
if (n->val == a) { has_a = true; return; }
if (n->val == b) { has_b = true; return; }
min_common_ancestor(n->left, a, b, has_a, has_b, min_ca);
min_common_ancestor(n->right, a, b, has_a, has_b, min_ca);
if (has_a && has_b) min_ca = min(min_ca, n->val);
}

int min_ca = numeric_limits<int>::max();
min_common_ancestor(root, a, b, false, false, min_ca);``````

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

// code for finding common ancestor in a BST for two node having minimum values
// code will return the address of the common ancestor
struct node *ancestor(struct node *p)
{
if(p->left->left->left)
ancestor(p->left);
else
return p;
}

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

(least common ancestor(LST) follows the bst rules i.e
if n1, n2 are the two numbers then there exist a LST (n) with this property
n1<n<n2 )
--------------------
Algorithm: LST
input:root, n1,n2
output: least common ancestor

LST(root,n1,n2)

if(root = null)

``return 0``

else

``if (n1<root.value and root.value<n2)``

``return root.value``

``if(n1<root.value and n2<root.value``

``return LST(root.left,n1,n2)``

``if(n1>root.value and n2>root.value``

``return LST(root.right,n1,n2)``

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

Please correct me,If am missing something,
If its a BST , a common least ancestor will be always top most root right ?

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

Am I getting smthing wrong here. As far as I understand it should be a simple code.

node* leastValueNode = FindMinimum(root);
if (leastValueNode->Right != null)
return leastValueNode;
else if (leastValueNode->Parent != null) // Why? Because the leastValueNode has to be the left child.
return leastValueNode->Parent;
return leastValueNode;

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.