## Microsoft Interview Question Software Engineer in Tests

• 0

Given an n-ary tree, find the closest common ancestor ? Discuss the time complexity and write testcases.

Country: United States

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

http{://}community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

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

``````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))
{
return true;
}
}
}

return false;
}
}``````

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

what is the time complexity of this??

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

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.

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

can you show an implementation of this?

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

Lowest Common Ancestor

{
{
}
{
}
else
}

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

if not having parent pointers: O(n) + O(h) = O(n)
if having parent pointers: O(h)

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

Pretty much the same as LCA of a BST, we just need to traverse all children.

``````Node 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;
}``````

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.