12 важнейших структур данных для технических собеседований

1. Массивы

* Коллекция элементов фиксированного размера, хранящихся в непрерывной области памяти

* Обеспечивает доступ по индексу за O(1)

2. Матрица (двумерный массив)

* Многомерная структура данных для представления сеток, графов и решения задач динамического программирования

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

* Динамическая структура данных, где элементы (узлы) связаны через указатели

* Типы: односвязный список, двусвязный список, кольцевой связный список

4. Стек

* Структура данных типа Last-In-First-Out (LIFO), где последний добавленный элемент удаляется первым

* Поддерживает операции push, pop и peek за O(1)

5. Очередь

* Структура данных типа First-In-First-Out (FIFO)

* Позволяет добавлять элементы в конец (enqueue) и удалять из начала (dequeue) за O(1)

* Используется для обработки элементов в том же порядке, в котором они были добавлены

6. Хеш-таблица

* Структура данных типа "ключ-значение", использующая хеш-функцию для быстрого поиска

* Обеспечивает среднее время O(1) для операций вставки/удаления/поиска, в худшем случае O(N) (из-за коллизий)

7. Дерево

* Иерархическая структура данных с корневым узлом и дочерними узлами

* Типы: бинарное дерево, N-арное дерево, AVL-дерево, красно-чёрное дерево

8. Бинарное дерево поиска (BST)

* Специальное дерево, где левый потомок < корень < правый потомок

* Обеспечивает O(log N) для поиска, вставки и удаления в сбалансированных BST

9. Куча (приоритетная очередь)

* Структура данных на основе бинарного дерева, где родительский элемент всегда больше (max heap) или меньше (min heap) дочерних

* Обеспечивает O(log N) для вставки/удаления и O(1) для получения минимума/максимума

10. Префиксное дерево (Trie)

* Дерево для быстрого поиска строк

* Обеспечивает O(M) для операций вставки/поиска/удаления, где M — длина строки

11. Граф

* Набор узлов (вершин), соединённых рёбрами

* Представляется с помощью списка смежности (эффективно) или матрицы смежности

* Типы: ориентированный, неориентированный, взвешенный, невзвешенный

12. Система непересекающихся множеств (Union-Find / Disjoint Set)

* Структура данных для эффективной обработки динамической связности

* Поддерживает операции Union(x, y) и Find(x) почти за O(1) (с сжатием путей)

* Применяется для обнаружения циклов и поиска компонент связности в графе

Источник: vk.com

Комментарии: