Amazon Interview Question
Country: India
First find the minimum and maximum element in the list of n nodes, and then apply standard LCA solution to min & max nodes.
suppose the tree is
1
2 4
3 5
5 is the right child of 2
now keys are 3 , 4 ,5
a/c to ur solution min is 3 and max is 5 so the CA should be 2
but CA should be 1
m i missing something
If it is BST then above solution works, if it is just binary tree (not BST) then this won't works.
import java.util.List;
public class Lca {
private static class Node {
Node left;
Node right;
}
private Node root;
// Helper class
private static class LcaSpec {
Node lca;
int numOfChildren;
LcaSpec(Node lca, int numberOfChildren) {
this.lca = lca;
this.numOfChildren = numberOfChildren;
}
}
// Gets the spec of its children.
// Checks if one of its child is already an lca.
// Checks if it is one of the nodes (uses naive reference equals) and
// updates spec.
//
// Recursive and O(N x M)
// N - size of tree
// M - size of list of child nodes
private LcaSpec getLca(Node node, List<Node> nodes) {
if (node == null) {
return null;
}
LcaSpec leftSpec = getLca(node.left, nodes);
LcaSpec rightSpec = getLca(node.right, nodes);
if (leftSpec != null && leftSpec.numOfChildren == nodes.size()) {
return leftSpec;
}
if (rightSpec != null && rightSpec.numOfChildren == nodes.size()) {
return rightSpec;
}
int numOfChildren = (leftSpec == null) ? 0 : leftSpec.numOfChildren;
numOfChildren += (rightSpec == null) ? 0 : rightSpec.numOfChildren;
if (nodes.contains(node)) {
++numOfChildren;
}
return new LcaSpec(node, numOfChildren);
}
// Get LCA given list of child nodes.
// Assumption is there exists such a node.
public Node getLca(List<Node> nodes) {
return getLca(root, nodes).lca;
}
}
1. For each node (in the multiple node list) store its path from root to itself say each path in an array. This can be done by pre - order search. Remember this not a BST.
2. Let A,B,C,.. M be such arrays. (count m).
3. Let n be the shortest of the above paths. you can also collect the arrays that yield the shortest paths.
for (i=0; i<n;i++)
{
if( i is not within the range of any one Array Say H)
{
then last element of H is the LCA;
break;
}
if(A[i] == B[i] == ... == M[i]);//great do nothing
else
{
A[i-1] is the LCA.
break;
}
}
node *closest(node* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;
if(root == NULL)
{
return(NULL);
}
if(root->left==p || root->right==p || root->left==q || root->right==q)
{
return(root);
}
else
{
l = closest(root->left, p, q);
r = closest(root->right, p, q);
if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}
<pre lang="" line="1" title="CodeMonkey38495" class="run-this">mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;
if(root == NULL)
{
return(NULL);
}
if(root->left==p || root->right==p || root->left==q || root->right==q)
{
return(root);
}
else
{
l = closestAncestor(root->left, p, q);
r = closestAncestor(root->right, p, q);
if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}
</pre><pre title="CodeMonkey38495" input="yes">
</pre>
static BinaryNode leastCommonAncestor(BinaryNode root,List<Integer> integers){
if(root == null) return null;
for (Iterator<Integer> iterator = integers.iterator(); iterator.hasNext();) {
Integer value = iterator.next();
if(value == root.value)
return root;
}
BinaryNode lnode = leastCommonAncestor(root.left, integers);
BinaryNode rnode = leastCommonAncestor(root.right, integers);
if(lnode == null && rnode == null) return null;
if(lnode != null && rnode != null) return root;
if(lnode != null) return lnode;
else return rnode;
}
As everybody has written code, The algorithm for finding the LCA in simple words is as follows:
Start from root (TOP: preorder traversal) . lets consider the 2 nodes given as input be n1 and n2. Search both the left and right subtree of the root. As long as you find both n1 and n2 being part of one of the subtree, drillAs we proceed from root towards the leafAs we proceed from root towards theAs we proceed from root towards the leaf leafAs we proceed from root towards the leafAs we proceed from root towards the leafAs we proceed from root towards the leaf down on that subtree ignoring the other. If you find a node such that n1 is in left subtree and n2 in right subtree or vice versa then it will be the LCA.
- getjar.com/todotasklist my android app December 18, 2011