Мне нужна была краткая, полная и правильная шпаргалка для быстрого обзора технических собеседований, но я не мог найти удовлетворительную в Интернете, поэтому Я создал свою. Время выполнения относится к среднему времени выполнения. Версию со скидкой можно найти здесь. Не стесняйтесь разветвлять его и изменять по своему усмотрению. Пожалуйста, прокомментируйте ошибки или пропущенные важные концепции.
Структуры данных
1 динамический массив
Последовательно сохраненные данные в непрерывном фрагменте памяти. Удвойте текущую емкость при достижении емкости. При увеличении емкости он выделяет новый фрагмент памяти и копирует предыдущие значения в новое место.
Время выполнения
- индексирование: O (1)
- поиск: O (n)
- вставка: O (n)
- push: O (n) Примечание. O (1) Амортизировано
- удаление: O (n)
2 Связанный список
Чаще всего относится к односвязному списку. Данные хранятся в узлах, где каждый узел имеет ссылку на следующий узел. Есть двусвязный список и круговой список.
Время выполнения
- индексирование: O (n)
- поиск: O (n)
- вставка: O (1)
- удаление: O (1)
Стек и очередь часто реализуются со связным списком, потому что связанный список наиболее эффективен для вставки / удаления, которые являются наиболее часто используемыми операциями для стеков / очередей.
Стек последний пришел - первый ушел (LIFO)
Очередь в порядке очереди (FIFO)
3 Хеш-таблица (хеш-карта)
Обычно неупорядоченная структура данных, которая сопоставляет ключи со значениями. Хэш (предпочтительно уникальный) вычисляется для данного ключа, и его значение будет сохранено в соответствующих ячейках или индексе в соответствии с хешем. Внутренне бункеры могут быть массивом. Конфликт может произойти, когда несколько ключей сопоставлены с одним и тем же хешем. Обычное решение - хранить список / связанный список в каждой ячейке / индексе (это называется цепочкой).
Время выполнения
- поиск значения: O (1)
- вставка: O (1)
- удаление: O (1)
4 Дерево двоичного поиска (BST)
Двоичное дерево с дополнительным условием, что каждый узел больше или равен всем узлам в левом поддереве и меньше или равен всем узлам в правом поддереве.
Время выполнения
- поиск: O (журнал n)
- вставка: O (журнал n)
- удаление: O (журнал n)
5 Heap (максимальная куча / минимальная куча)
Бинарное дерево с условием, что значение родительского узла больше / меньше его дочерних узлов. Таким образом, root - это максимум в максимальной куче и минимум в минимальной куче. Очередь с приоритетом также называется кучей, потому что она обычно реализуется с помощью кучи.
Время выполнения
- мин. / макс .: O (1)
- вставка: O (журнал n)
- удаление: O (журнал n)
Алгоритмы
1 Сортировка
Пузырьковая сортировка. Итерируйте по всему списку, сравнивая пары, и меняйте позиции на основе их значений, пока все элементы не будут отсортированы.
- O (n²), но быстро, если список почти отсортирован.
Сортировка вставкой: просматривает несортированный список при построении отсортированного списка. Для каждого значения, встречающегося в несортированном списке, найдите подходящее место в отсортированном списке и вставьте его.
- O(n²).
Сортировка слиянием Тип алгоритма «разделяй и властвуй»: 1) делит список на два подсписка одинакового размера 2) сортирует каждый подсписок 3) объединяет два отсортированных списка в окончательный список.
- O (n log n) - необходимо разделить log n раз, и для каждого деления необходимо пройти все n элементов для объединения , таким образом n раз log n.
Куча Сортировка 1) Создайте кучу (минимальную или максимальную) из несортированного списка 2) несколько раз удалите корневой узел из кучи и поместите в отсортированный список.
- O (n log n) - удаление корневого узла равно O (log n), и его необходимо повторить для каждого узла, таким образом, n раз зарегистрировать.
Быстрая сортировка Тип алгоритма «разделяй и властвуй»: 1) выберите элемент в несортированном списке в качестве сводного 2) разделите список на 2 подсписка, один из которых содержит элементы меньше, чем сводный, а другой - элементы больше, чем стержень 3) отсортируйте подсписки и объедините результаты в окончательный список
- O (n log n) - необходимо разделить O (log n) раз, и после каждого деления разбиение должно проходить через все элементы, таким образом, общее время выполнения n раз зарегистрировать n.
2 Поиск
Линейный поиск O (n)
Двоичный поиск O (журнал n)
Поиск в ширину (BFS) Сначала братья и сестры, затем дети. Обычно используют очередь.
Поиск в глубину (DFS) Сначала дети, затем братья и сестры. Обычно используют стек.
A * Search Цель состоит в том, чтобы найти кратчайший путь между двумя узлами на графике. Это поиск по принципу "сначала лучшее". На каждой итерации он находит следующий узел для расширения пути на основе критерия g (next) + h (next), где g - расстояние от следующего узла до начального узла. и h - эвристическое (оценочное) расстояние от следующего узла до конечного узла. обычно используют кучу.
3 обхода дерева
Inorder (Left, Root, Right): полезно для получения отсортированного списка из BST.
Предварительный заказ (корень, влево, вправо): полезно для создания копий двоичных деревьев или оценки деревьев выражений.
Поступорядочение (влево, вправо, корень): полезно для удаления деревьев (поскольку необходимо удалить дочерние элементы перед удалением родителя).