Google Interview Question
Software Engineer / DevelopersCountry: Switzerland
I agree with your answer.
int numberOfPixelsGivenColor(QuadTree* t, bool col)
can be implemented as a trivial tree traversal.
Hi Marcello! Could you think about some super simple code that builds the tree given the binary image? Maybe that would be tough during the interview given the fact you only have about 40min and whiteboard only. The method signature would be something like this:
public static QuadNode buildQuadTree(boolean[][] img);
I would have explored the need to store white pixels at all, this could be the default state, ie the blank screen, so I would only have stored the black pixels and included a variable on my wrapping class to track black pixels.
If the answer was that there were three states eg off, white, black I'd use a byte to store the colour rather than a boolean, booleans are vm dependant and could eat up a lot of memory.
I could imagine something like this:
public class QuadNode{
private QuadNode[] children;
private Color color;
final Rectangle rectangle;
public QuadNode(boolean boolColor, int x, int y, int w, int h){
this.color = colorFor(boolColor);
rectangle = new Rectangle(x, y, w, h);
}
public void setColor(int x, int y, boolean boolColor){
if (!rectangle.contains(x,y)) throw new IllegalArgumentException(“index out of range”);;
if (isLeaf()){
if (colorMatch(boolColor)){
return;
} else if (rectangle.area() == 1){
setColor(boolColor);
return;
} else {
//adding 4 new children
split();
}
}
QuadNode child = childFor(x,y);
child.setColor(x, y, boolColor);
//all kids have same color
if (isCompressable()){
removeChildren();
setColor(boolColor);
}
}
public int numberOfPixelsGivenColor(boolean boolColor){
if (isLeaf()){
if (colorMatch(boolColor)){
return rectangle.area();
} else {
return 0;
}
}
int ret = 0;
for(QuadNode child : children){
ret += child.numberOfPixelsGivenColor(boolColor);
}
return ret;
}
...
}
class Rectangle{
int x, y, w, h;
....
}
Quadtree is a tree with branching factor of four. In this context it is probably used for dividing screen space recursively into four quadrants. The important question is 'how and what for we will use it for'? Now I am guessing, I think that we will deal with the case when there is a binary picture given and we want to zoom out (or scale down) the image by factors of two.
Lets design the node, each node:
(i) will contain four links to children
(ii) will contain color
(iii) will contain portion of white pixels in its sub-tree
(iv) if node is a leaf, its number of white pixels will be either 0 or 1;
Then the query 'numberOfPixelsGivenColor' will be straightforward. The datastructure may look like this:
I am not sure this is exactly what interviewer was asking for.
- autoboli April 23, 2015