## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Consider that edge nodes are either black or white in Q tree. If your node edge is at depth d, it corresponds to S/2^(2d) pixels, when S is total number of pixels in image, So you can traverse through tree and find total black pixels

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

Could you provide any solution with code please?

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

A quad tree can have only 3 color of nodes .. black white and gray

The crux is that at each level(depth) if the pixel color is not gray then it represents 4^(k-d) pixels of color same as itself. where k represents the overall size of image of size (2^k X 2^k) and d represents the current depth of node in the tree

Assuming each node has color field: "black"/"white"/"gray"
and 4 field for the 4 child nodes of type node: ne , nw, se, sw

Code in Python:

``````def quadTreeCountBlackPixels(root, depth, size):
if (None == root):
return 0
if (root.color == “white”):
return 0
elif (root.color == “black”):
return pow(4, size-depth)
else:
seCount = quadTreeCountBlackPixels(root.se, depth+1, size)
swCount = quadTreeCountBlackPixels(root.sw, depth+1, size)
neCount = quadTreeCountBlackPixels(root.ne, depth+1, size)
nwCount = quadTreeCountBlackPixels(root.nw, depth+1, size)
return seCount + swCount + neCount +nwCount

#initial call to function
totalBlackPixels  = quadTreeCountBlackPixels(root, 0 , k):

#where the image is of size 2^k X 2^k``````

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

Where ne , nw, se, sw represents 4 subsection of current section of image (north east, north west, south west, south east)

nw|ne
sw|se

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.