Решение задачи с собеседования программиста

При подготовке к собеседованию больше всего вопросов возникает к алгоритмической секции интервью. В этом видео я - бекенд разработчик Анна Коптева, разберу одну из алгоритмических задач, которую вам могут задать на собеседовании. Задача про острова входит в Топ-100 самых задаваемых задач на интервью и, возможно, понимание алгоритма её решения поможет вам получить работу мечты.

[zhuk]

очень качественно сделано видео, ну и конечно, интересно и доступно

[verge_programming]

Крутое решение) Да и сама задача очень интересная

[borispr]

Механизм рекурсии это не когда мы сталкиваемся с ограничением мы возвращаемся назад. Девушка милая. Продолжайте

[vanzo]

на последней единичке пальчик так и остался на shift-'e'. 😉
благодарю за видео.

[petrnaboko]

Спасибо огромное за задачку и решение!

Решение на шарпе:
{

static void Main(string[] args)
{
char[, ] grid = new char[, ]
{
{ '1', '0', '1', '0', '1'},
{ '1', '0', '0', '0', '1'},
{ '0', '0', '1', '0', '0'},
{ '1', '1', '0', '0', '0'},
{ '1', '1', '1', '0', '1'}
};



Console.ReadKey();
}

public static int NumberOfIslands(char [, ] grid)
{
if (grid == null || grid.Length == 0)
return 0;

int numberOfIslands = 0;

var rows = grid.GetUpperBound(0) + 1;
var columns = grid.Length / rows;

for(int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
if (grid[i, j] == '1')
{
numberOfIslands++;
MarkIsland(grid, i, j);
}
}
}

return numberOfIslands;
}

private static void MarkIsland(char [, ] grid, int i, int j)
{
var rows = grid.GetUpperBound(0) + 1;
var cols = grid.Length / rows;
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i, j] == '0')
return;

grid[i, j] = '0';

MarkIsland(grid, i, j + 1);
MarkIsland(grid, i + 1, j);
MarkIsland(grid, i, j - 1);
MarkIsland(grid, i - 1, j);
}


}

[amerohful]

разве в java можно так изменять массив?(давно не использовал)

[paparazzi]

Заранее извиняюсь за тупые вопросы!)

Это с++?

Почему двойной массив имеет тип char(Символьный) если в массиве только нули и однерки?

На 12 строке! "MarkIsland(grid., i, j)" Можете объяснить?

Отличный видос, надеюсь еще будет больше таких видосов!

[Maiq-The_Liar]

Почему счетчики называют "итэ", "джитэ", а не "ай", "джей"? Не первый раз слышу, не могу найти этимологию.

[timur]

Асимптотическая сложность в худшем случае будет ~ O(n^3) - в случае, если вся матрица - материк без воды - каждую клетку будем обходить дважды - методом markIsland + внешними вложенными циклами

[hutoryanin]

упс, всё отлично 😊

*Р. е. с. п. е. к. т.*

[loadmore]

Короче в автоматах игра где лягушка 🐸 прыгает по листьям

[QesOrwuMqN]

никакого поиска в глубину - только в ширину

[viplark]

Реализация на python
import numpy as np
from scipy import ndimage

ary = np.array([
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 1, 0, 0],
[1, 0, 1, 0, 1]
])

island_map, num_islands = ndimage.label(ary)
print(island_map)
print(num_islands)

[ivankonst]

О большое от N посчитано неверно. Вы учли два вложенных for-цикла, это действительно M*N.
Но вы не учли рекурсивную функцию, она тоже добавит прилично по времени.

[mfdjywq]

Пожалуй не буду смотреть, сначала сам решу.