Вопросы об очередях, часто задаваемые на собеседованиях
· Реализуйте стек при помощи очереди
· Обратите первые k элементов в очереди
· Сгенерируйте двоичные числа от 1 до n при помощи очереди
Связный список
Связный список — еще одна важная линейная структура данных, на первый взгляд напоминающая массив. Однако, связный список отличается от массива по выделению памяти, внутренней структуре и по тому, как в нем выполняются базовые операции вставки и удаления.
Связный список напоминает цепочку узлов, в каждом из которых содержится информация: например, данные и указатель на следующий узел в цепочке. Есть головной указатель, соответствующий первому элементу в связном списке, и, если список пуст, то он направлен просто на null (ничто).
При помощи связных списков реализуются файловые системы, хеш-таблицы и списки смежности.
Вот так можно наглядно изобразить внутреннюю структуру связного списка:
Существуют такие типы связных списков:
· Односвязный список (однонаправленный)
· Двусвязный список (двунаправленный)
Простейшие операции со связными списками:
· InsertAtEnd — Вставляет заданный элемент в конце связного списка
· InsertAtHead — Вставляет заданный элемент в начале (с головы) связного списка
· Delete — Удаляет заданный элемент из связного списка
· DeleteAtHead — Удаляет первый элемент в связном списке
· Search — Возвращает заданный элемент из связного списка
· isEmpty — Возвращает true, если связный список пуст
|
|
|
Вопросы о связных списках, часто задаваемые на собеседованиях:
· Обратите связный список
· Найдите петлю в связном списке
· Возвратите N-ный узел с начала связного списка
· Удалите из связного списка дублирующиеся значения
Графы
Граф — это множество узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x,y) называется ребром, это означает, что вершина x соединена с вершиной y. Ребро может иметь вес/стоимость — показатель, характеризующий, насколько затратен переход от вершины x к вершине y.
Типы графов:
· Неориентированный граф
· Ориентированный граф
В языке программирования графы могут быть двух видов:
· Матрица смежности
· Список смежности
Распространенные алгоритмы обхода графа:
· Поиск в ширину
· Поиск в глубину
Вопросы о графах, часто задаваемые на собеседованиях:
· Реализуйте поиск в ширину и поиск в глубину
· Проверьте, является граф деревом или нет
· Подсчитайте количество ребер в графе
· Найдите кратчайший путь между двумя вершинами
Деревья
Дерево — это иерархическая структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Деревья подобны графам, однако, ключевое отличие дерева от графа таково: в дереве не бывает циклов.
|
|
|
Деревья широко используются в области искусственного интеллекта и в сложных алгоритмах, выступая в качестве эффективного хранилища информации при решении задач.
Вот схема простого дерева и базовая терминология, связанная с этой структурой данных:
Существуют деревья следующих типов:
· N-арное дерево
· Сбалансированное дерево
· Двоичное дерево
· Двоичное дерево поиска
· АВЛ-дерево
· Красно-черное дерево
· 2—3 дерево
Из вышеперечисленных деревьев чаще всего используются двоичное дерево и двоичное дерево поиска.
Вопросы о деревьях, часто задаваемые на собеседованиях:
Найдите высоту двоичного дерева
Найдите k-ное максимальное значение в двоичном дереве поиска
Найдите узлы, расположенные на расстоянии “k” от корня
Найдите предков заданного узла в двоичном дереве
Бор
Бор, также именуемый «префиксное дерево» — это древовидная структура данных, которая особенно эффективна при решении задач на строки. Она обеспечивает быстрое извлечение данных и чаще всего применяется для поиска слов в словаре, автозавершений в поисковике и даже для IP-маршрутизации.
|
|
|
Вот как три слова «top» (верх), «thus» (следовательно), and «their» (их) хранятся в бору:
Слова располагаются в направлении сверху вниз, и зеленые узлы «p», «s» и «r» завершают, соответственно, слова «top», «thus» и «their».
Вопросы о борах, часто задаваемые на собеседованиях:
· Подсчитайте общее количество слов, сохраненных в бору
· Выведите на экран все слова, сохраненные в бору
· Отсортируйте элементы массива при помощи бора
· Постройте слова из словаря, воспользовавшись бором
· Создайте словарь T9
Хеш-таблица
Хеширование — это процесс, применяемый для уникальной идентификации объектов и сохранения каждого объекта по заранее вычисленному индексу, именуемому его «ключом». Таким образом, объект хранится в виде «ключ-значение», а коллекция таких объектов называется «словарь». Каждый объект можно искать по его ключу. Существуют разные структуры данных, построенные по принципу хеширования, но чаще всего из таких структур применяется хеш-таблица.
Как правило, хеш-таблицы реализуются при помощи массивов.
Производительность хеширующей структуры данных зависит от следующих трех факторов:
· Хеш-функция
· Размер хеш-таблицы
· Метод обработки коллизий
|
|
|
Ниже показано, как хеш отображается на массив. Индекс этого массива вычисляется при помощи хеш-функции.
Вопросы о хешировании, часто задаваемые на собеседованиях:
· Найдите симметричные пары в массиве
· Отследите полную траекторию пути
· Найдите, является ли массив подмножеством другого массива
· Проверьте, являются ли массивы непересекающимися
Выше описаны восемь важнейших структур данных, которые определенно нужно знать, прежде чем идти на собеседование по программированию.
Дата добавления: 2020-01-07; просмотров: 214; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!