Структуры данных для собеседования на java developer

Структуры данных для собеседования на java developer

Небольшой дисклеймер. Эта статья рассчитана на повторение и/или изучение основных структур данных для собеседования на java developer позицию.
Ссылка на оригинал статьи от ex-Facebook и ex-Microsoft разработчика Fahim ul Haq

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

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

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

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

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

Структура данных, что это?

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

Зачем нам знать структуры данных перед собеседованием?

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

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

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

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

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

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

Массивы

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

data structure

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

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

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

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

  • Insert-вставка элемента по заданному индексу
  • Get — возвращает элемент по указанному индексу
  • Delete-удаление элемента с заданным индексом
  • Size— получить общее количество элементов в массиве

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

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

Стеки/стопки

Мы все знакомы с известным вариантом отмены (Undo – ctrl+z  прим. автора перевода), который присутствует почти в каждом приложении. Когда-нибудь задумывались, как это работает? Идея: вы сохраняете предыдущие состояния вашей работы (которые ограничены определенным числом) в памяти в таком порядке, что последнее появляется первым. Это не может быть сделано только с помощью массивов. То есть это реализуется с помощью стека.

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

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

data structure

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

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

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

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

Очередь

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

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

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

data structure
Основные операции очереди
  • Enqueue () – вставляет элемент в конец очереди
  • Dequeue () – удаляет элемент из начала очереди
  • isEmpty () – возвращает true, если очередь пуста
  • Top () – возвращает первый элемент очереди
Часто задаваемые вопросы интервью очереди
  • Реализовать стек с помощью очереди
  • Обратного первые k элементов очереди
  • Генерировать двоичные числа от 1 до n, используя очередь

Связанные списки

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

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

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

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

data structure

 

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

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

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

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

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

  • Реверс связанного списка
  • Обнаружение цикла в связанном списке
  • Возвращает N-й узел из конца в связанном списке
  • Удаление дубликатов из связанного списка

Graphs

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

data structure

 

тип графика:

  • неориентированный граф
  • ориентированный граф

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

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

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

  • Поиск По Ширине
  • Поиск по глубине

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

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

Деревья

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

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

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

data structure

Ниже перечислены типы деревьев:

  • N-ary дерево
  • сбалансированное дерево
  • бинарное дерево
  • Двоичное Дерево Поиска
  • Дерево AVL
  • Красное Черное Дерево
  • 2-3 дерево

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

  • Найти высоту двоичного дерева
  • K-е максимальное значение в двоичном дереве поиска
  • Идентифицировать узлы на расстоянии ” k” от корня
  • Поискать предков данного узла в двоичном дереве

Попытка или Префиксные деревья

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

Вот иллюстрация того, как три слова “top”, “thus” и “their” хранятся в Trie:

data structure

Слова хранятся сверху вниз, где зеленые цветные узлы “p”, “s” и “r” указывают конец “top”, “thus” и “their” соответственно.

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

  • Количество общее количество слов в Trie
  • Напечатать все слова, хранящиеся в боре
  • Элементов сортировка массива с помощью дерева
  • Форма слова из словаря с помощью Trie
  • Создание словаря T9

Хэш Таблицы

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

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

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

  • функция хеширования
  • Размер хэш-таблицы
  • Способ Управления Столкновением

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

data structure

Часто задаваемые вопросы интервью хэширования

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

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

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

Отставить отзыв

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