Алгоритмы с нуля
Кучи и приоритетные очереди: тренажёр для собеседований
Heap ты понимаешь. Собеседование проверяет, заметишь ли ты, когда «мне нужны только k лучших» бьёт сортировку, потянешься ли за priority queue под таймером и объяснишь ли стоимость вслух.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Пять задач из NeetCode-150 на приём heap и priority queue из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/5 решено
heap priority queue
Follow-up (вслух)
Почему min-heap размера k, а не max-heap по всему? Проговори сложность одного add и почему она зависит от k, а не от n.
Follow-up (вслух)
Каждый раунд уменьшает heap минимум на один. Назови общую сложность и почему её определяют операции с heap.
Follow-up (вслух)
Quickselect в среднем O(n), но в худшем случае O(n²). Какой вход вызывает худший случай и как случайный pivot защищает от него?
Follow-up (вслух)
Сравни подход с heap размера k и quickselect-разбиение по расстоянию. Назови сложность каждого и когда выберешь который.
Follow-up (вслух)
Обоснуй, почему жадность «всегда запускай самую частую готовую задачу» оптимальна здесь. Что сломалось бы, если две задачи имеют одинаковую максимальную частоту?
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.