Алгоритмы с нуля
Списки, стеки и очереди: тренажёр для собеседований
Linked list и stack ты понимаешь. Собеседование проверяет, сможешь ли ты потянуться за ними под таймером, вхолодную, и вслух объяснить стоимость.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Семь задач из NeetCode-150 на приёмы linked list и stack из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/7 решено
linked list
Follow-up (вслух)
Это O(n) по времени и O(1) по памяти итеративно. Набросай рекурсивную версию и объясни, почему её память становится O(n).
Follow-up (вслух)
Почему сшивание существующих узлов — O(1) доп. памяти и как это тот самый шаг merge, на котором работает merge sort для списков?
Follow-up (вслух)
Обоснуй, почему fast гарантированно догоняет slow внутри цикла и почему они не встречаются на ациклическом списке.
Follow-up (вслух)
Проведи интервьюера через то, как держать O(1) доп. памяти и где ошибка на единицу при разбиении испортит результат.
stack
Follow-up (вслух)
Назови два случая ошибки: что ловит проверка пустого stack в конце против проверки несовпадения по ходу.
Follow-up (вслух)
Все четыре операции должны быть O(1). Объясни, почему трюк со вспомогательным stack лучше, чем сканировать минимум на каждый getMin.
Follow-up (вслух)
Защити оценку O(n) через амортизированный анализ и назови другую задачу, которую решает та же идея monotonic stack.
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.