Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
This code will do find the path in one scan of the tree:
Please correct me if I have got something wrong.
struct state
{
int maxPathLength;
int amIinMaxPAth; // 0==> No , 1==> I am in the path, 2==> I am the center of the path
int currPathLength;
int maxWithoutCenter;
};
struct state findLongestWhitePath(struct treeDef *p1)
{
struct state leftStatus,rightStatus;
struct state curState;
curState.maxPathLength=curState.amIinMaxPAth=curState.currPathLength=0;
if(p1 != NULL)
{
leftStatus=findLongestWhitePath(p1->left);
rightStatus=findLongestWhitePath(p1->right);
if(p1-> left == NULL && p1->right == NULL)
{
// I am a leaf node..
if(p1->color == 'w' || p1->color == 'W')
{
curState.maxPathLength = curState.currPathLength=1;
curState.amIinMaxPAth=1;
}
else
{
curState.maxPathLength = curState.currPathLength=0;
curState.amIinMaxPAth=0;
}
return curState;
}
else
{
//This is black color
if(p1-> color == 'B' || p1-> color =='b')
{
curState.maxPathLength=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
curState.amIinMaxPAth=0;
curState.currPathLength=0;
}
else // This is white color
{
//This belong to maxPath
//1. If both of my child belong to max path
if(leftStatus.amIinMaxPAth == 2 && rightStatus.amIinMaxPAth == 2)
{
curState.amIinMaxPAth=2;// I am at the center...
curState.maxPathLength=leftStatus.maxWithoutCenter + rightStatus.maxWithoutCenter +1;
curState.currPathLength=curState.maxPathLength;
curState.maxWithoutCenter=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
}
else if(leftStatus.amIinMaxPAth == 2)
{
curState.amIinMaxPAth=0;
curState.currPathLength=leftStatus.maxWithoutCenter +1;
curState.maxPathLength=leftStatus.maxPathLength;
if(curState.currPathLength > curState.maxPathLength)
{
curState.amIinMaxPAth=1;
curState.maxPathLength=curState.currPathLength;
}
}
else if (rightStatus.amIinMaxPAth == 2)
{
curState.amIinMaxPAth=0;
curState.currPathLength=rightStatus.maxWithoutCenter +1;
curState.maxPathLength=rightStatus.maxPathLength;
if(curState.currPathLength > curState.maxPathLength)
{
curState.amIinMaxPAth=1;
curState.maxPathLength=curState.currPathLength;
}
}
else if(leftStatus.amIinMaxPAth == 1 && rightStatus.amIinMaxPAth == 1)
{
curState.amIinMaxPAth=2;// I am at the center...
curState.maxPathLength=leftStatus.maxPathLength + rightStatus.maxPathLength +1;
curState.currPathLength=curState.maxPathLength;
curState.maxWithoutCenter=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
}
//2. If any one of my child belong to maxPath
else if( leftStatus.amIinMaxPAth == 1 )
{
curState.amIinMaxPAth=1;
curState.maxPathLength=leftStatus.maxPathLength +1;
curState.currPathLength=curState.maxPathLength;
}
else if(rightStatus.amIinMaxPAth == 1)
{
curState.amIinMaxPAth=1;
curState.maxPathLength=rightStatus.maxPathLength +1;
curState.currPathLength=curState.maxPathLength;
}
else // None of my childs are in maxPath
{
curState.amIinMaxPAth=0;
curState.maxPathLength=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
curState.currPathLength=1+max(leftStatus.currPathLength,rightStatus.currPathLength);
if(curState.currPathLength > curState.maxPathLength)
{
curState.maxPathLength=curState.currPathLength;
curState.amIinMaxPAth=1;
}
}
//It does not belong to maxPath
}
}
}
return curState;
}
int main()
{
struct state length;
createBSTree();
length=findLongestWhitePath(root);
printf("\nLongest White Path Length Is:%d\n",length.maxPathLength);
return 0;
}
int whitenodes(node root, int max)
{
if(root == null)
return 0;
if(root.value == white)
{
int newmax = max(1+ whitenodes(root.right, max), 1+whitenodes(root.left,max));
if(newmax>max)
max = newmax;
}
else
newmax = 0;
return newmax;
}
answer will be in max (not newmax)
Doesn't work if one short path of nodes starts at the root of the tree and a longer one start somewhere deep inside the tree.
This modification seems to do the trick:
int whitenodes(TNode node, int max) {
if (node == null)
return 0;
int newmax = 0;
int right = whitenodes(node.right, max);
int left = whitenodes(node.left, max);
if (node.data == 1)
newmax = Math.max(1 + left, 1 + right);
else
newmax = Math.max(left, right);
if (newmax > max)
max = newmax;
return newmax;
}
This worked. Tested.
<code>
public static int solve(Node root) {
if (root == null) {
return 0;
}
int left = solve(root.left);
int right = solve(root.right);
if (root.color == 1) {
return 0;
} else {
int newmax = Math.max(left, right) + 1;
if (newmax > max) {
max = newmax;
}
return newmax;
}
}</code>
int search(node,flag)
{
val=val1=val2=0;
if(node.color=Black )
{
if(node->left != NULL)
val1=search(node->left,0);
if(node->right != NULL)
val2=search(node->right,0);
return max(val1,val2);
}
else
{
val=1;
if(node->left != NULL)
{
val+=search(node->left,1);
val1=search(node->left,0);
}
if(node->right != NULL)
{
val+=search(node->right,1);
val2=search(node->right,0);
}
if(flag=1)
{
return max(val1,val2);
}
else return max(val,val1,val2);
}
}
I don't think this works
I guess using flag you wanted to return longest white path till root inclusive when flag is 1 (here you are not returning 0 when root is black), and longest white path in subtree when flag is 0
the final value in global variable max is the answer.
static int max = Integer.MIN_VALUE;
private static int fn(Node root) {
if (root == null) return 0;
int l = fn(root.left);
int r = fn(root.right);
if (root.data % 2 == 1) {
int innerMax = l > r ? l : r;
if (innerMax > max) {
max = innerMax;
return 0;
}
}
return l + r + 1;
}
int Longesthpath(root, MaxPathInSubtree, MaxPathEndingAtNode) {
MaxPathInSubtree = 0;
MaxPathEndingAtNode = 0;
if(root == null)
{
return 0;
}
LongethPath(root->left, MaxPathInSubtree1, MaxPathEndingAtNode1);
LongethPath(root->left, MaxPathInSubtree2, MaxPathEndingAtNode2);
if(x is white)
{
MaxPathEndingAtNode = 1 + max( MaxPathEndingAtNode1, MaxPathEndingAtNode2);
}
else
{
MaxPathEndingAtNode = 0;
}
MaxPathInSubtree = max (MaxPathEndingAtNode, MaxPathInSubtree1, MaxPathInSubtree2);
if(max_so_far < MaxPathInSubtree)
max_so_far = MaxPathInSubtree;
}
Modification of well known graph problem of finding longest path in a directed acyclic graph (DAG):
- topologically sort the tree using dfs and throw away all black nodes
- perform linear backwards scan on the resulting list calculating max path of white nodes starting at particular vertex. Two nodes are considered adjacent in the list if they are adjacent in the original tree
This is very similar to the tree diameter problem: at any node the longest path may belong to a subtree or go through the node itself if it's white. Just track recursively the longest path of each subtree and the length of white-path ending at current node:
- KS December 11, 2012