Microsoft Interview Question Software Engineer / Developers


Country: India


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)
}

- Gautam on August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

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

This looks promising though.

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

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

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

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.

- devdeep1987 on September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- harsh.nitkkr09 on October 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sonesh on November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 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)

- IsAs on September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on September 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is this right? Or did I misunderstand?

Test case:

1 2 3 4 6 5 8 9 10

- Anonymous on September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Aleksey.M on September 25, 2012 | Flag
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

- Wolverine on October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Wolverine on October 13, 2012 | Flag
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.

- pks on August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

incorrect algo

- Anonymous on September 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cjmemory on September 29, 2012 | Flag
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.

- zeroByzero on August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- smallville on August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

again inserting can change the structure of tree

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

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.

- Anonymous on August 30, 2012 | Flag
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);
}

- srinichal on August 31, 2012 | Flag Reply
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.. :)

- rohitpandey710 on August 31, 2012 | Flag Reply
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.

- Anonymous on September 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

first of all your assumpiton is wrong

- t.deepak.iitg on September 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- jkwang on September 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
        }

- sachin on September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Andy on June 30, 2013 | Flag
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 );
}

- neo on September 18, 2012 | Flag Reply
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

- pandit on October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry faulty leaf node

- Anonymous on August 30, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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