Python interview with an Apple engineer: Count islands

[EaimanShoshi]

error is on line number 39.
it should be" 0 <= future_x < row_len and 0 <= future_y < col_len

[sirdudes]

One approach for this could be:
1) maintain a list of coordinates already processed
1.1) maintain a count of total islands
2) traverse matrix standard for loop way
3) for each coordinate determine if it is a piece of land
4) if it is a piece of land, DFS(right negihbour, bottom neighbour)
5) in the DFS function, base case is if current coordinate == 0
6) if not 0, then add coordinate to processed set and DFS on right and bottom neighbour
7) once original DFS call returns, add a delimiter to processed coordinate list (this seperates one island from one another) and update island count
8) continue traversing the matrix and only DFS'ing on coordinaate if non 0 and not in processed

[Decessus]

My instinct with this would be to implement a flood-fill algorithm (as a helper function). Then, pick a random 1 coordinate, flood-fill from that point to get all the other 1's on its island, yield that island's coordinates, then set all those coordinates to 0 and repeat. I guess DFS ends up being equivalent to BFS though.

[jigarmav]

Basic dfs question where you visit all the neighbors of 1 and mark them all -1. You repeat dfs until you got no 1s in the matrix and the no of times dfs runs would be the no of islands I guess.

[xiomaracalderon]

Hi, what position where you interviewing for? I’m applying to test engineer position and have a coding exercise. Just wonder what the complexity is going to look like.

[thedebatemechannel]

This is a trick question. Just say it can't be done and you win.