Microsoft Interview Question


Country: India




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

its a simple n-ary tree traversal in two trees simultaneously and based on certain rules generate a new n-ary tree

- hinax June 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

enum Color { WHITE=0, BLACK=1, UNKNOWN=3 };
struct Item {
  Color color;
  Item* child_1;
  Item* child_2;
  Item* child_3;
  Item* child_4;
};

Item* GetOverlap(Item* root_1, Item* root_2) {
  if (!root_1 && !root_2)
    return NULL;
 
  Item* item = new Item;
  if (!root_1 || !root_2) {
    Item* root = root_1 ? root_1 : root_2;
    item->color = root->color;
    if (item->color == UNKNOWN) {
      item->child_1 = GetOverlap(root->child_1, NULL);
      item->child_2 = GetOverlap(root->child_2, NULL);
      item->child_3 = GetOverlap(root->child_3, NULL);
      item->child_4 = GetOverlap(root->child_4, NULL);
    }
  } else if (root_1->color != UNKNOWN && root_2->color != UNKNOWN) {
    item->color = root_1->color | root_2->color;
  } else {
   item->color = UNKNOWN;
   item->child_1=GetOverlap(root_1->color == UNKNOWN ? root_1->child_1 : root_1,
                            root_2->color == UNKNOWN ? root_2->child_1 : root_2);
   item->child_2=GetOverlap(root_1->color == UNKNOWN ? root_1->child_2 : root_1,
                            root_2->color == UNKNOWN ? root_2->child_2 : root_2);
   item->child_3=GetOverlap(root_1->color == UNKNOWN ? root_1->child_3 : root_1,
                            root_2->color == UNKNOWN ? root_2->child_3 : root_2);
   item->child_4=GetOverlap(root_1->color == UNKNOWN ? root_1->child_4 : root_1,
                            root_2->color == UNKNOWN ? root_2->child_4 : root_2);
  }
  return item;
}

- zprogd June 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is my logic

Assumptions:
A1. Start with root nodes of tree A and tree B, lets call overlap tree as O. We go recursively with each of these trees
A2. A quad tree representing a screen can either have 0 chidren or 4 children. It cannot have 1, 2 or 3 child ndoes.
A3. The 4 children of a given node are called nw, ne, se and sw (for four quadrants) 

Now at any given level
1. Check if any of node is null, if yes, copy the other screen's tree to O (if A == NULL, copy B to O else if B == NULL copy A to O) and return
2. Now we know, both A and B ae not NULL. Check if they have any color on them. If yes, they cannot have children. So no need to check for children if they have a color on them. If any one of them do not have a color and other is white or no color, then we need to recurse.
3. If color of root A is black or color of B is black, then mark O as black and return (because, no matter what is represented in subtree of non black node, it will be overlapped with a black node)
4. If both A and B are white, then mark O as white and return
5. If we reach here, we know, either one node or both nodes have no color marked. lets intiially check for one node white and the other "No color"
6. If A is white, it means, what ever is represented by sub tree B will be te overlapping screen so copy it and return (if A is white, copy B to O and return)
7. If B is white, then copy A to O and return
8. This means, both are having no color and so they have children,
	8.a recurse (A.nw, B.nw, O.nw)
	8.b recurse (A.ne, B.ne, O.ne)
	8.c recurse (A.se, B.se, O.se)
	8.d recurse (A.sw, B.sw, O.sw)

- CCoder July 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We may divide the problem into two parts:
(1)mix each subtree according to the colors of nodes
(2)try to concetrate those nodes whose children have same color.
Following is Code in C:

/*********************** definitions **************************/
#define SCREEN_DIVISION	4
enum Color{
	unknown,
	white,
	black	
};
typedef struct ScreenNode{
	Color color;
	struct ScreenNode* child[SCREEN_DIVISION];
} ScreenNode;
/********************** general function ***********************/
int isLeaf(const ScreenNode* p)
{
	if(!p) return false;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		if(p->child[i]) return 0;
	}
	return 1;
}
void freeChildren(ScreenNode* parent)
{
	if(!parent) return;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		if(parent->child[i]){
			free(parent->child[i]);
			parent->child[i] = NULL;
		}
	}
}
ScreenNode* cloneScreen(const ScreenNode* p)
{
	if(!p) return NULL;

	ScreenNode* t = (ScreenNode*)malloc(sizeof(ScreenNode));
	t->color = p->color;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		t->child[i] = cloneScreen(p->child[i]);
	}
	return t;
}
/******************* get overlapped screen *********************/
ScreenNode* mixLeafWithTree(const ScreenNode* leaf, const ScreenNode* tree)
{
	if(leaf->color == Color.black) return cloneScreen(leaf);
	else return cloneScreen(tree);
}
ScreenNode* overlap(const ScreenNode* a, const ScreenNode* b)
{
	if(!a) return cloneScreen(b);
	if(!b) return cloneScreen(a);

	if(isLeaf(a)) return mixLeafWithTree(a, b);
	if(isLeaf(b)) return mixLeafWithTree(b, a);

	ScreenNode* p = (ScreenNode*)malloc(sizeof(ScreenNode));
	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		p->child[i] = overlap(a->child[i], b->child[i]);
	}
	return p;
}
/********************* concentrate subscreen *********************/
int canBeConcentrated(const ScreenNode* parent)
{
/* In given condition: all children are leaves && all children has same color */
	if(parent->child[0] && !isLeaf(parent->child[0])) return parent;
	for(i = 1; i < SCREEN_DIVISION; ++i){
		if(!parent->child[0]) continue;
		if(isLeaf(parent->child[i]) ||
		   parent->child[i]->color != parent->child[i-1]->color
		) return 0;
	}
	return 1;
}
Color getConcentratedColor(const ScreenNode* parent)
{
/* In given condition: parent's color is first child's color */
	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		if(parent->child[i]) return parent->child[i]->color;
	}
	return Color.unknown;
}
ScreenNode* concentrate(ScreenNode* p)
{
	if(!p || isLeaf(p)) return p;

	int i = 0;
	for(; i < SCREEN_DIVISION; ++i){
		p->child[i] = concentrate(p->child[i]);
	}
	if(canBeConcentrated(p)){
		p->color = getConcentratedColor(p);
		freeChildren(p);
	}
	return p;
}

/********************** interface to outside ***********************/
ScreenNode* getOverlappedScreen(const ScreenNode* a, const ScreenNode* b)
{
	return concentrate(overlap(a, b));
}

- uuuouou June 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question: in case it is neither black nor white color, what value the node would carry?

- Jackie July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

null

- codewarrior August 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

struct Node{
  bool color;
  Node* child_1;
  Node* child_2;
  Node* child_3;
  Node* child_4;
};

Node* overlap(Node* root_1, Node* root_2) {
  if (!root_1 && !root_2)
    return NULL;
  
  Node* node = new Node;
  node->color = (root1 ? root1->color : false) |
                (root2 ? root2->color : false);
  node->child1 = overlap(root1 ? root1->child1 : NULL, 
                         root2 ? root2->child1 : NULL);
  node->child2 = overlap(root1 ? root1->child2 : NULL, 
                         root2 ? root2->child2 : NULL);
  node->child3 = overlap(root1 ? root1->child3 : NULL, 
                         root2 ? root2->child3 : NULL);
  node->child4 = overlap(root1 ? root1->child4 : NULL, 
                         root2 ? root2->child4 : NULL);
  return node;
}

- zprogd June 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I had a similar solution, can someone comment on this if this is correct...?

- HardCode June 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

this solution does not consider the condition when color is unknown.

- Vezita June 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

QuadTree. Quad. Quad.

Not Quadra.

Ok, carry on.

- Anonymous June 28, 2014 | 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