Алгоритмы с нуля
Графы: тренажёр для собеседований
DFS, BFS и кратчайшие пути ты понимаешь. Собеседование проверяет, узнаешь ли ты в сетке или списке зависимостей замаскированный граф, выберешь ли правильный обход под таймером и объяснишь ли стоимость вслух.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Пять задач из NeetCode-150 на приёмы обхода графов и advanced graphs из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/5 решено
graphs
Follow-up (вслух)
Назови сложность через строки и столбцы. Почему каждая клетка обрабатывается константное число раз несмотря на вложенный обход?
Follow-up (вслух)
Почему map посещённых выполняет двойную роль — и защита от циклов, и результат? Какова пространственная сложность?
Follow-up (вслух)
Сравни DFS-обнаружение цикла с алгоритмом Кана: какое состояние ведёт каждый и как каждый делает вывод о наличии цикла?
Follow-up (вслух)
Почему заливка внутрь от океанов асимптотически дешевле, чем заливка наружу от каждой клетки? Назови обе сложности.
advanced graphs
Follow-up (вслух)
Назови сложность Dijkstra с бинарным heap. Почему он требует неотрицательных весов рёбер и что бы ты взял, будь некоторые отрицательными?
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.