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;
	QuadNode[] children;

	public QuadNode(boolean col) {
		this.col = col;
		this.nwhite = 0;
		this.children = new QuadNode[4];
	}

	public void addChild(QuadNode node, int k) {
		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.

- autoboli April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with your answer.

int numberOfPixelsGivenColor(QuadTree* t, bool col)

can be implemented as a trivial tree traversal.

- Marcello Ghali April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- autoboli April 25, 2015 | Flag
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;
};

- crazysea13 April 27, 2015 | Flag Reply
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.

- jninety67 May 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- madno May 16, 2015 | Flag Reply
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.

- DKR November 13, 2015 | Flag Reply


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