Microsoft Interview Question for Software Engineer in Tests


Team: Windows Live
Country: United States




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

int Height(Tree t) {

int height = -1;

if(t != NULL) {

std::list<Tree> q; //Queue to store tree nodes

q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level

while(!q.empty()) {

TreeNode *node = q.front();
q.pop_front();

if(node == NULL) {//delimeter encountered, increase height and push NULL if q not empty

height++;

if(!q.empty())
q.push_back(NULL);

}
else {

if(node->left)
q.push_back(node->left);

if(node->right)
q.push_back(node->right);
}

}

}

return height;
}

- cinderella October 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is the code gonna work for a linked list??

- Anonymous December 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Initialize a depth variable to 1. Do a traversal from the root, incrementing the variable by 1 every time you go from a parent node to a child node and decrementing the variable by 1 every time you go from a child node to a parent node. Every time you increment the variable, check to see if it's greater than a maxDepth variable, and if so, update maxDepth.

- eugene.yarovoi October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Let OPT[i] = height at i th node in the tree

The recurrence relation would be
OPT[i] = Max{OPT[2i]+1, OPT[2i+1]+1}

so a iterative solution for above would be,

int depth(int *tree){
for(int i=1; i<n; i++){ //I am assuming my tree is in a array
if(2i < m && 2i+1 < n)
OPT[i] = 0; //If this is a leaf then height at that node is 0
}

for(int i=n; i>=1; i--){
OPT[i] = max(OPT[2i]+1, OPT[2i+1]+1);
}

return OPT[1]; //The root of the tree is at tree[i] and dept for that node is
// at OPT[1]
}

- Nikhil Rajguru October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

BFS, which does a level order traversal. while inserting in the queue use std::pair< Node *, int > rather than the NODE* alone, this would give us the level of the currently de-queued node and enable us to calculate the next level for its children

- subramanian.ganapathy86 January 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is first and second in the above code??

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

can be solved in o(n) time using - iterative implementation of post-order traversal.

- azhilprashanth87 November 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is it not max level = max depth, use level order traversal which is an iterative procedure use Q and easily figure out the max level.

- Doctor.Sai December 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

typedef std::pair<Node*,int> NodeLevelPair_t;
int getMaxDepth( Node* root )
{
	int maxDepth = 0;

	if ( root  )
	{
		std::queue< NodeLevelPair_t > q;
		q.push( NodeLevelPair_t( root , 1 ) );

		while ( ! q.empty() )
		{
			NodeLevelPair_t curNode = q.front();
			q.pop();

			if ( curNode.second > maxDepth )
				maxDepth = curNode.second;

			if ( curNode.first->left != NULL )
				q.push( NodeLevelPair_t( curNode.first->left , curNode.second + 1 ));

			if ( curNode.first->left != NULL )
				q.push( NodeLevelPair_t( curNode.first->left , curNode.second + 1 ));

		}
	}

	return maxDepth;
}

Assuming Tree is a object Node* with left and right ptrs

- Anonymous October 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

int finddepth(Node root, int depth)
{
if(!root)
{
return depth;
}
int depthleft = finddepth(root->large,depth+1);
int depthright = finddepth(root->small,depth+1);
return (depthleft>depthright?depthleft:depthright);
}

- Vasu October 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What part of "iteratively" did you know understand ?

- Anonymous October 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

:) sorry missed the second line

- Vasu October 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Any recursive program can be converted to iterative one. Left as an exercise to the compiler :-)

- Anonymous October 31, 2011 | Flag


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