Microsoft Interview Question Software Engineer in Tests
Country: United States
This code assumes that both the nodes (a and b) are present in the tree right?
If only one of them is present then it will return that whereas it must return NULL for such a case.
class FindClosestCommonAncestorNaryTree
{
public Node Solve(Node tree, Node node1, Node node2)
{
List<Node> ancestors1 = new List<Node>();
List<Node> ancestors2 = new List<Node>();
tree.GetAncestorsOf(node1, ref ancestors1);
tree.GetAncestorsOf(node2, ref ancestors2);
foreach (Node n1 in ancestors1)
{
foreach (Node n2 in ancestors2)
{
if (n1 == n2)
{
return n1;
}
}
}
return null;
}
}
public class Node
{
public int data;
public List<Node> children = null;
public Node(int _data, List<Node> _children)
{
data = _data;
children = _children;
}
internal bool GetAncestorsOf(Node node, ref List<Node> ancestors)
{
if (this == node)
{
return true;
}
if (children != null)
{
foreach (Node child in children)
{
if (child.GetAncestorsOf(node, ref ancestors))
{
ancestors.Add(this);
return true;
}
}
}
return false;
}
}
get ancestor list of both nodes n1 and n2.
compare top ancestor of n1 with top ancestor of n2.
if equal, got to the a level below of ancestor for n1 & n2 and compare in iterative manner.
at some point, either they will not be equal or one of the ancestor will be null.
return the previous compared ancestor.
Lowest Common Ancestor
findLCA(Node head,int Key1,int Key2)
{
if( head==null) return;
if(Key1>head.Key && Key2> head.Key)
{
findLCA(head.Right,Key1,Key2)
}
else if(Key1<head.Key && Key2<head.Key)
{
findLCA(head.Left,Key1,Key2)
}
else
return head;
}
def lca_dfs(self,key1,key2,root):
execut=[]
execut.extend([key1,key2])
lst1=self.dfs(execut[0],root)
lst2=self.dfs(execut[1],root)
intrsctn=(set(lst1)).intersection(set(lst2))
lst=list(intrsctn)
if len(lst)>0:
print "lca is:",lst[len(lst)-1]
else:
print "lca is:",root.val
def dfs(self,key,root):
if len(root.child)==0:
return
for nde in root.child:
if nde.val==key:
return ([])
else:
fnd=self.dfs(key,nde)
if isinstance(fnd,list):
fnd.append(nde.val)
return fnd
return fnd
def lca_dfs(self,key1,key2,root):
execut=[]
execut.extend([key1,key2])
lst1=self.dfs(execut[0],root)
lst2=self.dfs(execut[1],root)
intrsctn=(set(lst1)).intersection(set(lst2))
lst=list(intrsctn)
if len(lst)>0:
print "lca is:",lst[len(lst)-1]
else:
print "lca is:",root.val
def dfs(self,key,root):
if len(root.child)==0:
return
for nde in root.child:
if nde.val==key:
return ([])
else:
fnd=self.dfs(key,nde)
if isinstance(fnd,list):
fnd.append(nde.val)
return fnd
return fnd
public static N_ary_tree findCommonAncestor(N_ary_tree root,
N_ary_tree node1,N_ary_tree node2){
if(root == null){
return root;
}
if(root==node1 || root==node2){
return root;
}
N_ary_tree res = null;
int count = 0;
for(N_ary_tree ele : root.children){
N_ary_tree temp = findCommonAncestor(ele,node1,node2);
if(temp!=null){
res=temp;
count++;
}
}
if(count>=2){
return root;
}
return res;
}
class Node(object):
def __init__(self, val):
self.val = val
self.children = []
self.ans = None
def add_child(self, child_node):
self.children.append(child_node)
def lca(node, a, b, ans):
if ans[0] is not None:
return
return_vals = []
for child in node.children:
if child.val == a or child.val == b:
return_vals.append(child.val)
else:
return_vals.append(lca(child, a, b, ans))
else:
is_a = is_b = False
for val in return_vals:
if val == a:
is_a = True
if val == b:
is_b = True
if is_a and is_b:
ans[0] = node.val
print(node.val)
else:
if is_a:
return a
if is_b:
return b
root = Node(0)
l1_c1 = Node(1)
l1_c2 = Node(7)
l2_c1 = Node(2)
l2_c2 = Node(3)
l2_c3 = Node(6)
l2_c4 = Node(8)
l2_c5 = Node(9)
l3_c1 = Node(4)
l3_c2 = Node(5)
root.add_child(l1_c1)
root.add_child(l1_c2)
l1_c1.add_child(l2_c1)
l1_c1.add_child(l2_c2)
l1_c1.add_child(l2_c3)
l1_c2.add_child(l2_c4)
l1_c2.add_child(l2_c5)
l2_c2.add_child(l3_c1)
l2_c2.add_child(l3_c2)
lca(root, 4, 6, [None])
lca(root, 8, 9, [None])
lca(root, 4, 5, [None])
lca(root, 4, 8, [None])
class Node(object):
def __init__(self, val):
self.val = val
self.children = []
self.ans = None
def add_child(self, child_node):
self.children.append(child_node)
def lca(node, a, b, ans):
if ans[0] is not None:
return
return_vals = []
for child in node.children:
if child.val == a or child.val == b:
return_vals.append(child.val)
else:
return_vals.append(lca(child, a, b, ans))
else:
is_a = is_b = False
for val in return_vals:
if val == a:
is_a = True
if val == b:
is_b = True
if is_a and is_b:
ans[0] = node.val
print(node.val)
else:
if is_a:
return a
if is_b:
return b
root = Node(0)
l1_c1 = Node(1)
l1_c2 = Node(7)
l2_c1 = Node(2)
l2_c2 = Node(3)
l2_c3 = Node(6)
l2_c4 = Node(8)
l2_c5 = Node(9)
l3_c1 = Node(4)
l3_c2 = Node(5)
root.add_child(l1_c1)
root.add_child(l1_c2)
l1_c1.add_child(l2_c1)
l1_c1.add_child(l2_c2)
l1_c1.add_child(l2_c3)
l1_c2.add_child(l2_c4)
l1_c2.add_child(l2_c5)
l2_c2.add_child(l3_c1)
l2_c2.add_child(l3_c2)
lca(root, 4, 6, [None])
lca(root, 8, 9, [None])
lca(root, 4, 5, [None])
lca(root, 4, 8, [None])
Pretty much the same as LCA of a BST, we just need to traverse all children.
- Alberto Munguia April 23, 2013Node LCA(Node a, Node b, Node root) { if(a == root || b == root) return root; int count = 0; Node temp = null; for(Node iter : root.children) { Node res = LCA(a, b, iter); if(res != null) { count++; temp = res; } } if(count == 2) return root; return temp; }