Алгоритмы с нуля
Рекурсия и backtracking: тренажёр для собеседований
Backtracking ты понимаешь. Собеседование проверяет, сможешь ли ты потянуться за ним под таймером, вхолодную, и вслух объяснить стоимость.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Пять задач из NeetCode-150 на приём backtracking из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/5 решено
backtracking
Follow-up (вслух)
Подмножеств 2^n. Обоснуй время O(n·2^n) и объясни, откуда берётся дополнительный множитель n.
Follow-up (вслух)
Почему передача «start», а не свободный выбор любого индекса, исключает перестановки одной и той же комбинации?
Follow-up (вслух)
Перестановок n! — проговори оценку времени и сопоставь с 2^n у подмножеств.
Follow-up (вслух)
Число допустимых строк — n-е число Каталана. Формула не нужна — но почему обрезка недопустимых префиксов важна для реальной стоимости?
Follow-up (вслух)
Назови худшее время как O(m·n·4^L) и определи L; объясни, почему шаг восстановления держит память в O(L).
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.