Информация

Дата основания
2004
Местоположение
США
Сайт
alconost.com
Численность
201–500 человек
Дата регистрации

Блог на Хабре

Обновить
82,71
Рейтинг
Alconost
Локализуем на 70 языков, делаем видеоролики для IT

Важнейшие структуры данных, которые вам следует знать к своему собеседованию по программированию

Блог компании AlconostПрограммированиеРазработка мобильных приложенийРазработка игрКарьера в IT-индустрии
Автор оригинала: Fahim ul Haq


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

Через 40 с лишним лет это тождество остается в силе. Вот почему соискатели, желающие стать программистами, должны продемонстрировать, что знают структуры данных и умеют их применять.

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

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

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

Переведено в Alconost



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


Если коротко, структура данных — это контейнер, информация в котором скомпонована характерным образом. Благодаря такой «компоновке», структура данных будет эффективна в одних операциях и неэффективна — в других. Наша цель — разобраться в структурах данных таким образом, чтобы вы могли выбрать из них наиболее подходящую для решения конкретной стоящей перед вами задачи.

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


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

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

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

Наиболее распространенные структуры данных


Сначала давайте перечислим наиболее распространенные структуры данных, а затем разберем каждую по очереди:

  1. Массивы
  2. Стеки
  3. Очереди
  4. Связные списки
  5. Деревья
  6. Графы
  7. Боры (в сущности, это тоже деревья, но их целесообразно рассмотреть отдельно).
  8. Хеш-таблицы

Массивы


Массив — это простейшая и наиболее распространенная структура данных. Другие структуры данных, например, стеки и очереди, производны от массивов.

Здесь показан простой массив размером 4, содержащий элементы (1, 2, 3 и 4).

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

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

  • Одномерные (такие, как показанный выше)
  • Многомерные (массивы, в которые вложены другие массивы)

Простейшие операции с массивами


  • Insert — вставляем элемент на позицию с заданным индексом
  • Get — возвращаем элемент, занимающий позицию с заданным индексом
  • Delete — удаляем элемент с заданным индексом
  • Size — Получаем общее количество элементов в массиве

Вопросы по массивам, часто задаваемые на собеседованиях


  • Найти второй минимальный элемент массива
  • Найти неповторяющиеся целые числа в массиве
  • Объединить два отсортированных массива
  • Переупорядочить положительные и отрицательные значения в массиве

Стеки


Всем известна знаменитая опция «Отмена», предусмотренная почти во всех приложениях. Задумывались когда-нибудь, как она работает? Смысл такой: в программе сохраняются предшествующие состояния вашей работы (количество сохраняемых состояний ограничено), причем, они располагаются в памяти в таком порядке: последний сохраненный элемент идет первым. Одними массивами такую задачу не решить. Именно здесь нам пригодится стек.

Стек можно сравнить с высокой стопкой книг. Если вам нужна какая-то книга, лежащая около центра стопки, вам сначала придется снять все книги, лежащие выше. Именно так работает принцип LIFO (Последним пришел — первым вышел).

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

Простейшие операции со стеком:

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

Вопросы о стеке, часто задаваемые на собеседованиях


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

Очереди


Очередь, как и стек — это линейная структура данных, элементы в которой хранятся в последовательном порядке. Единственное существенное отличие между стеком и очередью заключается в том, что в очереди вместо LIFO действует принцип FIFO (Первым пришел — первым вышел).

Идеальный реалистичный пример очереди — это и есть очередь покупателей в билетную кассу. Новый покупатель становится в самый хвост очереди, а не в начало. Тот же, кто стоит в очереди первым, первым приобретет билет и первым ее покинет.

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


Простейшие операции с очередью


  • Enqueue() — Добавляет элемент в конец очереди
  • Dequeue() — Удаляет элемент из начала очереди
  • isEmpty() — Возвращает true, если очередь пуста
  • Top() — Возвращает первый элемент в очереди

Вопросы об очередях, часто задаваемые на собеседованиях


  • Реализуйте стек при помощи очереди
  • Обратите первые 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

Хеш-таблица


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

Как правило, хеш-таблицы реализуются при помощи массивов.

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

  • Хеш-функция
  • Размер хеш-таблицы
  • Метод обработки коллизий

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


Вопросы о хешировании, часто задаваемые на собеседованиях:



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

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

Удачи и интересного обучения! :)

О переводчике

Перевод статьи выполнен в Alconost.

Alconost занимается локализацией игр, приложений и сайтов на 68 языков. Переводчики-носители языка, лингвистическое тестирование, облачная платформа с API, непрерывная локализация, менеджеры проектов 24/7, любые форматы строковых ресурсов.

Мы также делаем рекламные и обучающие видеоролики — для сайтов, продающие, имиджевые, рекламные, обучающие, тизеры, эксплейнеры, трейлеры для Google Play и App Store.

Подробнее
Теги:программированиеразработкаинтервьюАлконостAlconostструктуры данных
Хабы: Блог компании Alconost Программирование Разработка мобильных приложений Разработка игр Карьера в IT-индустрии
Рейтинг +6
Количество просмотров 49,5k Добавить в закладки 389
Комментарии
Комментарии 17

Похожие публикации

Лучшие публикации за сутки