## Microsoft Interview Question for Software Engineer / Developers

Country: India

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

Create a stack and start inserting the nodes of BST in stack in in-order fashion

if elt/node that we are going to insert is larger than stack top, pop the top node and push the elt/node

else push the elt/node

Finally swap the values of first and last nodes in Stack (After the traversal stack will have two elements if adjacent numbers are swapped and stack will have three elements if non-adjacent numbers are swapped)

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

this is best so far. some optimizations like -:
we can stop early
I.e after finding first anamoly using your method (anamoly is "number whose next number is smaller than the itself", no need of Stack just variable could do).
Now we just have to traverse to find the number's position whose next number is bigger than anamoly number

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

Is this right? Or did I misunderstand?

Test case:

1 2 3 4 6 5 8 9 10

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

Yep, the mentioned algo is not absolutely correct.
E.g. it shouldn't do pop(top) - push(current) in case of (there are more than one element in the stack and current.data > top.data). Otherwise the stack won't contain swapped elements at the end of the BST traversal procedure.

Comment hidden because of low score. Click to expand.
2
of 4 vote

``````int
buggynode1(node* root,int min,int max)
{
int left=0;
int right=0;

if(root)
{
if(root->data<min) return root->data;
if(root->data>max) return root->data;

left=buggynode1(root->left,min,root->data);
if(left) return left;

right=buggynode1(root->right,root->data,max);
if(right) return right;
}
return 0;
}

int
buggynode2(node* root,int min,int max)
{
int left=0;
int right=0;

if(root)
{
if(root->data>max) return root->data;
if(root->data<min) return root->data;

right=buggynode2(root->right,root->data,max);
if(right) return right;

left=buggynode2(root->left,min,root->data);
if(left) return left;
}
return 0;
}

void
swapBuggy(node* root, int buggy1,int buggy2)
{
if(root)
{
if(root->data==buggy1 || root->data==buggy2)
{
root->data=root->data^buggy1^buggy2;
}
swapBuggy(root->left,buggy1,buggy2);
swapBuggy(root->right,buggy1,buggy2);
}
}

int
main()
{
int tmp1=buggynode1(root,INT_MIN,INT_MAX);
int tmp2=buggynode2(root,INT_MIN,INT_MAX);

swapBuggy(root,tmp1,tmp2)
}``````

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

i have codophobia :) ,can u plz explain the approach?

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

I too am unwilling to invest time in reading code when I know that statistically speaking 80% of the answers on this site are incorrect

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

This looks promising though.

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

What if both nodes are on the same side of the tree?

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

it does not work if root is one of the buggy nodes.
Test with:
3(root)->left=2; 3->right=null
2->left=1(leaf), 2->right=5(leaf)
Here 3 and 5 need to be swapped but the code cannot find 3.

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

function buggynode1 and buggynode2 will return same element.
hence solution is wrong

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

and it is also not necessary that you will find two buggy node always, there are many cases where you can only able to identify single buggy node.
consider the case when a node is replace with one of it's decedent

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

Don't know if this logic works for all test cases:

1. Find In order traversal of the tree.
2. In the inorder traversal, from left to right, find the first node which is misplaced(A misplaced element is one which is greater than its right element in the inorder matrix).
3. Now taking the element found in step two, traverse inorder array from left to right, and find the first element which is less than the element found in step two.

So the in actual implementation, for step two we traverse tree in order two find the node.
And two find the second node in step three we traverse in reverse inorder.

Example:
Actual tree inorder : 2,5,7,8,10,12,14
Disorder Tree inorder : 2,8,7,5,10,12,14(5,8 are swapped)

In step two we find 8 (As the right element 7 is less than 8)
Now in step three we find 5 which is the first element found which is less than 8.

Correct we if my logic is wrong

Comment hidden because of low score. Click to expand.
2

Correction : In step 3 we actually traverse array from right to left not left to right

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

Start with inorder traversal, keep a reference of current and old node. The moment you find out-of-order numbers, swap the values.

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

This method is incorrect because the swapped nodes are not necessarily adjacent in an in-order traversal.

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

incorrect algo

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

This is correct answer. If you could not understand it, please don't say it's wrong.

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

store inorder traversal of tree in an array and sort it ,and again do inorder traversal and insert value from sorted array to tree .
the method posted by PKS may not work.

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

The two nodes swapped may not be adjacent to each other in inorder traversal. Instead when you find a node that is out of order do a binary search for the correct position of the node and swap with that node.

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

again inserting can change the structure of tree

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

No, this works. The tree structure won't be changed. After the array is sorted, an in-order traversal of the tree will be done, and the i-th node in the in-oirder traversal will get the i-th value from the array. The problem here is that 1) you are using extra space (no one said you couldn't, but still); 2) sorting is O(NlogN) whereas this problem can be solved in O(N); and 3) even if you realize that you should use insertion sort because the list is almost sorted and end up with an O(N) sort here (since only O(1) elements are out of order), you're still doing 2 tree traversals, writing to an array, and doing an insertion sort when it's possible to solve this problem with just one tree traversal.

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

void Tree::GetMaxMin(TNode* node,int *cmp,bool flag)
{
if(node == NULL) return;
if(flag)
*cmp = *cmp > node->val?node->val:*cmp;
else
*cmp = *cmp < node->val?node->val:*cmp;
GetMaxMin(node->left,cmp,flag);
GetMaxMin(node->right,cmp,flag);
}

void Tree::swap(TNode* node,int min,int max)
{
if(node==NULL) return;
if(node->val == min || node->val == max)
node->val = node->val==min?max:min;
swap(node->left,min,max);
swap(node->right,min,max);
}

void Tree::BSTNormal(TNode* node)
{
if(node==NULL) return;
int max = node->val;
int min = node->val;
GetMaxMin(node->left,&max,0);
GetMaxMin(node->right,&min,1);
if(min < max)
swap(node,max,min);
else if(node->val <= max)
swap(node,node->val,max);
else if(node->val >= min)
swap(node,node->val,min);
BSTNormal(node->left);
BSTNormal(node->right);
}

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

tarverse the tree in inorder nd preorder way nd store in two arrays.. now check for the incorrect number in inorderly filled array(as can be easily seen b'coz number must be sorted) and den swap dese two values in both tha arrays i.e. inorder traversed array and preoder traversed array.. and then using two traversal its easy to create the tree with the same structure as that of before..
p.s. two traversal are required just to maintain the structure or else only one can also work.. :)

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

Assumption: the swapped nodes are breaking the BST features of the tree.

Step 1: Find two BST violated nodes using modified isBST() testing routine. Please check the isBST() method.
Step 2: Swap the content of those two nodes.

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

first of all your assumpiton is wrong

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

This should work. But just swapping the nodes content wouldn't work instead the subtree of faulty node and its children should be considered before swapping the nodes.

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

This will not work because you cannot always find only two nodes that violate BST rule. Consider the tree below:

8
/ \
5 12
/ \ / \
2 7 10 14

Swapping 8 and 10 gives us:

10
/ \
5 12
/ \ / \
2 7 8 14

Which two violate? 8 and 10? Then how about 12?

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

The method works. Consider the isBST calls when we are traversing the right sub tree.
assume isBST (Tree, min, max);
For node 12, we get isBST (T, 10, INT_MAX); which is ok for 12
For node 8, we get isBST(T, 10, 12); which is not ok, as 8 < 10 (min). so we set the 2 nodes to be swapped as 8, 10.

In cases, if the swapped nodes belong to left and right subtrees, then isBST will encounter such anomaly twice , and we can simply set the nodes to be swapped as the nodes that caused those anomalies.

``````// Set the swapNodes[0] = swapNodes[1] = -1
if (data < min || data > max)
{
if (swapNodes[0] == -1)
{
swapNodes[0] = data;
swapNodes[1] =  data < min ? min : max;
}
else
// We encountered second anomaly in the isBST.
swapNodes[1] = data;
}``````

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

This will fail for below test case where nodes 5 and 12 are swapped.
8
10 12
2 7 5 14

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

is it right?? plzzz comment

typedef struct node *NODEPTR;
void tree(NODEPTR root)
{
NODEPTR p=NULL, j=NULL;
if(root==NULL)
return;
else if(root!=NULL && (j==NULL || p==NULL))
{
if( root->left != NULL && root->info < (root->left)->info )
j = root->left;
if( root->right != NULL && root->info >= (root->right)->info )
p = root->right;
tree( root->left );
tree( root->right );
}
swap( j->info , p->info );
}

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

Do an in order element ...
misplaced element will be 2 elements
[1] one element will be greater than both of it's left and right
[2] 2nd element will be less than both left and right
Swap above 2 elements

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

how will you test the above condition for a faulty root node

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

sorry faulty leaf node

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.

### 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.

### 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.

### 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.