Алгоритмы с нуля
Деревья: тренажёр для собеседований
Trees и tries ты понимаешь. Собеседование проверяет, сможешь ли ты потянуться за ними под таймером, вхолодную, и вслух объяснить стоимость.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Шесть задач из NeetCode-150 на приёмы trees и tries из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/6 решено
trees
Follow-up (вслух)
Назови время O(n), затем объясни, почему память O(h) и чему равно h для сбалансированного против вырожденного дерева.
Follow-up (вслух)
Дай итеративную версию со stack или BFS-очередью и скажи, какая из них естественно меряет глубину по уровням.
Follow-up (вслух)
Как эта процедура становится вспомогательной для проверки, является ли одно дерево поддеревом другого?
Follow-up (вслух)
Почему фиксация размера очереди на уровень — это суть и какова память в худшем случае в терминах самого широкого уровня?
Follow-up (вслух)
Сопоставь подход с границами и in-order по корректности и памяти и назови вход, ломающий наивную проверку только по родителю.
tries
Follow-up (вслух)
Назови время каждой операции в терминах длины слова L и объясни, почему trie может обойти hash set на префиксных запросах.
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.