Microsoft Interview Question for Software Engineer / Developers






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

???. Binary Search O(lg(n))?? I c no reason why doubly LL.
Please clarify the questions.

- T December 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think question is very clear.It was asked in MS interview when it visited our campus last yr.We find the hight of a BST.Now the variation is, if leafs of that tree are connected to each other.so that from one leaf, we can go to next leaf... so for such tree, find the height of the node

- richa.cseit December 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

OK. I C. since the right and left child has been occupied. The leaf node can't be determined as usual.

Solution: DFS, leaf node condition node->left->right == node || !node->left && !node->right || node->right == last visitleaf && !node->right

Is the last element in the DLL connect to the head? otherwise, third condition not need

If not,

- T December 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think .. current ->left->right = current.. if it holds gud then the current will be leaf.
this only is sufficient.

x is value of the node whose hight, we need to know
root is the root of the BST
int level ( node * root, int x)
{
static int level = 0;
if ( root == NULL)
{
level = -1;
return level ; }
else if ( root->val == x)
{ level = 0;
return level ; }
if( roo->left)
{
if ( root->left->right == root)
level = -1;
else
level = (root->left)? level(root->left) ;
if(root->right)
{
if ( root->left->right == root)
level = -1;
else
level = level( root->right);
}

- richa.cseit December 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So you need to further clarify, what means a node is given.
Just use Binary search with similar leaf node condition first, if you mean by a value.

Then DFS.

- T December 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What we know the answer for hight of tree has leaf node no link to other node, so This algo wont work in case of leaf node is pointing to other leaf node ,
So we need to explore new algo in this context(Leaf is poitnig to other leaf).

- Anonymous December 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think .. current ->left->right = current.. if it holds gud then the current will be leaf.
this only is sufficient.

x is value of the node whose hight, we need to know
root is the root of the BST
int level ( node * root, int x)
{
static int level = 0;
if ( root == NULL)
{
level = -1;
return level ; }
else if ( root->val == x)
{ level = 0;
return level ; }
if( roo->left)
{
if ( root->left->right == root)
level = -1;
else
level = (root->left)? level(root->left) ;
if(root->right)
{
if ( root->left->right == root)
level = -1;
else
level = level( root->right);
}

- richa.cseit December 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@richa
I think,Question looks root node is not given.
Only one node is given, u have to find its hight.

- nks December 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

where u r increasing the level of the nodes??

- saurabh December 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yea.. i missed one small part.we have to append following:

if ( level !=-1)
level++;
return level;

- richa December 21, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess we can use a trick here: when we reach a leaf node, even though its next node (left child or right child) is another leaf, the parent node of the next leaf node is not the current leaf node. By doing so, we know if it is a leaf node or not and the height can be identified easily.

- Anonymous January 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question doesn't specify that the pointer to the root is given. Some arbitrary node's pointer is given. So, I don't see how the above codes work.

- Anonymous January 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

guys, the height is logn, n - the number of leafs.

it's pretty clear that we can't use DFS or whatever because we're only supposed to use the LL!
if we divide by 2 untill we get 1 then we'll get the height.
actually we get a little more than the height.
this is only optimized if the tree is a full tree (each node has either no sons or 2 sons).
but it's a very good estimation no matter how you look at it (save O(n) that is :D)

- Anonymous January 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If pointer to the root is given then we can use BFS as well

- abhimanipal March 19, 2010 | 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