30 лучших структур данных и алгоритмов интервью, вопросы и ответы [для новичков и опытных]

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

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

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

Лучшие структуры данных и алгоритмы Интервью Вопросы и ответы

1. Что вы понимаете под «Структурами данных»?

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

2. Как можно отличить файловую структуру от структуры данных?

В файловых структурах данные хранятся на дисках в соответствии со стандартными политиками хранения файлов и несовместимы с внешними сторонними приложениями. С другой стороны, в структурах данных данные хранятся как на диске, так и в ОЗУ в настраиваемых политиках хранения, и они хорошо совместимы с внешними приложениями.

3. Каковы общие типы структур данных?

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

• Линейный: в этом случае все элементы хранятся последовательно, а поиск происходит линейно. Расположение неиерархическое, и у каждого элемента есть один преемник и один предшественник. Пример — массивы, связанные списки, стеки, очереди и т. д.
• Нелинейный: здесь хранение происходит не в линейной последовательности, т. е. все элементы не обязательно имеют только одного преемника и предшественника. Вместо этого элементы в нелинейных структурах данных связаны с двумя или более элементами нелинейным образом. Пример — деревья, графики, кучи.

4. Каковы основные области использования структур данных?

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

• Дизайн операционной системы
• Численный анализ
• Машинное обучение и ИИ
• Дизайн и разработка компилятора
• Управление базой данных
• Лексический анализ
• Графическое программирование
• Алгоритмы поиска и сортировки и многое другое.

5. Объясните структуру данных стека и укажите области ее использования.

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

• Возвращение
• Управление памятью
• Возврат функции и вызов
• Оценка выражения

6. Какие операции можно выполнять со стеком?

Структура данных стека поддерживает следующие три операции:

• push() — для вставки элемента в верхнюю позицию стека.
• pop() — вывести один элемент из вершины стека.
• peek() — чтобы просто проверить элемент, находящийся на вершине стека, не извлекая его из стека.

7. Что вы понимаете в постфиксных выражениях?

Постфиксное выражение — это выражение, в котором операторы следуют за операндами. Это чрезвычайно полезно с точки зрения вычислений, поскольку не требует группировки подвыражений в круглые скобки или даже учета приоритета операторов. Выражение a+b просто представляется как ab+ в постфиксе.

8. Как элементы двумерного массива хранятся в памяти?

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

• Row-Major: в этом методе сначала все строки массива сохраняются в памяти непрерывно. Сначала полностью сохраняется 1-я строка, затем 2-я и так до последней.
• Column-Major: при этом все столбцы массива постоянно хранятся в памяти. Сначала полностью сохраняется 1-й столбец, затем 2-й столбец и так далее.

9. Определите структуру данных связанного списка.

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

10. Чем связные списки лучше массивов?

Связанные списки лучше, чем массивы, в следующих отношениях:

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

11. Какой указатель на языке программирования C вы бы использовали для реализации разнородного связанного списка?

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

12. Что такое двусвязный список?

Как следует из названия, двусвязный список — это связанный список, узлы которого связаны как с последующими, так и с предыдущими узлами. В результате узлы двусвязного списка имеют три, а не два поля:

• Поле данных
• Следующий указатель (для указания следующего узла)
• Предыдущий указатель (для указания предыдущего узла)

13. Объясните структуру данных очереди с некоторыми ее приложениями.

Очередь — это упорядоченный список, который позволяет вставлять и удалять элементы не с одного, а с двух концов, называемых ЗАДНИЙ и ПЕРЕДНИЙ. Вставка происходит с ПЕРЕДНЕГО конца, а удаление с ЗАДНЕГО конца. В результате этого очередь часто называют «первым пришел — первым обслужен» (FIFO). Вот некоторые распространенные применения очередей как структуры данных:

• Для списков ожидания для отдельных общих ресурсов, таких как ЦП, принтер, диск и т. д.
• Для асинхронной передачи данных, пример файлового ввода-вывода, сокетов, каналов.
• В качестве буферов в большинстве приложений медиаплееров.
• В операционных системах для обработки прерываний.

14. Можете ли вы перечислить некоторые недостатки реализации очередей с использованием массивов?

В основном есть два недостатка, которые возникают при реализации очередей с массивами:

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

15. Какие условия должны быть выполнены, чтобы элемент попал в циклическую очередь?

Вот некоторые важные условия вставки в циклические очереди:

• Если (rear + 1)%maxsize == front -> это означает, что очередь заполнена -> вставка больше невозможна.
• Если задний != max – 1, значение заднего увеличивается до максимального размера, а новое значение будет вставлено сзади.
• Если передний != 0 и задний == max -1 --> это означает, что очередь не заполнена. Таким образом, значение Rear устанавливается равным 0, и новый элемент вставляется в задний конец циклической очереди.

16. Что такое dequeue?

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

17. Определите структуру данных дерева и перечислите некоторые типы деревьев.

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

• Общие деревья
• Бинарные деревья
• Бинарные деревья поиска
• Леса
• Дерево выражений
• Дерево турниров

18. Как работает пузырьковая сортировка?

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

Читать: Структуры данных в C и как их использовать?

19. Какой из доступных алгоритмов сортировки является самым быстрым?

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

20. Что такое бинарные деревья?

Двоичные деревья — это специальные типы деревьев, в которых каждый узел может иметь НЕ МЕНЬШЕ двух дочерних элементов. Чтобы упростить задачу, бинарные деревья обычно делятся на три непересекающихся множества — корневой узел, правое поддерево и левое поддерево.

21. Как деревья AVL можно использовать в различных операциях по сравнению с BST?

Деревья AVL — это деревья со сбалансированной высотой, поэтому они не допускают перекоса дерева с какой-либо стороны. Время, затрачиваемое на все операции, выполняемые над BST высоты h, равно O(h). Однако это может продолжаться до O (n) в худшем случае, когда BST становится искаженным. AVL помогает устранить это ограничение, ограничивая высоту дерева. При этом он накладывает верхнюю границу на все операции, которая должна быть максимальной O (log n), где n = количество узлов.

22. Каковы свойства B-дерева?

B-дерево порядка m содержит следующие свойства:

• Все свойства M-дерева путей.
• Каждый узел B_tree будет иметь максимум m дочерних элементов.
• Каждый узел, кроме корня и листа, будет иметь как минимум m/2 потомков.
• Корневой узел должен иметь как минимум 2 дочерних узла.
• Все конечные узлы должны лежать на одном горизонтальном уровне.

23. Что вы понимаете в структуре графических данных?

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

24. Различайте цикл, путь и цепь со ссылкой на структуру данных графа.

Различия между циклом, путем и цепью заключаются в следующем:

• Патч — это порядок соседних вершин, соединенных ребрами без каких-либо ограничений.
• Цикл — это замкнутый путь, начальная вершина которого совпадает с конечной вершиной. В цикле ни одна вершина не может быть посещена дважды.
• Цепь, как и цикл, представляет собой замкнутый путь, начальная вершина которого совпадает с конечной вершиной. Однако любую конкретную вершину цепи можно посетить более одного раза.

25. Как работает алгоритм Крускала?

Алгоритм Крускала рассматривает граф как лес, а каждый его узел — как отдельное дерево. Говорят, что дерево соединяется с другим деревом тогда и только тогда, когда оно имеет наименьшую стоимость среди всех вариантов и не нарушает никаких свойств минимального остовного дерева (MST).

Связанный: Двоичное дерево в структуре данных

26. Как алгоритм Прима находит остовное дерево?

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

27. Что такое минимальное остовное дерево (MST)?

MST во взвешенных графах — это деревья с минимальным весом, но охватывающие все вершины.

28. Что такое рекурсивная функция?

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

29. Что такое метод интерполяционного поиска?

Техника интерполяционного поиска является модификацией метода бинарного поиска. Алгоритм интерполяционного поиска работает с определением положения искомых значений.

30. Что такое хеширование?

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

В заключение

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

Итак, если вы новичок и хотите сделать карьеру в любой из областей нового века, вам рекомендуется начать с освоения структур данных и алгоритмов. Или же вы также можете ознакомиться с нашим курсом Executive PG Program in Data Science , который предназначен для начинающих. Учитесь с нуля и станьте экспертом в области Data Science. Запишитесь сегодня!