Microsoft Interview Question
Software Engineer / DevelopersTeam: Bing
Country: India
Interview Type: Phone Interview
Any closed shape of sufficient area containing color other than blue as majority can be considered an island.
This is just a basic idea but can be helpful if a programming approach is to be used.
We can do this by using the Connected Components algorithm that uses the Union-Find data structure. To account for different shades of same color we can define a function that will return true if difference between color attributes of neighbouring pixels are within some configurable threshold.
Start traversing the picture
- Old Monk December 01, 2012----> If found an unfound land pixel
--------> DFS traverse all connected land pixels mark all of them found
Number of islands = Number of DFS traversals started for land pixels