8 известных структур данных, о которых спросят на собеседовании

Сайт proglib.io опубликовал перевод статьи  “The top data structures you should know for your next coding interview” с разбором 8 основных структур данных, которые должен знать каждый разработчик. Проверьте свои теоретические знания.

Известные структуры данных

Никлаус Вирт, швейцарский информатик, написал в 1976 году книгу под названием «Алгоритмы + структуры данных = программы».

Больше сорока лет спустя это уравнение все еще верно. Почти все задачи программирования требуют от разработчика глубокого понимания структур данных. Вопросы на эту тему обязательно встречаются на любом IT-собеседовании.

Иногда в этих вопросах явно упоминается искомая структура, например, «дано двоичное дерево». В других случаях это не столь очевидно, например, «мы хотим отслеживать количество книг, связанных с каждым автором».

Изучение структур данных имеет важное значение, даже если вы не ищете новую работу, а просто хотите улучшить текущую. Давайте начнем с понимания основ.

Что такое структуры данных?

Простыми словами, структура данных – это контейнер, который хранит информацию в определенном виде. Из-за такой «компоновки» она может быть эффективной в одних операциях и неэффективной в других. Цель разработчика – выбрать из существующих структур оптимальный для конкретной задачи вариант.

Зачем нужны структуры данных?

Данные являются самой важной сущностью в информатике, а структуры позволяют хранить их в организованной форме.

Какую бы проблему вы не решали, вам приходится иметь дело с данными — будь то зарплата сотрудника, цены на акции, список покупок или даже простой телефонный справочник.

В зависимости от ситуации данные должны храниться в некотором определенном формате. Структуры данных предлагают несколько вариантов таких размещений.

8 часто используемых структур

Давайте сначала перечислим наиболее часто используемые структуры данных, а затем рассмотрим их одну за другой:

  • Массив (Array)
  • Стек (Stack)
  • Очередь (Queue)
  • Связный список (Linked List)
  • Дерево (Tree)
  • Граф (Graph)
  • Префиксное дерево (Trie)
  • Хэш-Таблица (Hash Table)

Массивы

Массив – это самая простая и наиболее широко используемая из структур. Стеки и очереди являются производными от массивов.

Вот изображение простого массива размером 4, содержащего элементы (1, 2, 3 и 4).

Массивы

Каждому из них присваивается неотрицательное числовое значение – индекс, который соответствует позиции этого элемента в массиве. Большинство языков определяют начальный индекс массива как 0.

Существует два типа массивов:

  • Одномерные массивы (как на картинке).
  • Многомерные массивы (массивы массивов).

Основные операции с массивами

  • Insert – вставка.
  • Get – получение элемента.
  • Delete – удаление.
  • Size – получение общего количества элементов в массиве.

Частые вопросы о массивах

Стеки

Мы все знакомы с опцией Отменить (Undo), которая присутствует практически в каждом приложении. Вы когда-нибудь задумывались, как это работает?

Для этого вы сохраняете предыдущие состояния приложения (определенное их количество) в памяти в таком порядке, что последнее сохраненное появляется первым. Это не может быть сделано только с помощью массивов. Здесь на помощь приходит стек.

Пример стека из реальной жизни – куча книг, лежащих друг на друге. Чтобы получить книгу, которая находится где-то в середине, вам нужно удалить все, что лежит сверху. Так работает метод LIFO (Last In First Out, последним пришел – первым ушел).

Вот изображение стека, содержащего три элемента (1, 2 и 3). Элемент 3 находится сверху и будет удален первым:

Стеки

Основные операции со стеками

  • Push – вставка элемента наверх стека.
  • Pop – получение верхнего элемента и его удаление.
  • isEmpty – возвращает true, если стек пуст.
  • Top – получение верхнего элемента без удаления.

Часто задаваемые вопросы о стеках

  • Вычисление постфиксного выражения с помощью стека.
  • Сортировка значений в стеке.
  • Проверка сбалансированности скобок в выражении.

Очереди

Как и стек, очередь – это линейная структура данных, которая хранит элементы последовательно. Единственное существенное различие заключается в том, что вместо использования метода LIFO, очередь реализует метод FIFO (First in First Out, первым пришел – первым ушел).

Идеальный пример этих структур в реальной жизни – очереди людей в билетную кассу. Если придет новый человек, он присоединится к линии с конца, а не с начала. А человек, стоящий впереди, первым получит билет и, следовательно, покинет очередь.

Вот изображение очереди, содержащей четыре элемента (1, 2, 3 и 4). Здесь 1 находится вверху и будет удален первым:

Очереди

Основные операции с очередями

  • Enqueue – вставка в конец.
  • Dequeue – удаление из начала.
  • isEmpty – возвращает true, если очередь пуста.
  • Top – получение первого элемента.

Часто задаваемые вопросы об очередях

  • Реализация стека с помощью очереди.
  • Развернуть первые k элементов.
  • Генерация двоичных чисел от 1 до n с помощью очереди.

Связный список

Еще одна важная линейная структура данных, которая на первый взгляд похожа на массив, но отличается распределением памяти, внутренней организацией и способом выполнения основных операций вставки и удаления.

Связный список – это сеть узлов, каждый из которых содержит данные и указатель на следующий узел в цепочке. Также есть указатель на первый элемент – head. Если список пуст, то он указывает на null.

Связные списки используются для реализации файловых систем, хэш-таблиц и списков смежности.

Вот визуальное представление внутренней структуры связного списка:

Связный список

Типы связных списков:

  • Однонаправленный
  • Двунаправленный

Основные операции со связными списками

  • InsertAtEnd – вставка в конец.
  • InsertAtHead – вставка в начало.
  • Delete – удаление указанного элемента.
  • DeleteAtHead – удаление первого элемента.
  • Search – получение указанного элемента.
  • isEmpty – возвращает true, если связный список пуст.

Часто задаваемые вопросы о связных списках

  • Разворот связного списка.
  • Обнаружение цикла.
  • Получение N-го узла с конца.
  • Удаление дубликатов.

Графы

Граф представляет собой набор узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x, y) называется ребром, которое указывает, что вершина x соединена с вершиной y. Ребро может содержать вес/стоимость, показывая, сколько затрат требуется, чтобы пройти от x до y.

Графы

Типы графов:

  • Неориентированный
  • Ориентированный

В языке программирования графы могут быть представлены в двух формах:

Общие алгоритмы обхода графов:

  • В ширину
  • В глубину

Часто задаваемые вопросы о графах

Деревья

Дерево – это иерархическая структура данных, состоящая из вершин (узлов) и ребер, соединяющих их. Они похожи на графы, но есть одно важное отличие: в дереве не может быть цикла.

Деревья широко используются в искусственном интеллекте и сложных алгоритмах для обеспечения эффективного механизма хранения данных.

Вот изображение простого дерева, и основные термины:

Деревья

Типы деревьев:

Из всех типов чаще всего используются бинарное дерево и бинарное дерево поиска.

Часто задаваемые вопросы о деревьях

  • Высота бинарного дерева.
  • Найти k-ое максимальное значение в дереве бинарного поиска.
  • Узлы на расстоянии k от корня.
  • Предки заданного узла в бинарном дереве.

Префиксное дерево

Префиксные деревья (tries) – древовидные структуры данных, эффективные для решения задач со строками. Они обеспечивают быстрый поиск и используются преимущественно для поиска слов в словаре, автодополнения в поисковых системах и даже для IP-маршрутизации.

Вот иллюстрация того, как три слова top, thus и their хранятся в префиксном дереве:

Префиксное дерево

Слова размещаются сверху вниз. Выделенные зеленым элементы показывают конец каждого слова.

Часто задаваемые вопросы о префиксных деревьях

  • Общее количество слов.
  • Вывод всех слов.
  • Сортировка элементов массива.
  • Формирование слов из словаря.
  • Создание словаря T9.

Хеш-Таблица

Хеширование – это процесс, используемый для уникальной идентификации объектов и хранения каждого из них в некотором предварительно вычисленном уникальном индексе – ключе. Итак, объект хранится в виде пары ключ-значение, а коллекция таких элементов называется словарем. Каждый объект можно найти с помощью его ключа. Существует несколько структур, основанных на хешировании, но наиболее часто используется хеш-таблица, которая обычно реализуется с помощью массивов.

Производительность структуры зависит от трех факторов:

  • функция хеширования;
  • размер хеш-таблицы;
  • метод обработки коллизий.

Вот иллюстрация того, как хэш отображается в массиве. Индекс вычисляется с помощью хеш-функции.

Хеш-Таблица

Часто задаваемые вопросы о хеш-таблицах

  • Найти симметричные пары.
  • Определить, является ли массив подмножеством другого массива.
  • Проверить, являются ли массивы непересекающимися.

Теперь вы знаете 8 основных структур данных любого языка программирования. Можете смело отправляться на IT-собеседование.


[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

https://beverlywoodbakery.com/ deneme bonusugrandpashabetgrandpashabet1winküçükçekmece escorthttps://www.bakirkoyfal.com/kagithane escortatakoy escortatakoy escorthttps://halkaliescortmanken.xyz/lara konyaaltı escorttaraftarium24dumanbetdeneme bonusu veren sitelerkadıköy escortümraniye escortistanbul escortbasaksehir escortşişli escortholiganbethttps://www.escortbayanlariz.net/imajbetmavibetextrabetromabetromabetromabetkartal escorttipobetultrabet twitterportobetcasibommecidiyeköy escortjojobet girişdeneme bonusu veren casino siteleribatumi escortcasibom girişcasibom güncel girişcasibomholiganbetholiganbetcasibomhttps://vheshop.com/casibombetwooncasibomsahabetbetpark girişmavibet girişsekabet girişnakitbahiszbahisbahiscomotobetbetturkeybets10sheratonbetbelugabahis güncel girişcasibomaresbetgrandpashabetbetcioextrabetimajbetmavibetnakitbahismahmutbey escortDeneme Bonusugrandpashabetdeneme bonusu veren sitelergrandpashabetgrandpashabetvaycasinograndpashabetcasino siteleriDeneme Bonusu Veren SitelerAlanya EscortDeneme Bonusu Veren SitelervaycasinonakitbahisGrandpashabetJojobetbetgarantiperabetsekabetholiganbet girişcasibombetgarantimariobetsekabet girişcasibom girişbetcio girişvaycasinobetcio girişmavibetbetwoongrandpashabetcasibomcasibom girişdeneme bonusu veren sitelergrandpashabetdeneme bonusu veren sitelerholiganbetbahsegeldeneme bonusu veren sitelereditörbet betparktimebetpadişahbetbettiltkumar sitelerideneme bonusudeneme bonusutürk ifşaHoliganbet girişHoliganbet girişpusulabet1xbetvbetvaycasino girişvaycasino güncel girişbaklavarestbetmarsbahisklasbahisdeneme bonusuvaycasinodeneme bonususdsdgrandpashabetsahabet girişholiganbet girişotobetholiganbet güncel giriş1xbetgrandpashabetcasibom
Прокрутить вверх