Алгоритмы с нуля
Сортировка и поиск: тренажёр для собеседований
Binary search ты понимаешь. Собеседование проверяет, сможешь ли ты потянуться за ним под таймером, вхолодную, и вслух объяснить стоимость.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Пять задач из NeetCode-150 на приём binary search из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/5 решено
binary search
Follow-up (вслух)
Вычисляй mid как lo + (hi - lo) // 2, а не (lo + hi) // 2 — какую ошибку это предотвращает и каков инвариант цикла?
Follow-up (вслух)
Почему это O(log(m·n)), а не два отдельных поиска O(log m)+O(log n) — и когда двухшаговая версия всё же обязательна?
Follow-up (вслух)
Почему сравнивать с nums[hi], а не с nums[lo]? Разбери, что ломается при неверном якоре.
Follow-up (вслух)
Подтверди, что это остаётся O(log n) несмотря на поворот, затем опиши, как дубликаты ухудшают худший случай.
Follow-up (вслух)
Назови сложность как O(n log m) и определи n и m, затем объясни, что вообще делает задачу пригодной для binary search по ответу.
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.