Bazaarvoice Interview Question for Software Engineer / Developers






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

Solve this recursively.

1) findCluster(root.left)+findCluster(root.right)
2) check if root itself has a cluster.
3) return clusterCount.

- Anonymous August 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What 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.

- Anonymous August 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

// 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;
}

- Anonymous August 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous September 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous September 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A little confused about Cluster Definition, how many Clusters in this tree, one or three?

R
       R       R
     R   R    R  R

- lct8712 August 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That is one, I believe.

- Anonymous August 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do an DFS on this Tree...Return count of connected components...Assume there is a edge between 2 nodes if there are of same color...

- Anonymous September 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous February 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

R
          B     R
       B   B      R

- Anonymous February 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can't change a condition of the problem, just because, to you, it seems more intuitive. If that was the case, I would just answer with 'it isn't intuitive to give a crap about clusters- problem solved'.

The tree you listed has 1 Blue cluster.

- Anonymous September 14, 2012 | Flag


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