Решаю задачу с собеседования в Google: number of islands

Сегодня мы разберём собеседование, на котором кандидат подробно объясняет решение задачи «подсчёт островов» на двумерной сетке, используя алгоритм обхода в глубину (DFS), и пошагово реализует его в коде. Несмотря на несколько опечаток и небольшие запинки при написании кода, кандидат демонстрирует понимание логики рекурсивного обхода, корректно обрабатывает границы массива и в итоге приходит к рабочему решению. Интервьюер выступает в роли модератора задачи, а основной диалог строится вокруг технического объяснения и реализации алгоритма.

Вопрос 1. Реализовать алгоритм подсчёта количества островов в двумерной сетке, где 1 — суша, 0 — вода. Остров — это группа единиц, соединённых горизонтально или вертикально (не по диагонали).

Таймкод: 00:00:00

Ответ собеседника: Правильный. Предложено решение с использованием обхода в глубину (DFS). Алгоритм итеративно проходит по матрице, при обнаружении единицы увеличивает счётчик островов и рекурсивно помечает все связанные ячейки суши значением 2, чтобы не учитывать их повторно. Реализована функция dfs, которая проверяет границы матрицы и наличие суши в четырёх направлениях (вверх, вниз, влево, вправо). Код содержит несколько опечаток, но после исправлений решение прошло проверку и оказалось верным.

Правильный ответ:

Задача «Number of Islands — это классическая задача на обход графа, применяемая в реальных сценариях: обработка изображений (поиск связанных компонентов), геоинформационные системы, игры и сетевые кластеры.

Основные подходы к решению:

1. Обход в глубину (DFS)

DFS — наиболее интуитивный подход. При обнаружении непосещённой ячейки суши запускаем рекурсивный обход, помечая все связанные ячейки как посещённые.

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    
    rows, cols := len(grid), len(grid[0])
    count := 0
    
    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
            return
        }
        grid[r][c] = '2' // помечаем как посещённую
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }
    
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                count++
                dfs(i, j)
            }
        }
    }
    return count
}

Сложность: O(m×n) по времени и памяти (глубина рекурсии в худшем случае).

2. Обход в ширину (BFS)

BFS использует очередь вместо рекурсии, что предотвращает переполнение стека на больших сетках:

func numIslandsBFS(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    
    rows, cols := len(grid), len(grid[0])
    count := 0
    directions := [][2]int{{1,0}, {-1,0}, {0,1}, {0,-1}}
    
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] != '1' {
                continue
            }
            
            count++
            queue := [][2]int{{i, j}}
            grid[i][j] = '2'
            
            for len(queue) > 0 {
                cell := queue[0]
                queue = queue[1:]
                
                for _, d := range directions {
                    nr, nc := cell[0]+d[0], cell[1]+d[1]
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
                        grid[nr][nc] = '2'
                        queue = append(queue, [2]int{nr, nc})
                    }
                }
            }
        }
    }
    return count
}

3. Система непересекающихся множеств (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 := range parent {
        parent[i] = i
        rank[i] = 1
    }
    return &UnionFind{parent: parent, rank: rank, count: 0}
}

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) {
    px, py := uf.Find(x), uf.Find(y)
    if px == py {
        return
    }
    if uf.rank[px] < uf.rank[py] {
        px, py = py, px
    }
    uf.parent[py] = px
    if uf.rank[px] == uf.rank[py] {
        uf.rank[px]++
    }
    uf.count--
}

Ключевые моменты для интервью:

• Проверка граничных условий (пустая сетка, одна ячейка)
• Четыре направления обхода (без диагоналей)
• Модификация исходной матрицы vs. использование отдельной матрицы посещений
• Обработка больших входных данных (итеративный DFS/BFS вместо рекурсивного)
• Понимание разницы между модификацией входных данных и использованием дополнительной памяти

Оптимизации для продакшена:

• Использование sync.Pool для переиспользования буферов в высоконагруженных системах
• Параллельная обработка для очень больших сеток (разбиение на регионы с последующим объединением границ)
• Применение для потоковых данных с инкрементальным обновлением через Union-Find