Основные структуры данных, которые вы должны знать на следующем собеседовании с кодировкой

1656570260 osnovnye struktury dannyh kotorye vy dolzhny znat na sleduyushhem sobesedovanii

автор Фахим уль Хак

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

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

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

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

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

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

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

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

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

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

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

Часто используемые структуры данных

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

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

Массивы

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

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

изображение-81
B4CncYOv-dN76B45UXdVrfat45MvgQ9b8atv

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

Ниже приведены два типа массивов:

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

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

  • Вставка – вставляет элемент по заданному индексу
  • Получить – возвращает элемент с заданным индексом
  • Удалить — удаляет элемент по заданному индексу
  • Размер – получает общее количество элементов в массиве

Часто задаваемые вопросы на интервью Array

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

Стеки

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

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

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

BP-lD2OxkMbIQI2iZD-jxgIPlANlsMTqwnLP

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

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

Часто задаваемые вопросы по интервью Stack

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

Очереди

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

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

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

C2riLJTPBVpSI-3o5Cx9IrQ16LZi1kLrqYXo

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

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

Часто задаваемые вопросы относительно очереди на собеседовании

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

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

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

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

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

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

ezrkbpSyblh3famnGsgIHiRvHV9CKODu0tPw

Ниже приведены типы связанных списков:

  • Однонаправленный список (однонаправленный)
  • Двухвязанный список (двухсторонний)

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

  • InsertAtEnd — Вставляет заданный элемент в конец связанного списка
  • InsertAtHead — Вставляет заданный элемент в начало/голову связанного списка
  • Удалить — Удаляет заданный элемент из связанного списка
  • DeleteAtHead — Удаляет первый элемент связанного списка
  • Поиск — Возвращает заданный элемент из связанного списка
  • пусто — Возвращает true, если связанный список пуст

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

  • Перевернуть связанный список
  • Выявить цикл в связанном списке
  • Вернуть N-ый узел из конца в связанном списке
  • Удалить дубликаты из списка

Графики

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

0MsvzasAr6vS6bnvozjRAa5iBnEDKn9Cty0D

Типы графиков:

  • Неориентированный график
  • Направленный график

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

  • Матрица смежности
  • Список смежности

Распространенные алгоритмы обхода графа:

  • Поиск в ширину
  • Поиск в глубину

Часто задаваемые вопросы интервью Graph

  • Реализуйте поиск в ширину и глубину
  • Проверьте, есть ли график деревом или нет
  • Подсчитайте количество ребер в графе
  • Найдите кратчайший путь между двумя вершинами

Деревья

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

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

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

VPUnmQO8rMoLGMqMe24EnoJ3uS72JZdMt48w

Вот такие виды деревьев:

  • N-арное дерево
  • Сбалансированное дерево
  • Бинарное дерево
  • Двоичное дерево поиска
  • Дерево AVL
  • Красное черное дерево
  • 2–3 Дерево

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

Часто задаваемые вопросы на интервью с Деревом

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

Попробуй

Trie, также известный как «префиксные деревья», является древовидной структурой данных, которая оказывается достаточно эффективной для решения проблем, связанных со строками. Он обеспечивает быстрый поиск и в основном используется для поиска слов в словаре, предоставления автоматических предложений в поисковике и даже для IP-маршрутизации.

Вот иллюстрация того, как три слова «верх», «да» и «их» хранятся в Trie:

lSNi21Wr4P6eMKDwLMQ5rijHhA-lBlovlc40-1

Слова сохраняются сверху вниз, где зеленые узлы «p», «s» и «r» указывают на конец «верх», «таким образом» и «их» соответственно.

Часто задаваемые вопросы на собеседовании с Три:

  • Ссчитайте общее количество слов в Три
  • Напечатайте все слова, сохраненные в Trie
  • Сортируйте элементы массива с помощью Trie
  • Создайте слова из словаря с помощью Trie
  • Создайте словарь T9

Хэш-таблица

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

Хэш-таблицы обычно реализуются с помощью массивов.

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

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

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

zV3x2Pxt0JFt7UjokTKNx24HFmM3t-6phDV2

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

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

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

Если вы ищете ресурсы о структуре данных для интервью с кодировкой, просмотрите интерактивные курсы, основанные на вызовах: Структуры данных для интервью с кодировкой (Python, Java или JavaScript).

Для получения дополнительных вопросов см. Coderust 3.0: Быстрая подготовка к интервью с кодировкой с интерактивными задачами и визуализациями.

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

Удачи и приятного обучения! 🙂

Добавить комментарий

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