Google Interview Question for Software Engineer / Developers
- 0of 4 votes
Given a matrix of size N*N and a starting point "s" in the matrix which represents a color.
Find the area of the shape represented by the color of the starting point "s".
Note 1: A shape can be anything as long as it is connected, e.g. a square, a circle, a doughnut or a line.
Note 2: It is only a shape if they are connected from the starting point.
Note 3: Connected means, adjacent and the same color.
zero based index. Starting point = top left "R" , color = R, area = 10 000000000 000000000 000000000 00RRRR000 00R00R000 00RRRR000 000000000 000000000 000000000
Update: OK as requested further clarifications, a cell is only a single color, it is a matrix and contains
a single value stating the color of the cell. Think of each cell as a pixel and each pixel represents a length of 1.
The shape above has an area of 10, because that it is not a regular square but has two holes in the middle, if you do it mathematically:
(3*4) - (1*2) = 10 or simply by visually counting the R squares.
You are not trying to create shapes, you are using the starting point "s" to find the complete shape (traverse the matrix until you have found all connected pixels) and calculate the area.
If you need more clarification I can try but I think that should clarify.
State your Time and Space complexity of your algorithm.
Consider also this:
0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 00RRRR0000000 00R00R000RR00 00RRRR000RR00 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 zero based index. Starting point s = top-left "R" , area = 10.
In the above case, the other shape, same color is not connected to the shape specified by the starting point, hence is not part of the area calculation.- DotQ May 09, 2014 in United States
Apologies for the formatting.
| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
Interview Type: Written Test
Open Chat in New Window