Google Interview Question
Site Reliability EngineersCountry: Irland
Interview Type: Phone Interview
Using another 2 dimensional array that counts for each position the number of adjacent isles.
For example, for the following board:
o x o
x o x
o x x
the extra matrix will look as follows
2 -1 2
-1 4 -1
2 -1 -1
where -1 signals 'x'
when changing 'o' to 'x' we increment all adjacent (horizontal and vertical) counters.
in addition, save a global counter for the number of isles in the board which will be incremented by 1 when changing 'o' to 'x' in a position i,j with corresponding counter equal to zero, and will be decremented by MIN(isles - 1, counters[i][j]-1) and will be returned by the function.
//This is to find connected components for Graph using DFS/BFS
public class Islands {
// number of rows n columns
static final int ROW = 5, COL = 5;
// A fucntion to check given cell to be included in DFS
boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
// row number is in range, column number is in range
// and value is 1 and not yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
}
// A utility function to do DFS for a 2D boolean matrix.
// It only considers the 8 neighbors as adjacent vertices
void DFS(int M[][], int row, int col, boolean visited[][]) {
// if you want to check neighbours of i, j, do following iteration,
// initialized in rowNbr n colNbr
/*
* [i-1,j-1][i-1,j ][i-1,j+1] [i ,j-1][i ,j ][i ,j+1] [i+1,j-1][i+1,j
* ][i+1,j+1]
*/
int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
// The main function that returns count of islands in a given
// boolean 2D matrix
int countIslands(int M[][]) {
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
boolean visited[][] = new boolean[ROW][COL];
// Initialize count as 0 and traverse through the all cells
// of given matrix
int count = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (M[i][j] == 1 && !visited[i][j]) // If a cell with
{ // value 1 is not
// visited yet, then new island found, Visit all
// cells in this island and increment island count
DFS(M, i, j, visited);
++count;
}
return count;
}
public static void main(String[] args) {
int M[][] = new int[][] { { 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 1 },
{ 0, 0, 0, 1, 0 } };
Islands I = new Islands();
System.out.println("Number of islands is: " + I.countIslands(M));
}
}
The DFS approach, but using queue instead of recursion
private static final char GROUND = 'x';
private static final char WATER = 'o';
private static final char VISITED = 'v';
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int T = scanner.nextInt();
for (int t = 0; t < T; t++) {
int n = scanner.nextInt();
int m = scanner.nextInt();
scanner.nextLine();
char[][] board = new char[n][m];
for (int j = 0; j < m; j++) {
int i = 0;
for (String s : scanner.nextLine().split(" ")) {
board[i++][j] = s.toLowerCase().charAt(0);
}
}
int x = scanner.nextInt();
int y = scanner.nextInt();
System.out.println(getNumberOfIsles(board, n, m, x, y));
}
}
}
private static int getNumberOfIsles(char[][] board, int n, int m, int x, int y) {
// update board
char[][] updatedBoard = deepCopyOfBoard(board);
updatedBoard[x][y] = GROUND;
// check number of isles
int numberOfIsles = 0;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (updatedBoard[i][j] == GROUND) {
LinkedList<int[]> island = new LinkedList<>();
island.add(new int[]{i, j});
while (!island.isEmpty()) {
int[] currentPoint = island.pollFirst();
updatedBoard[currentPoint[0]][currentPoint[1]] = VISITED;
for (int[] direction : directions) {
int newI = currentPoint[0] + direction[0];
int newJ = currentPoint[1] + direction[1];
if (0 <= newI && newI < n && 0 <= newJ && newJ < m && updatedBoard[newI][newJ] == GROUND) {
island.add(new int[]{newI, newJ});
}
}
}
numberOfIsles++;
} else if (updatedBoard[i][j] == WATER) {
updatedBoard[i][j] = VISITED;
}
}
}
return numberOfIsles;
}
private static char[][] deepCopyOfBoard(char[][] originalBoard) {
if (originalBoard == null) {
return null;
}
char[][] copiedBoard = new char[originalBoard.length][];
int i = 0;
for (char[] originalBoardLine : originalBoard) {
copiedBoard[i++] = Arrays.copyOf(originalBoardLine, originalBoardLine.length);
}
return copiedBoard;
}
Input:
3
3 3
o o o
o o o
o o o
1 2
3 3
o o o
o x x
o x o
0 0
7 6
x o o o x o o
o o x o x x o
o x o x o x o
x o x o o x o
x o o o x o o
x x x o o x o
2 2
Output:
1
2
6
def mark_land(arr, row, col):
arr[row][col] = "x"
def get_surrounding_lands(arr, rows, cols, row, col):
surroundings = []
for x, y in [(row, col+1), (row, col-1), (row+1, col), (row-1, col)]:
if x < 0 or y < 0 or x >= rows or y >= cols:
continue
if arr[x][y] == "x":
surroundings.append((x,y))
return surroundings
def count_isles(arr, rows, cols):
''' Counts isles. If there is land surrounding to the current land, it's
marked and counted as part of one big isle.
'''
count = 0
marked = {}
for r in range(rows):
for c in range(cols):
if arr[r][c] == "o":
continue
if marked.get((r,c), False) == True:
continue
marked[(r,c)] = True
count += 1
surroundings = get_surrounding_lands(arr, rows, cols, r, c)
for sx, sy in surroundings:
if marked.get((sx, sy), False) == False:
marked[(sx, sy)] = True
return count
def test():
# Test case 1
arr = [
["o", "o", "o"],
["o", "o", "o"],
["o", "o", "o"]
]
mark_land(arr, 0, 2)
result = count_isles(arr, 3, 3)
assert result == 1, result
# Test case 2
arr = [
["o", "o", "o"],
["o", "o", "o"],
["o", "o", "o"]
]
mark_land(arr, 1, 1)
mark_land(arr, 1, 2)
mark_land(arr, 2, 1)
result = count_isles(arr, 3, 3)
assert result == 1, result
test()
def mark_land(arr, row, col):
arr[row][col] = "x"
def get_surrounding_lands(arr, rows, cols, row, col):
surroundings = []
for x, y in [(row, col+1), (row, col-1), (row+1, col), (row-1, col)]:
if x < 0 or y < 0 or x >= rows or y >= cols:
continue
if arr[x][y] == "x":
surroundings.append((x,y))
return surroundings
def count_isles(arr, rows, cols):
''' Counts isles. If there is land surrounding to the current land, it's
marked and counted as part of one big isle.
'''
count = 0
marked = {}
for r in range(rows):
for c in range(cols):
if arr[r][c] == "o":
continue
if marked.get((r,c), False) == True:
continue
marked[(r,c)] = True
count += 1
surroundings = get_surrounding_lands(arr, rows, cols, r, c)
for sx, sy in surroundings:
if marked.get((sx, sy), False) == False:
marked[(sx, sy)] = True
return count
def test():
# Test case 1
arr = [
["o", "o", "o"],
["o", "o", "o"],
["o", "o", "o"]
]
mark_land(arr, 0, 2)
result = count_isles(arr, 3, 3)
assert result == 1, result
# Test case 2
arr = [
["o", "o", "o"],
["o", "o", "o"],
["o", "o", "o"]
]
mark_land(arr, 1, 1)
mark_land(arr, 1, 2)
mark_land(arr, 2, 1)
result = count_isles(arr, 3, 3)
assert result == 1, result
test()
Union-Find Algorithm
- dmitry.labutin February 09, 2017