60 вопросов с собеседований по работе с древовидной структурой данных (Tree), которые должен решить каждый программист
Древовидная структура данных (Tree)является одной из наиболее фундаментальных структур данных наряду с массивом и связанным списком в программировании. Что делает древовидную структуру уникальной, так это способность представлять иерархические данные.
Например, вы можете использовать древовидную структуру данных для моделирования отношений сотрудника и менеджера, а также генеалогического древа. Это невозможно реализовать с массивом и связанным списком, поскольку они представляют собой линейные структуры данных. Вот почему древовидная структура данных довольно популярна на собеседованиях по программированию.
Ещё одна причина, по которой на собеседовании так часто задаются вопросы по основе древовидных структурых , таких как алгоритмы обхода дерева (pre order, post order и in-order), заключается в том, что их, как правило их сложнее решить, по сравнению с задачами на основе массива и связанного списка, и многие кандидаты с трудом это делают.
Одной из важных незнаний в этой области отсутствие практики, в то время как массив и связанный список довольно популярны, и все практикуют проблемы кодирования на их основе. Именно поэтому программисты так часто “сыпятся”, когда дело доходит до вопросов о древовидной структуре.
Но вы не можете игнорировать древовидную структуру данных, если серьёзно настроены получить техническую работу в качестве разработчика программного обеспечения. Если у вас появится желание попрактиковаться в решении задач на тематику древовидных структур, вы можете найти их на таких сайтах, как LeetCode и HackerRank.
Я много практиковался в этой области и создал свой собственный список древовидных задач, которые, я думаю, каждый программист должен уметь реализовывать. Сегодня я поделюсь этим списком с вами. Вы также можете решить их, чтобы не только лучше изучить древовидную структуру данных, но и подготовиться к собеседованиям по программированию.
В этом посте мы перечислили часто задаваемые вопросы на собеседовании, в которых используется бинарное дерево:
60 вопросов и задач на основе древовидной структуры данных (Tree) для практикию
Вот список популярных вопросов на основе древовидных структур для собеседований с инженерами-программистами. Эти вопросы охватывают не только базовые понятия, такие как двоичное дерево и двоичное дерево поиска, но и более продвинутые самобалансирующиеся деревья, такие как AVL и Red Black Tree.
Я расположил их в порядке от простого к сложному, и самое главное, что их задают на различных собеседованиях, так что вы получите много практики.
Попутно вы также узнаете ключевые понятия о различных типах деревьев, таких как двоичное дерево, дерево бинарного поиска, дерево AVL, Red Black Tree и другие самобалансирующиеся деревья.
- Как реализовать древовидную структуру данных на Java или C++?
- Как реализовать предварительный обход двоичного дерева в Java или C++?
- Как реализовать обратный обход двоичного дерева в Java, Python или C++?
- Напишите программу для обхода упорядоченного двоичного дерева на Java или C++?
- Можете ли вы написать программу для реализации обхода порядка на уровне двоичного дерева на Java, Python или C++?
- Как вывести правильное представление двоичного дерева на Java, Python или C++?
- Можете ли вы вывести все узлы двоичного дерева, у которых нет родственных узлов в Java?
- Как вывести все пути от корня к узлам двоичного дерева в Java или C++?
- Как найти минимальную глубину двоичного дерева в Java, C++ или Python?
- Как напечатать вид двоичного дерева слева на вашем любимом языке программирования? Не стесняйтесь использовать Java, C++, Python, Ruby или даже JavaScript
- Как найти сумму всех оставшихся узлов двоичного дерева в Java или C++?
- Как найти глубину конечного узла нечетного уровня в двоичном дереве?
- Как проверить, является ли двоичное дерево полным двоичным деревом или нет? Вы можете использовать любой язык программирования для реализации этого задания
- Как проверить, является ли двоичное дерево полным или нет в Java или C++?
- Как проверить, являются ли два узла двоюродными братьями в двоичном дереве в C++ и JavaScript?
- Как проверить, идентичны ли два двоичных дерева в Java, C++ или JavaScript?
- Как проверить, все ли внутренние узлы по московскому летнему времени имеют только одного дочернего узла без построения дерева в Java, на C++ или Python?
- Как преобразовать данное n-арное дерево в его зеркало в Java, Python или JavaScript?
- Как преобразовать двоичное дерево в его зеркальное дерево в Java или C++?
- Как вывести вид сверху двоичного дерева на Java или C++?
- Как распечатать вид сверху двоичного дерева с помощью обхода порядка уровней в Java, C++ или Python?
- Как вывести вид снизу двоичного дерева на Java, Python или C?
- Как вывести вид снизу двоичного дерева с помощью обхода порядка уровней в Java или C++?
- Как удалить все узлы, которые лежат на пути, имеющем сумму меньше k в Java или C++?
- Как удалить все узлы из двоичного дерева в Java или C++?
- Как вывести двоичное дерево в вертикальном порядке на Java или C++?
- Как корректно заполнить все узлы в двоичном дереве в Java, Python или C++?
- Напишите программу на Java или C++, чтобы найти наименьшего общего предка двух узлов в двоичном дереве поиска
- Напишите программу на Java или C++ для реализации итеративного обхода двоичного дерева по предварительному заказу
- Можете ли вы написать программу для поиска преемника узла в двоичном дереве по порядку на языке программирования Java или C?
- Как восстановить двоичное дерево поиска, если позиции двух узлов поменялись местами? Напишите код на Java, Python или C++?
- Как вы находите низ и в верх лемента из набора данных, используя двоичное дерево поиска на языке программирования Java или C++?
- Напишите программу на Java или C++ для вычисления диагональной суммы двоичного дерева.
- Как создать сбалансированное двоичное дерево поиска из отсортированного массива на Java, C++ или даже JavaScript?
- Как преобразовать отсортированный двусвязный список в сбалансированное двоичное дерево поиска на Java, C++ или Python?
- Как преобразовать двоичное дерево в двусвязный список на языке программирования Java или C++?
- Напишите программу на Java или C++, чтобы проверить, сбалансировано ли двоичное дерево или нет? ваша программа должна возвращать значение true, если данное двоичное дерево сбалансировано, и значение false, если нет
- Как вы проверите, является ли двоичное дерево двоичным деревом поиска или нет? Напишите свой код на языках программирования Java, C++, Ruby, Python или JavaScript.
- Напишите программу для проверки того, идентичны ли два двоичных дерева поиска, учитывая их представления в массивах на Java или C++?
- Как вы проверите, является ли двоичное дерево поддеревом другого двоичного дерева за время O (n) в Java или C++?
- Напишите программу на Java, C++ или Python, чтобы проверить, является ли двоичное дерево поддеревом другого двоичного дерева в пространстве O(1)
- Напишите программу на Java или C++ для реализации операций вставки, удаления и поиска
- Как вы проверите, является ли двоичное дерево симметричным деревом или нет на языках программирования Java, C или C++?
- Как вы проверите, является ли данное n-арное дерево симметричным деревом или нет в Java, Python или C++?
- Как вы реализуете обход бинарного дерева по спиральному порядку в Java или C++?
- Как вы найдёте максимальный элемент из каждого подмассива размера ‘k’ в Java, Python или C++?
- Напишите программу для нахождения общего числа возможных двоичных деревьев поиска с ключами ’n’ на Java, Python, JavaScript или C++
- Как найти размер самого крупного двоичного дерева по британскому летнему времени в Java или C++?
- Напишите программу для поиска наименьшего общего предка из 2 узлов в двоичном дереве на Java, Python или C++
- Как найти высоту двоичного дерева по его представлению родительского массива в Java или C++?
- Напишите программу на Java или C++ для преобразования двоичного дерева в двоичное дерево поиска
- Напишите программу для построения двоичного дерева из представления его родительского массива на Java или C++?
- Напишите программу на Java или C++ для построения двоичного дерева из обходов inorder и preorder. Также придайте им временной и пространственной сложности
- Как вы построите двоичное дерево из обходов inorder и postorder ? Решите эту задачу на Java, C++ или Python
- Реализуйте дерево AVL на Java или C++
- Реализуйте вставку, удаление и поиск в заданном дереве AVL на Java или C++
- Напишите программу для реализации сопоставления с образцом с использованием Trie на Java или C++
- Напишите программу для поиска соответствия самому длинному префиксу с помощью Trie на Java, C++ и Python
- Напишите программу на Java или C++, которая, учитывая последовательность слов, сгруппирует все анаграммы и распечатает их
- Напишите программу на Java или C++, сериализующую и десериализующую двоичное дерево поиска
- Как вы сериализуете и десериализуете двоичное дерево поиска с помощью обхода post order в Java или C++?
Это одни из самых популярных вопросов, которые задают на собеседованиях по программированию древовидных структур данных. Вы можете начать практиковать их, чтобы не только лучше изучить древовидную структуру данных, но и быть готовым к любым возможным вопросам.
Я желаю вам всего наилучшего в ваших собеседованиях, и если вы столкнётесь с какими-либо другими интересными проблемами программирования на основе дерева, то вы также можете поделиться со мной в комментариях!