Bazaarvoice Interview Question
Software Engineer / DevelopersWhat does start of cluster mean? You could have more than three nodes in a cluster? Guessing that cluster is just the largest sub-tree with the same coloured node.
Yep thats right, as mentioned when root, left and right have same colored node it is a start of cluster, it will end when you encounter different color node in your tree traversal algorithm.
In which case the recursive solution posted above would almost work.
Once you have the number of clusters for the left sub-tree and right sub-tree, you need to consider a few (but constant) cases when you compute the number of clusters for the whole tree.
// Recursive solution
// No error checking. For instance t.Left being null etc.
FindNumClusters(Tree t) {
int left = FindNumClusters(t.Left);
int right = FindNumClusters(t.Right);
if (t.Left.Color == t.Right.Color) {
if (t.Color == t.Left.Color) {
return left + right -1;
} else {
return left + right + 1;
}
}
return left + right;
}
That algorithm may work, but the can't the check for current node being the start of a cluster not be done first? The algorithm would just be a check for cluster, and if so, go left, go right. until cluster end, increment cluster count. If no cluster (cluster end), go left, go right to find the next cluster.
That way, there would not be the obfuscatory math in the algorithm, and it would have that classic 'recursive look'. Although, it probably wouldn't be any more readable, just like all simple recursive algorithms that don't make sense until stared at for a while.
Looking at it again, your solution (the first one), would probably be a little cleaner. It just goes all the down, then the recursive unwind subtracts out the clusters that are part of a larger cluster.
My way would have involved logic to determine the end of a cluster, which would have been slightly more complex than just recursively subtracting.
A little confused about Cluster Definition, how many Clusters in this tree, one or three?
R
R R
R R R R
R
B R
B B R
This tree has 1 oder 2 clusters? In intuitive understanding I would say two clusters (1 red, 1 blue). The Description says only one clusters, 'cause the red-path is only right-handed.
The intuitiv definition of cluster is easy: do a DFS on the tree and count the number of color-changes.
Solve this recursively.
- Anonymous August 17, 20111) findCluster(root.left)+findCluster(root.right)
2) check if root itself has a cluster.
3) return clusterCount.