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

Структуры данных

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.

Предварительный заказ (корень, влево, вправо): полезно для создания копий двоичных деревьев или оценки деревьев выражений.

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