Mock Coding interview with a Google Software Engineer
Сегодня мы разберём процесс прохождения кандидатом Джей задания на подсчёт количества островов в бинарной матрице, которое он успешно решил с помощью DFS, продемонстрировав глубокое понимание алгоритмов и структур данных. В ходе собеседования Джей также адаптировал решение для определения размеров каждого острова и объяснил влияние учёта диагональных связей, а завершил обсуждение анализом временной и пространственной сложности, подтвердив высокий уровень подготовки и способность мыслить системно.
Вопрос 1. Дана двумерная сетка, состоящая из единиц (суша) и нулей (вода). Единицы, соединённые горизонтально или вертикально, образуют остров. Диагональные соединения не учитываются. Необходимо подсчитать количество отдельных островов на карте. Как решить эту задачу?
Таймкод: 00:00:37
Ответ собеседника: Правильный. Предложен подход с итеративным проходом по всем ячейкам сетки. При обнаружении непосещённой суши (1) запускается рекурсивный обход в глубину (DFS) для пометки всех связанных ячеек как посещённых, после чего счётчик островов увеличивается на единицу. Для отслеживания посещённых ячеек используется множество (set) кортежей (строка, столбец). Обработаны граничные случаи: пустая сетка (возврат 0), сетка из одних нулей. Базовые случаи для рекурсии DFS: выход за границы сетки, ячейка уже посещена, ячейка — вода (0). Реализован код на Python с функцией numDistinctIslands и вспомогательной рекурсивной функцией exploreDFS. Проведён пошаговый прогон кода на тестовом примере, подтвердивший корректность (результат — 3 острова). Также обсуждены модификации задачи: возврат массива размеров островов — DFS изменён на возврат размера (1 + сумма размеров соседних участков), результаты собираются в список; учёт диагональных соединений — добавляются ещё 4 направления обхода. Проанализирована временная и пространственная сложность: O(M×N) в обоих случаях, где M — число строк, N — число столбцов. Указано, что замена DFS на BFS не меняет сложность, так как в худшем случае все ячейки посещаются, а очередь в BFS аналогична стеку вызовов в DFS по объёму используемой памяти.
Правильный ответ:
Задача «Number of Islands» — классическая задача на обход графа, где двумерная сетка неявно представляет собой граф: каждая ячейка — вершина, а рёбра — это связи между соседними ячейками суши (вверх, вниз, влево, вправо). Цель — подсчитать количество связных компонент в этом графе.
Основной алгоритм: DFS (обход в глубину)
Идея проста: проходим по каждой ячейке сетки. Когда встречаем непосещённую ячейку суши (значение 1), мы нашли новый остров — увеличиваем счётчик и запускаем DFS, чтобы «залить» весь остров, пометив все его ячейки как посещённые. После этого повторный проход по этим ячейкам не приведёт к увеличению счётчика.
Реализация на Go:
package main
func numIslands(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
visited := make([][]bool, rows)
for i := range visited {
visited[i] = make([]bool, cols)
}
count := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' && !visited[r][c] {
count++
dfs(grid, visited, r, c, rows, cols)
}
}
}
return count
}
func dfs(grid [][]byte, visited [][]bool, r, c, rows, cols int) {
if r < 0 || r >= rows || c < 0 || c >= cols {
return
}
if visited[r][c] || grid[r][c] == '0' {
return
}
visited[r][c] = true
dfs(grid, visited, r-1, c, rows, cols) // вверх
dfs(grid, visited, r+1, c, rows, cols) // вниз
dfs(grid, visited, r, c-1, rows, cols) // влево
dfs(grid, visited, r, c+1, rows, cols) // вправо
}
Оптимизация по памяти: модификация входной сетки
Вместо выделения отдельной матрицы visited можно модифицировать саму сетку, заменяя '1' на '0' (или любой другой маркер) при посещении. Это снижает пространственную сложность с O(M×N) до O(1) дополнительной памяти (не считая стек рекурсии):
func numIslandsInPlace(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
count := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
count++
dfsInPlace(grid, r, c, rows, cols)
}
}
}
return count
}
func dfsInPlace(grid [][]byte, r, c, rows, cols int) {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
return
}
grid[r][c] = '0' // помечаем как посещённую (затапливаем)
dfsInPlace(grid, r-1, c, rows, cols)
dfsInPlace(grid, r+1, c, rows, cols)
dfsInPlace(grid, r, c-1, rows, cols)
dfsInPlace(grid, r, c+1, rows, cols)
}
Альтернативный подход: BFS (обход в ширину)
Вместо рекурсивного DFS можно использовать итеративный BFS с очередью. Это полезно, когда глубина рекурсии может быть очень большой (сетка 10⁶ × 10⁶), что приведёт к переполнению стека вызовов:
func numIslandsBFS(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
count := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
count++
bfs(grid, r, c, rows, cols)
}
}
}
return count
}
func bfs(grid [][]byte, sr, sc, rows, cols int) {
queue := [][2]int{{sr, sc}}
grid[sr][sc] = '0'
directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for len(queue) > 0 {
cell := queue[0]
queue = queue[1:]
r, c := cell[0], cell[1]
for _, d := range directions {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
grid[nr][nc] = '0'
queue = append(queue, [2]int{nr, nc})
}
}
}
}
Альтернативный подход: Union-Find (система непересекающихся множеств)
Ещё один подход — использовать структуру данных Union-Find. Сначала добавляем все ячейки суши как отдельные множества, затем для каждой ячейки объединяем её с соседями справа и снизу (если они тоже суша). В конце количество уникальных корней равно количеству островов:
type UnionFind struct {
parent []int
rank []int
count int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
rank := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
}
return &UnionFind{parent: parent, rank: rank, count: n}
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x]) // сжатие пути
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) {
rx, ry := uf.Find(x), uf.Find(y)
if rx == ry {
return
}
if uf.rank[rx] < uf.rank[ry] {
rx, ry = ry, rx
}
uf.parent[ry] = rx
if uf.rank[rx] == uf.rank[ry] {
uf.rank[rx]++
}
uf.count--
}
func numIslandsUnionFind(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
// Подсчитываем количество ячеек суши
landCount := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
landCount++
}
}
}
if landCount == 0 {
return 0
}
// Сопоставляем каждой ячейке суши уникальный индекс
index := make([][]int, rows)
for i := range index {
index[i] = make([]int, cols)
for j := range index[i] {
index[i][j] = -1
}
}
idx := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
index[r][c] = idx
idx++
}
}
}
uf := NewUnionFind(landCount)
directions := [][2]int{{-1, 0}, {0, -1}} // проверяем только вверх и влево
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
for _, d := range directions {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nc >= 0 && grid[nr][nc] == '1' {
uf.Union(index[r][c], index[nr][nc])
}
}
}
}
}
return uf.count
}
Сравнение подходов
DFS (рекурсивный) — самый простой и лаконичный. Временная сложность O(M×N), пространственная O(M×N) в худшем случае (стек рекурсии для сетки из одних единиц). Риск переполнения стека на больших сетках.
DFS (итеративный) или BFS — аналогичная сложность, но без риска переполнения стека вызовов. Пространственная сложность O(min(M×N, max(M, N))) для очереди/стека в худшем случае.
Union-Find — временная сложность O(M×N × α(M×N)), где α — обратная функция Аккермана (практически константа). Пространственная O(M×N). Этот подход особенно полезен, если сетка динамически меняется (добавляются/удаляются ячейки суши) и нужно поддерживать актуальное количество островов в реальном времени.
Анализ сложности
Для всех трёх подходов временная сложность составляет O(M×N), поскольку каждая ячейка посещается константное число раз. Пространственная сложность зависит от подхода: O(M×N) для матрицы visited, O(1) для in-place DFS, O(M×N) для Union-Find. В худшем случае (вся сетка — суша) стек рекурсии DFS или очередь BFS потребуют O(M×N) памяти.