Microsoft Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

inorder traversal of bst. Check if it's sorted. if not, the two nodes which are not fulfilling the criteria swap them

- Anonymous July 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why is this down voted?? This approach works

- IntwPrep December 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 9 vote

Use modified Inorder traversal.

correctBST(root)
{
	static Node* temp1,*temp2,*prev;
	static int found;
	if(root)
	{
		correctBST(root->left);
		if(!temp1 && prev && root->data<prev->data)
                {
			temp1=prev;
                        temp2=root;
                 }
		else if(prev && root->data<prev->data)
			temp2=root;
		else if(temp1 && temp2 && !found)
		{
			swap(&(temp1->data),&(temp2->data));
			found=1;
			return;
		}
		prev=root;
		correctBST(root->right);
	}
}

- Aashish July 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you explain the value of temp1 here?

if(!temp1 && prev && root->data<prev->data)

It is not initialized

- Harish July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

f(!temp1 && prev && root->data<prev->data)

pre is uninitilized pointer.....can u kindly modify this

- Anonymous July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Static variables are by default initialized by NULL.
See here: ideone.com/I39Ne

- Aashish July 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If NULL , then what would be prev->data in first call to the function ??

- dakshtalwar August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Before using prev->data, prev must not be NULL.
See the AND condition.

- Aashish August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There's no && in the second if though

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wonderful approach, few corrections and this work like a charm.

correctBST(root)
{
	static Node* temp1,*temp2,*prev;
	static int found;
        if(found) return;
	if(root)
	{
		correctBST(root->left);
		if(!temp1 && prev && root->data<prev->data)
			temp1=prev;
		else if(!temp2 && prev && root->data<prev->data)
			temp2=root;
		if(temp1 && temp2 && !found)
		{
			swap(&(temp1->data),&(temp2->data));
			found=1;
			return;
		}
		prev=root;
		correctBST(root->right);
	}
}

- AA August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think there is some problem with the code if you take the example

25
15 35
10 18 30 40

Now if you exchange 35 with 10 then the resultant tree would be


25
15 10
35 18 30 40
The given algo won't work for this example.

- Abhishank Sahu August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Abhishank Sahu, the algo is working well with the inut set given by you. Can you provide the link where it didn't give the correct output?

- Aashish August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not working! This will find the 1st node correctly, but will not always find the 2nd node
For instance consider this
5
/ \
4 6
/ \ \
1 2 7
temp1 will point to 2, and temp2 will point to nowhere!
Check carefully!

- Anshu Kumar August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anshu Kumar, thanks for pointing out the mistake.
I have corrected the code.

- Aashish August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a minor problem in the code . this doesnt work when the left child of any left subtree has been swapped. For example:
5
/ \
4 6
/ \ \
7 2 1

the code posted by AA it still doesnt work. A slight modification to AA's code will rectify it:

correctBST(root)
{
	static Node* temp1,*temp2,*prev;
	static int found;
        if(found) return;
	if(root)
	{
		correctBST(root->left);
                  //to handle the case when a left child of a left subtree  is swapped
                 if(!prev)
                         prev = root -> left
		if(!temp1 && prev && root->data<prev->data)
			temp1=prev;
		else if(!temp2 && prev && root->data<prev->data)
			temp2=root;
		if(temp1 && temp2 && !found)
		{
			swap(&(temp1->data),&(temp2->data));
			found=1;
			return;
		}
		prev=root;
		correctBST(root->right);
	}
}

- blah123 November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It wont work for tree where 40 & 60 are swapped
50
/ \
25 75
/ \ / \
12 60 40 100
\ / \
18 80 105
/ \
15 90

- Girish December 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

// Correct a BST where two nodes are swapped
void GetDeviants(Node* root, int nMin, int nMax, __out std::vector<Node*>* prgDeviants)
{
	if (nullptr == root)
	{
		return;
	}
	if (nullptr != root->left)
	{
		GetDeviants(root->left, nMin, root->val, prgDeviants);
	}
	if (nullptr != root->right)
	{
		GetDeviants(root->right, root->val+1, nMax, prgDeviants);
	}
	if ((root->val < nMin) || (root->val > nMax))
	{
		prgDeviants->push_back(root);
	}
}

void CorrectBST(Node* root)
{
	std::vector<Node*> rgDeviants;
	rgDeviants.reserve(2);
	GetDeviants(root, -INFINITY, INFINITY, &rgDeviants);
	ASSERT(2 == rgDeviants.size());
	std::swap(&(rgDeviants[0]->val), &(rgDeviants[1]->val));
}

- Saranya July 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey can you share more questns of microsoft interview??? the questions of personal interview

- coder August 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node Tree;
Tree *new_node(int data)
{
  Tree *node = (Tree *)malloc(sizeof(Tree));
  node->data=data;
  node->left=NULL;
  node->right=NULL;
  return node;
}
void make_tree(Tree **root,int data)          // constructing tree
{
     if(*root==NULL)
     { 
      *root = new_node(data);
     }
     else
     {
        if(data>(*root)->data)
        {
           make_tree(&(*root)->right,data);
        }
        else
        {
           make_tree(&(*root)->left,data);
        }
     
     } 
}
int arr[5];                // storing inorder traversal into global array so it can reflect in our main
void inorder(Tree *root)
{
  static int i=0;      
  if(root==NULL)
    return;
  inorder(root->left);
  arr[i++]=root->data;
  cout<<root->data<<"\t";
  inorder(root->right);  
}
int main()
{
Tree *head=new_node(5);      // making tree as per given condition
head->left=new_node(3);
head->right=new_node(4);
head->left->left=new_node(2);
head->left->right=new_node(6);
inorder(head);
cout<<endl;
int count=0,index1,index2;

for(int k=0;k<4;k++)         // finding position of swap indexes in an array
 {
  if(arr[k]>arr[k+1] && count==0)
   { index1=k; count++;}
  if(arr[k]>arr[k+1] && count==1)
    index2=k;
} 
int temp=arr[index1];              // swap those values
arr[index1]=arr[index2];
arr[index2]=temp;
head=NULL;     // again reconstructing
for(int k=0;k<5;k++)
 make_tree(&head,arr[k]);
 
inorder(head); 
getchar();
return 0;
}

- saurabh December 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

swapping data enough or nodes should be swapped?

- Anonymous July 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Traverse the whole tree to find the two parents(victim) where the lft child> rt child. Having the pntr to this parent, swap the two child(wrong one). Hope the idea works..

- Avenger July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

let take below case
       55
  30     50

here 55 & 50 are swapped, in this case there is no childs for 50... here does your logic works?

- Anonymous July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

swap the data... and the two nodes can be anywher in the tree..not only parent child..

- amnesiac July 28, 2012 | 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