Microsoft Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

node* lowestInLevel(node* current) {
        int level = 0;
        node* root = current;
        while(root->parent != null) {
            root = root->parent;
            level++;
        }
	return findleftmostatlevel(root,level);
}
node * findleftmostatlevel(node * root,int level)
{
	if(level == 0)
		return root;
	if(!root->left && !root->right)
		return NULL;
	node * temp = findleftmostatlevel(root->left,level-1);
	if(temp)
		return temp;
	else
		return findleftmostatlevel(root->right,level-1);

}

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

I was also asked same Question week back by Microsoft but for rightside node....use level order traversal using queue

- sameer November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Interviewer also asked me to solve it without using queue/level order traversal by assuming each node hash PARENT pointer

- sameer November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that the total number of elements is N, we must avoid trying to go to the left because we will achieve O (N) running time. Instead, first i would find the root and in the same time i would count my depth level. Then i would try to traverse down by trying to peek on each step the most left node. This down traversal i would do until my depth is reached. Total running time would be O (log N)

- aurelian.lica November 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But that is not O(log N) in worst or average case. It is O(log N) in the best case only, although I do agree DFS is better on average than BFS.

In worst case the tree is linear and your node can be the last.

In general, your tree can still be inbalanced and you may have to traversal n/2 or n/3 nodes to find the answer.

- lepeisi November 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O (Log N) it's NOT the best case, it's the average case. The best case is O (1) if the tree is plat (all nodes has a single root, the root of the tree) and I have to perform only two steps to find out the left most node.

- aurelian.lica December 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The worst case will be O(N) because you are not travelling only path. Suppose first time you chose the left node but the depth of the node is h-2 that means the if your input node is in height h then you should chose the right node first.The way you solve is using recursion. That will end up using O(N) in worst case.

- Dinesh Pant December 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

how will you print the nodes on the same level as you don't have the root node? Is additional information missing such as the node also have pointer to the parent node?

- aka November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void lowestInLevel(Node current) {
        int level = 0;
        Node runner = current;
        while(runner.parent != null) {
            runner = runner.parent;
            level++;
        }
        int i = 0;
        while(count != i) {
            if(runner.left != null) 
                runner = runner.left;
            else
                runner = runner.right;
            i++;
        }
        System.out.println(runner);
    }

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

Hey..this will break if left subtree has height 3 and right subtree has height 5 and the input node is depth 5 node. Your loop will never go to depth 5.

- Dinesh Pant December 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void lowestInLevel(Node current) {
        int level = 0;
        Node runner = current;
        while(runner.parent != null) {
            runner = runner.parent;
            level++;
        }
        int i = 0;
        while(count != i) {
            if(runner.left == null && runner.right == null)
      throw new NoSuchElementException();
            else if(runner.left != null) 
                runner = runner.left;
            else
                runner = runner.right;
            i++;
        }
        System.out.println(runner);
    }

- Domanc November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* lowestInLevel(node* current) {
int level = 0;
node* root = current;
while(root->parent != null) {
root = root->parent;
level++;
}
return findleftmostatlevel(root,level);
}
node * findleftmostatlevel(node * root,int level)
{
if(level == 0)
return root;
if(!root->left && !root->right)
return NULL;
node * temp = findleftmostatlevel(root->left,level-1);
if(temp)
return temp;
else
return findleftmostatlevel(root->right,level-1);
}

- Amol December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* lowestInLevel(node* current) {
int level = 0;
node* root = current;
while(root->parent != null) {
root = root->parent;
level++;
}
return findleftmostatlevel(root,level);
}
node* findleftmostatlevel(node * root,int level)
{
if(level == 0)
return root;
if(!root->left && !root->right)
return NULL;
node * temp = findleftmostatlevel(root->left,level-1);
if(temp)
return temp;
else
return findleftmostatlevel(root->right,level-1);
}

- Amol December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleApplication45
{
    class Program
    {
        static void Main(string[] args)
        {
            // data for creating tree
            // This file contains a string of numbers separated by spaces
            string[] input_data = File.ReadAllText(@"G:\input.txt").Split(new char[] { ' ','\n','\r','\t'}, StringSplitOptions.RemoveEmptyEntries);
            if (input_data.Length == 0)
            {
                return;
            }
            Tree node = new Tree(); // creating of root
            bool is_head = true;
            // creating of tree
            for (int i =0; i< input_data.Length; i++)
            {
                // this case is needed to fill the root
                if (is_head)
                {
                    node.data = int.Parse(input_data[i]);
                    is_head = false;
                }
                else
                {
                    node = GrowingTree(node, int.Parse(input_data[i]));
                }
            }
            // Now we have a tree for test
            // Get node for test
            int test_counter =2;
            while (node != null && test_counter > 0)
            {
                node = node.right;
                test_counter--;
            }
            node = GetLeftMost(node);
        }
        static Tree GetLeftMost(Tree item)
        {
            int level = 0;
            if (item == null)
            {
                return null;
            }
            // Get root
            while (item.parent !=null)
            {
                item = item.parent;
                level++;
            }
            // Get left most
            while (level > 0)
            {
                // Left sub tree is not null
                if (item.left != null)
                {
                    item = item.left;
                    level--;
                }
                // Get right sub tree
                else {
                    item = item.right;
                    level--;
                }
            }

            return item;
        }
        static Tree GrowingTree(Tree node, int data)
        {
            if (node.data > data)
            {
                if (node.left != null)
                {
                    GrowingTree(node.left, data);
                }
                else
                {
                    node.left = new Tree(node, data);

                }
            }
            else
            {
                if (node.right != null)
                {
                    GrowingTree(node.right, data);
                }
                else
                {
                    node.right = new Tree(node, data);
                }
            }
            return node;
        }
    }
    class Tree
    {
        public Tree parent;
        public Tree left;
        public Tree right;
        public int data;
        // Constructors
        public Tree()
        { }
        public Tree(Tree in_parent, int in_data)
        {
            data = in_data;
            parent = in_parent;
        }
    }
}

- Trushnikov.Ivan December 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Worst case time complexity will be O(N) (for any type of a tree: complete binary tree (i.e. a heap), full binary tree, balanced or unbalanced tree, binary search tree, full binary tree etc.).

Universal solution:

1. Find the depth/height of the pointed node in the tree.

2. Perform a pre-order traversal over the tree. We return the first node we obtain at the depth/height obtained in the step 1.

- Aditya P January 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node findLeftMost(int data) {
		Queue<Node> q = new LinkedList<Node>();
		q.add(root);
		while (!q.isEmpty()) {
			Node temp = q.poll();
			if (temp != null) {
				if (temp.leftNode != null) {
					if (temp.leftNode.nData == data)
						return temp.leftNode;
					else {
						q.add(temp.leftNode);
					}
				}
				if (temp.rightNode != null) {
					{
						if (temp.rightNode.nData == data) {
							return temp.leftNode;
						} else {
							q.add(temp.rightNode);
						}
					}
				}
			}
		}
		return null;
	}

- akhil.gupta@imaginea.com January 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

with the tree..if you send 6 to your function it return Node 6. That is not what is expected from this question
1
/ \
2 3
/ \ / \
4 5 6 7

- Anonymous January 27, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.

private static Node Find( Node node ) {

    if ( node.Parent != null ) {
        _counter = _counter + 1 ?? 1;
        return Find( node.Parent );
    }

    return InOrder( node );
}

private static Node InOrder( Node node ) {

    if ( _counter == 0 || _counter == null ) {
        return node;
    }

    if ( node.LeftChild != null && !Visited.Contains( node.LeftChild ) ) {
        _counter--;
        return InOrder( node.LeftChild );
    }

    if ( node.RightChild != null && !Visited.Contains( node.RightChild ) ) {
        _counter--;
        return InOrder( node.RightChild );
    }
    Visited.Add( node );
    _counter++;
    return InOrder( node.Parent );
}

static readonly HashSet<Node> Visited = new HashSet<Node>();
private static int? _counter = null;

- zr.roman February 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void display_same_level(struct btree **b) {
deque< struct btree* > dtree;

if(*b)
dtree.push_back(*b);
int level=0;
int element_at_level=1;
while(!dtree.empty() ) {
struct btree* t = dtree.front();
cout << t->nodedata << " " ;
dtree.pop_front();
element_at_level--;
if(element_at_level == 0) {
level++;
}
if(t->left) {
dtree.push_back(t->left);
element_at_level++;
}
if(t->right) {
dtree.push_back(t->right);
element_at_level++;
}
}
}

- kbkunalb April 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First track the level of the node and add parent pointer in your tree structure.

static void LeftMostNodeSameLevel(Node myNode)
        {
            int level = 0;
            while (myNode.Parent!=null)
            {
                myNode = myNode.Parent;
                level += 1;
            }

            while (myNode!=null && level>0)
            {
                if (myNode.LeftNode != null)
                    myNode = myNode.LeftNode;
                else
                    myNode = myNode.RightNode;

                level-=1;
            }

                Console.WriteLine("Left Most Node is {0}",myNode.Value);
        }

- Neelavan April 06, 2017 | 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