Microsoft Interview Question for Software Engineer / Developers


Country: United States




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

sg
1) does each node have link to its parent ?
2) what do you mean by "if all nodes of a tree are not given, return null". In you example all the nodes (A-F) are not in the list (FEA). Did you mean if the list contains a node that is not in the tree ?

- DarkKnight August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no, there is no parent link.
All the nodes are given. When I was working on it, I removed it by mistake.
i/p - B C F E A
o/p - A

- sg August 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i/ should contain "D" too correct ?

- DarkKnight August 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Possible Approach

Apply any tree traversal(in , pre ,post) while iterating through all nodes in list. The node whose traversal list is equal to size of input list and also has the largest size is the root else return null(some nodes may be missing in input list).

- rsrs3 August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can optimize above by maintaining a list/hash of already visited nodes that have parents in previous iterations and not iterating through these.

- Srilaxmi August 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If we use Hashtable, we can achieve O(n) complexity. Am I correct?

Traversal needs to be changed to refer/populate Hashtable.

- codealtecdown September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Approach should be that, first check for nodes whose node->left and node->right is NULL. Then make these node values as NULL, as these are lowest nodes in tree. Go on doing same. If the node count becomes one, then it is the root node.

- vishwajit kumar vishnu September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question is not complete!
It is not even said "it is BST"!!!? How can you answer by "left and right"?

- frash83 October 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.add all the given nodes to a Que,store the number of nodes given in separate variable
2.count the nodes of tree using recursion method by starting from each element on the Que
3.at any stage if count equals the total number of elements then that element is the root
4.else return null

- sj September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Take the next Tree Node from the list
2. if the Tree Node is not visited before 
2.1 flag it as visited (use a Hashtable for this)
2.2 root = Tree Node 
2.3 flag all child nodes in the Tree Node sub tree as visited
3. if there are more nodes in the list then go to 1
4. If list has less elements than the Hashtable //Some nodes from the tree were not given in the list
4.1 root = null //if all nodes are not given, return null
5. return root

//C#
static TreeNode GetRoot(List<TreeNode> nodes)
{
	if (nodes == null)
	{
		return null;
	}

	Hashtable visitedNodes = new Hashtable();
	TreeNode root = null;

	foreach(TreeNode currentNode in nodes)
	{
		if (!visitedNodes.Contains(currentNode))
		{
			//traverse subtree and flag nodes as visited
			Traverse(visitedNodes, currentNode);
			root = currentNode;
		}
	}
	if (visitedNodes.Keys.Count > nodes.Count)
	{
		root = null; //some nodes are not given
	}
	return root;	
}

//Traverse tree
static void Traverse(Hashtable visitedNodes, TreeNode currentNode)
{
	if (currentNode != null)
	{
		if (!visitedNodes.Contains(currentNode))//Avoid retraversal of subtrees already traversed
		{
			visitedNodes.Add(currentNode, null); //used just for searching so value is NULL
			Traverse(visitedNodes, currentNode.left);
			Traverse(visitedNodes, currentNode.right);
		}
	}
}

- IC September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is similar to finding the person who isn't a friend of anyone else. (A) will be the only node that isn't the child of another element.

- Matt M September 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Given a list of nodes of a tree, return the root. (you are given all nodes of tree)
def return_root_tree(lst):
num_children = {}
for node in lst:
root_helper(node, num_children)
# Now, num_children is filled with information of ( node : # of total children )
root = None
max_children = 0
for node in num_children:
if num_children[node] > max_children:
root, max_children = node, num_children[node]
return root


def root_helper(node, num_children):
if node not in num_children:
num_children[node] = 0
if not node.children:
num_children[node] = 1
return 1
for child in node.children:
num_children[node] += root_helper(child, num_children)
num_children[node] += 1
return num_children[node]

return num_children[node]

- Anonymous October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Given a list of nodes of a tree, return the root. (you are given all nodes of tree)
def return_root_tree(lst):
    num_children = {}
    for node in lst:
        root_helper(node, num_children)
    # Now, num_children is filled with information of ( node : # of total children )
    root = None
    max_children = 0
    for node in num_children:
        if num_children[node] > max_children:
            root, max_children = node, num_children[node]
    return root


def root_helper(node, num_children):
    if node not in num_children:
        num_children[node] = 0
        if not node.children:
            num_children[node] = 1
            return 1
        for child in node.children:
            num_children[node] += root_helper(child, num_children)
        num_children[node] += 1
        return num_children[node]

    return num_children[node]

- Anonymous October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Given a list of nodes of a tree, return the root. (you are given all nodes of tree)
def return_root_tree(lst):
    num_children = {}
    for node in lst:
        root_helper(node, num_children)
    # Now, num_children is filled with information of ( node : # of total children )
    root = None
    max_children = 0
    for node in num_children:
        if num_children[node] > max_children:
            root, max_children = node, num_children[node]
    return root


def root_helper(node, num_children):
    if node not in num_children:
        num_children[node] = 0
        if not node.children:
            num_children[node] = 1
            return 1
        for child in node.children:
            num_children[node] += root_helper(child, num_children)
        num_children[node] += 1
        return num_children[node]

    return num_children[node]

- kangkim9264 October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterate all the nodes from the list and for each node find the height of that node which ever node is having highest height that would be the root node. (Main root stays at largest height). Time complexity would be O(nloglogn) .

- Anonymous September 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: O(n) Space: O(1)

1) Let's take result = 0.
2) Now let's go over all nodes. In each node: result XOR node_index XOR all child indices.
As soon as root index should be only one, and other indices have pairs(self index + smb's child index) in the end result = root_index.

Check that answer is correct!
1. Check if result < total nodes
2. Throw away result index, and iterate with XOR again. Check if result == 0
If not => We have several nodes that are alone, tree is incomplete! => return null

- PGeorge September 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start with a set of all nodes. Scan the nodes in the list and remove the child nodes from the set. Eventually there will be only one element in the set which is the root if there is one tree. This is O(n) time/space.

- preparer2021 January 13, 2021 | Flag Reply


Add a Comment
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.

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