Yahoo Interview Question
Software Engineer / DevelopersI would traverse every line keeping track of the ranges of black points. For example, if I have on a line: WWWBBWWWBBBWW, then I have the ranges [3-4] and [8-10].
For every range found, I would look for the ranges from the previous line that share some of the columns, then I would connect both ranges, one on another. For example WWBBWWWWWWWWB, has the ranges [2-3] and [12-12] and the first range share some columns with the first range of the previous example. When looking for share, we would have to consider dialgonals (its just a matter of expanding the ranges of the previous line by a unit of 1 on each limit).
After the last line I would have ranges connected to one another. Now the problem is to find how many graphs I have, which I can do flagging the nodes in a DFS, starting at every range that is not flagged already.
The answer is the number of graphs.
Copy the array if possible, (or modify it in place) - or, subvert one of the RGB components perhaps for our own purpose - traverse along, till you see a black pixel; bump the count of these blobs. Do a flood fill of black to white from that point (see wikipedia; the code is simple) and keep going.
Think this can be achieved using the flood fill algorithm.
Represent this picture as a bitmap i.e. a 2D array. Each element in the array is a number which represents a color. For now it only takes black and white.
1. Start traversing the array from 0,0.
2. Once you find a black color pixel stop.
3. Start to flood fill with target color as black and replacement color as something else say red.
4. Once done increment your count and start searching the matrix from where we stopped and repeat the above step 2.
This time the previous shape won't be considered since it is colored red now.
connected component analysis.
- Anonymous April 06, 2011