National Instruments Interview Question
Software Engineer / Developersint colorCode (struct node* root) {
if (root == NULL)
return 0;
if (root->left != NULL && root->right != NULL) {
if (root->left->color == root->color && root->right->color == root->color)
return (colorCode(root->left) + 1 + colorCode(root->right));
else
return (colorCode(root->left) + colorCode(root->right));
}
else
return 0;
}
Here is a psuedo code:
int ReturnClumps(List* head)
{
if (head == null )
{
if(FormsClumps(head))
return 1;
else return 0;
}
else
{
if(FormsClump(head))
return 1 + ReturnClumps(right.child) + ReturnClumps(left.child);
else
return ReturnClumps(right.child) + ReturnClumps(left.child);
}
}//End ReturnClumps()
boolean FormsClump(List* head)
{
if(head.RightAdjacent.color == head.color && head.LeftAdjacent.color == head.color)
return 1;//forms clump
else
return 0;
}//End FormsClumps()
PS: Please correct if wrong.:)
head being NULL will cause segmentation fault in FormsClump. Here we are trying to access NULL pointer.
head being NULL will cause segmentation fault in FormsClump. Here we are trying to access NULL pointer.
could u explain the ques plz? bcoz u r saying that more than three colors are adjacent then a clump is formed, and everybody only checking the color of root and their left and right child, it is not more than 3 they are checking for 3 colors, how we check for more than 3?
use a stack to keep track of the last node. Not move down (to the left/right) and check if the colors of the current node's left and right children AND the color of the node int the TOP of the stack are different. Call the function recursively, incrementing the value if you find a clump.
typedef _Tree{
- deerwish March 05, 2012int color;
bool clump; //indicate if it is already a clump or not
TreeNode *lchild;
TreeNode *rchild;
}TreeNode, pTree;
static int clumps;
void BiTreeClumps(pTree T){ //Postorder traversal
if(!T) return;
else{
BiTreeClumps(T->lchild);
BiTreeClumps(T->rchild);
if(T->lchild->color == T->rchild->color && T->lchild->color == T->color && T->lchild->clump != true && T->rchild->clump != true){
T->clump == true;
clumps++;
}
else if(T->lchild->color == T->color && T->lchild->clump == true)
T->clump = true; //doesn't count
else if(T->rchild->color == T->color && T->rchild->clump == true)
T->clump = true; //doesn't count
}
}