Last year when I was interviewing with Amazon, the first question that I was asked is to write a function get_number_of_islands(matrix) . This was ...
For further actions, you may consider blocking this person and/or reporting abuse
My approach to deal with this kind of problems :
For this specific task my solution is :
Use a double-buffered row (matching the matrix row length), in which I'll put "colours" (a natural will do fine) for each "1" found. Use an invalid colour (-1 for naturals) for the "0"s in the row. You fill one row buffer form left to right, then you swap buffers. To know what colour to assign, you have to check :
1) Is the matching matrix cell land or water ? If it's water, use invalid_colour
2) Else use colour of the cell directly to the left, or the colour of the cell directly above (that's why you need to keep 2 colour rows, but you don't need more). If both are invalid, use a new colour.
Do all the rows until you reach the bottom of the matrix. Initialize the colour buffers with invalid_colour.
By doing that, you will have "coloured" all the landmasses. But it may happen that a single island has 2 colours (Try with a U-shaped island). To avoid counting double you'll use a map that store, for each colour, the "name" of the island. (of course, the "names" too can be naturals). The idea is : when you add a new colour (see step 2 above), also add it to the map with a new island name. And when you detect a 2 different adjacent colours, change the name mapped to one of the colours, so they both map to the same name (by doing that, you're "freeing" an island name, that you can store for reuse later). Detecting adjacent colours is quite easy. In step 2 of the algorithm, if the cell above, and the cell on the left both have a valid colour, and they're different, then you should "merge" names.
At the end, you just want to count the number of different names, which is easy if you used integers, and reused "free"d ones : that's your "highest" name, minus the number of free'd ones remaining at the end.
This would be quite efficient if the matrix is given as a continuous stream of rows of booleans. If the matrix is given as columns, you may want to adapt the algorithm.
This is pretty detail. To be honest, I have to read it a couple times for it to make sense. I just want to do good enough for now to pass an interview. :-p
Umm, call me dumb, but according to the definition you have provided, there is only one island - centered at the second row fourth column.
The solution rather says an island is an isolated one, or a group of adjacent ones, diagonals excluded; that would give six as a result indeed.
Do you mean it's surrounded by adjacent 0's?
This picture should clarify what it means. Each color group represents each island.
Thanks, that's what I thought it meant, but wasn't sure.
a correct way to say it would be "an island is a group of adjacent cells that are all 1s, surrounded by 0s or array's margins"
I was asked this question in an interview(not Amazon). Initially I thought that I won't be able to solve it, but was able to with some hints from the interviewer. My solution was in C# and was similar to yours.
awesome. It always felt great to be able to find the solution in the end. Did you end up getting that job?
Ha! I actually asked the exact same challenge by Amazon few months back. Sadly unable to solve it during the interview itself. But 1.5 hours afterwards, I solved it and then sent my solution to them. Didn't land the job though :)
I think you could also solve it using Flood Fill
Algorithm, which is similar to your approach. Thank you for sharing!
I have no idea what Flood Fill algorithm is. Will take a look at it. Thanks
Tbh, this is a very basic question, solvable in linear time with graph traversal algorithms like BFS/DFS.