Алгоритмы с нуля
Greedy и интервалы: тренажёр для собеседований
Exchange argument ты понимаешь. Собеседование проверяет, заметишь ли ты локально-оптимальный ход под таймером, отсортируешь ли по нужному ключу и обоснуешь ли вслух, почему greedy остаётся оптимальным.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность — и почему жадный выбор доказуемо верен — так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Пять задач из NeetCode-150 на приёмы greedy и intervals из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/5 решено
greedy
Follow-up (вслух)
Назови инвариант Kadane: что означает текущее значение на каждом индексе и почему нести отрицательный префикс никогда не помогает?
Follow-up (вслух)
Эта жадность — O(n) за один проход. Докажи, что отслеживание только самого дальнего достижимого индекса не упускает ни один валидный путь.
intervals
Follow-up (вслух)
Поскольку вход уже отсортирован, это один линейный проход. Каково условие пересечения двух интервалов и где именно ты его проверяешь?
Follow-up (вслух)
Сортировка определяет стоимость. Назови общую сложность и почему после сортировки достаточно одного линейного прохода.
Follow-up (вслух)
Приведи exchange argument, почему «оставляй раньше всех заканчивающийся интервал» оптимально. Что сломается, если сортировать по началу?
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог обосновать жадный выбор без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.