Как решать задачи с деревьями и алгоритмами
Что проверяют
Есть ли у вас метод решения, а не набор заученных решений. Интервьюеру важно, как вы думаете вслух.
Как отвечать
Опишите подход по шагам, это и есть ответ.
1. Уточнить условие. Размер входа, диапазон значений, возможны ли дубликаты и пустой вход, что возвращать при отсутствии результата. Половина ошибок на собеседованиях это решение не той задачи.
2. Проговорить наивное решение. Даже квадратичное. Оно даёт точку отсчёта и показывает, что вы поняли задачу.
3. Найти структуру данных, которая помогает. Для деревьев это обход в глубину (рекурсия или стек) и в ширину (очередь). Для «найти пару» это хеш-таблица. Для «k наибольших» это куча. Для отсортированного массива это два указателя или бинарный поиск.
4. Оценить сложность по времени и по памяти, включая стек рекурсии.
5. Разобрать краевые случаи: пустое дерево, один узел, вырожденное дерево-список, дубликаты.
По деревьям полезно назвать базовый набор: обход в глубину в трёх порядках, обход по уровням через очередь, поиск в двоичном дереве поиска, глубина и балансировка, наименьший общий предок, сериализация. Большинство задач сводится к одному из них.
Отдельно про подготовку: практика на задачах даёт не память, а узнавание. Увидев «найти k-й элемент», вы вспоминаете кучу, а не выводите решение с нуля.
Где спотыкаются
Молча пишут код, не проговаривая ход мысли.
Начинают с оптимального решения и запутываются, вместо того чтобы улучшать наивное.
Не спрашивают про ограничения и решают не ту задачу.
Забывают про стек рекурсии в оценке памяти.