Microsoft Interview Question Software Engineer in Tests


Country: United States


Comment hidden because of low score. Click to expand.
3
of 3 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;
	}

- Alberto Munguia on April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- aakimpossible on September 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- dabbcomputers on April 24, 2012 | Flag Reply
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))
                    {
                        ancestors.Add(this);
                        return true;
                    }
                }
            }

            return false;
        }
    }

- me on May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the time complexity of this??

- ruth542 on March 05, 2013 | Flag
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.

- Anonymous on May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you show an implementation of this?

- ruth542 on March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

two stacks. push ancestor's from both the trees in two stacks. pull until different encounter or one of the stacks is empty. last pull is the answer.

can someone help with the complexity?

- Flag on August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- me on May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its n-ary. Not binary tree not even binary search tree.

- Psycho on October 22, 2013 | Flag
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)

- iman.goodarzi on March 07, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More