Microsoft Interview Question for Software Engineer in Tests






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

void mirror(Struct node *root)
{
  if (root == null)
      return;

  mirror(*root->first);
  mirror(*root->secord);
             .
             .
             .
  mirror(root->nth);

  swap(root->first, root->nth);
  swap(root->second, root->(n-1)th);
     .
     .
     .
  swap(root->(n/2)th, root->(n/2+1)th);
 }

- tetura June 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

does mirror image mean... left children to the right and vice-versa

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

does mirror image mean... left children to the right and vice-versa

- sangi.v.g June 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sangi.v.g, Draw yourself a tree on the paper, show it perpendicularly to a mirror and find out for yourself :)

- Nix June 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void mirror(struct node* node) {
if (node==NULL) {
return;
}
else {
struct node* temp; // do the subtrees
mirror(node->left); mirror(node->right); // swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}

- seeker7 June 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@smritedua - Its for a Nary tree, not binary

Tnode MirrorTree(TNode tnode)
{
	// Don't do anything if the number of children is less than one
	if(tnode.Children.Count < 2) return tnode;
	// else push the children into a stack and set that as children
	List<TNode> children = tnode.Children;
	List<TNode> stack = new List<TNode>;
	foreach(TNode t in children){
		stack.insertAt(0,MirrorTree(t));
	}
	t.Children = stack;
	children = null;
	return tnode;
}

- sorcerer June 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorcerer, your solution looks pretty good..

- Anonymous June 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u explain ur code and logic again.

- seeker7 July 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The function returns a node if it has less than 2 children. What if it had just one child, which in turn had more than 2 children? There's no way for recursion to reach that node, is there?

- Natthu January 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is just postorder traversal but except that we swap the child nodes instead of printing the parent's value. Guess seeker7's code works fine.

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

no it is valid only for binary,not n-ary

- seeker7 July 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

though seeker7 code is for a binary tree , but it can be extedended for to work for n-ry tree

use the same logic as in post1

mirror(*root->first);
mirror(*root->secord);
.
.
.
mirror(root->nth);



swap(root->first, root->nth);
swap(root->second, root->(n-1)th);
.
.
.
swap(root->(n/2)th, root->(n/2+1)th);

- pk July 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mirror_N_ary(node *root)
{
I = 0;
// push all the children on to stack

If(root == NULL)
Return(NULL);
Temp = ALL;
Temp->data = root->data;

Temp->first = Mirror_N_ary(pop());
Temp->second = Mirror_N_ary(pop());
And so.on.

Return(temp);
}

- nagpal_dce August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void mirrorImageOfntree<T>(nNode<T> head)
{
if (head == null) return;
int i = 0;
int j = head.Children.Length - 1;
while (i < j)
{
nNode<T> temp;
temp = head.Children[i];
head.Children[i] = head.Children[j];
head.Children[j] = temp;
i++;
j--;
}
foreach (nNode<T> node in head.Children)
{
mirrorImageOfntree<T>(node);
}

}
//class that represents a node in n-Tree
class nNode<T>
{
public nNode(int children, T value)
{
this.children = new nNode<T>[children];
this.value = value;
}
nNode<T>[] children;
T value;
public nNode<T>[] Children
{
get{return children;}
}
public nNode<T> this[int index]
{
get{ return this.children[index];}
set{children[index] = value;}
}
}

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

stack method as well as post1 method both are pretty much the same

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

Assuming that the children are stored using the right sibling pointers, I think we can just reverse the children linked list in each and every node.

Is this approach okay?

- Balaji September 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will doing BFS at every level from right child to left child help?

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

typedef struct nodeT
{
	node* child[MAX];
	int data;
}node;

void mirroImageNaryTree(node* root)
{
	if(root == null)
	
	while(int i=0; i< max; i++)
	{
		if(root->child[i] == null)
			continue;
		if(root->child[i] != null)
			mirroImageNaryTree(root->child[i]);
	}
	
	reverseChildren[root->child];
}

void reverseChildren(node* child[])
{
	start = 0;
	end = MAX;
	
	while(start < end)
	{
		node* temp = child[start];
		child[start] = child[end];
		child[end] = temp;
	}

}

- dumbass January 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the n-ary tree by BFS and at each level reverse the children in the parent by swapping before inserting them in the stack.

- Ashish Kaila March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done using DFS procedure with a little modification:
(Assume the color of all nodes intially is WHITE)
Time complexity: O(n)
Space complexity: O(1)

void mirrortree(node* root)
{
  if(root==null) return;
  int numch = root->numchildren;
  root->color = GREY;
  for(int i=0;i<numch;i++)
  {
    if(root->next[i]->color==WHITE)
      mirrortree(root->next[i]);
  }
  root->color=VISITED;

  // now start swapping child nodes of this tree to convert it to mirror
  int min=0, max=numch;

  while(min<max)
  {
     node* tmp = root->next[min];
     root->next[min] = root->next[max];
     root->next[max] = tmp;
     min++;max--;
  }
}

- Rochak June 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Clean and Correct solution...Cheers!!!

typedef struct treeNode
{
  int data;
  listNode* childrenListHead;
} treeNode;

typedef struct listNode
{
  treeNode* node;
  listNode* next;
} listNode;

void reverseList(listNode* &head)
{
  if(!head || !head->next)
    return;
  listNode* rest = head->next;
  reverseList(rest);
  head->next->next = head;
  head->next = NULL;
  head = rest;
}

void mirror(treeNode* root)
{
  if(!root)
    return;
  listNode* n = root->childrenListHead;
  while(n)
  {
    mirror(n->node);
    n = n->next;
  }
  reverseList(root->childrenListHead);
}

- Avinash October 12, 2012 | 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