Diagonal connections do not count. That would be two islands.
I'd prefer Java or Python.
Diagonal connections do not count. That would be two islands.
I'd prefer Java or Python.
@sapere-aude
I looked at the battleships problem. Its solution would not work for the number of islands, for example:
X . X
X X X
It would return 2, even though it's 1.
I thought my interview question was identical to the number of islands problem. I must have glossed over some of the details, since the interviewer asked for no modification and better than O(w*h) space. For a problem like number of islands, it's not possible right?
Write a function: int numIslands(boolean[] grid, int w, int h)
that returns the number of islands in grid
. grid
is 1-dimensional, but represents a 2-dimensional boolean[h][w]
array. Example: if h = 12
and w = 5
, then grid[7]
represents [1][2]
.
Now, there is an additional constraint: can you solve this problem without modifying grid
, and without using O(w*h)
extra space?
I was asked this in a interview, and haven't figured out the solution for the constraint.
@varun44 how many years experience do you have? What level at Google were your interviews targeting? I believe for L3 they don't do system design but not sure about L4+.