## Google Interview Question for Software Engineer / Developers

Country: Switzerland

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

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:

``````public class QuadNode {
boolean col;
int nwhite;

this.col = col;
this.nwhite = 0;
}

this.children[k] = node;
this.nwhite += node.nwhite;
}

public int nwhite() { return this.nwhite; }
}``````

I am not sure this is exactly what interviewer was asking for.

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

``int numberOfPixelsGivenColor(QuadTree* t, bool col)``

can be implemented as a trivial tree traversal.

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

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);``

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

Data structure can be something below. all the child node will be sibling so if A is parent of B,C,D,E we have link from A->B which is firstChild and from B->C->D->E

``````struct TreeNode
{
int pixtype;
TreeNode* firstChild;
TreeNode* sibling;
};``````

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

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.

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

I could imagine something like this:

``````public class QuadNode{
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 {
split();
}
}

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;
ret += child.numberOfPixelsGivenColor(boolColor);
}
return ret;
}
...
}
class Rectangle{
int x, y, w, h;
....
}``````

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

Given each box contains some value. So this could be a complete Quad-tree.
We can go for Boolean Array to represent Quad-tree and # white pixels is equal to sum of the array.

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.

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