Amazon Interview Question: You are given a n*n matrix of... | Glassdoor

## Interview Question

Software Development Engineer In Test I (SDET) Interview Seattle, WA

# You are given a n*n matrix of bits (1s and 0s) where

1 represents land and 0 represents water. Adjacent 1s can be considered as joined together to form sort of island in water. Count the number of islands. Discuss complexity.
Tags:
complexity, technical writing

2

int nCnt = 0;
int land = 0;
boolean bIsOne = false;
int a[rows][cloumns];
int i,j;
for(i = 0;i 1)
{
land ++;
}
nCnt = 0;
bIsOne = false;
}
}
}
}

0

My runnable code is here. With the use of DFS, it is very straightforward!

public class Island{
int[][] map;
boolean[][] visited;
int maxRow, maxCol;

public Island(int [][] map){
this.map = map;
maxRow = map.length - 1;
maxCol = map[0].length - 1;
visited = new boolean[maxRow + 1][maxCol + 1];
}

public int islandCount(){
int count = 0;

for(int i = 0; i maxRow || j > maxCol) return;

if(!visited[i][j] && map[i][j] == 1) {
visited[i][j] = true;
runDFS(i - 1, j);
runDFS(i , j + 1);
runDFS(i + 1, j);
runDFS(i , j + 1);
}
}

public class questions{
public static void main(String [] args){

int [][] map = new int [][]{
{1, 1, 1, 1, 0},
{0, 1, 0, 1, 0},
{0, 1, 1, 0, 1}
};

Island island = new Island(map);
System.out.println(island.islandCount());
}
}

Habib on Feb 13, 2016