Microsoft Interview Question
Country: India
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;
}
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)
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));
}
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;
}
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