Подготовка к интервью
26 вопросов с ответами по теме «Сложность алгоритмов»
Что проверяют на интервью
Вопросы связывают асимптотическую оценку с устройством алгоритма и структуры данных. Помимо классов сложности, подборка включает анализ памяти, поиск топ-K, пересечение множеств, операции коллекций и сравнение алгоритмов соединения и индексного поиска.
Каталог
В неотсортированном массиве для поиска элемента по ключу обычно требуется перебрать элементы один за другим, пока не будет найден нужный.
Читать ответБыстрая сортировка (in-place) в среднем работает за время O(n log n). По дополнительной памяти она использует стек вызовов рекурсии, глубина которого в среднем составляет O(log n). Таким образом, средние асимптотики:
Читать ответФункция isMonotonic проверяет, является ли массив чисел монотонным — то есть либо не убывающим (каждое следующее число не меньше предыдущего), либо не возрастающим (каждое следующее число не больше предыдущего).
Читать ответВременная сложность удаления элемента из массива зависит от того, где находится элемент и как реализован массив.
Читать ответСложность алгоритма бинарного поиска — O(log n).
Читать ответNested Loop Join — это простой алгоритм соединения двух таблиц, который для каждой строки из первой таблицы перебирает все строки второй таблицы и проверяет условие соединения.
Читать ответВременная сложность алгоритма, равная O(n), означает, что время выполнения алгоритма растёт линейно с увеличением размера входных данных n.
Читать ответСложность указанных операций зависит от высоты дерева.
Читать ответАсимптотическая сложность, обозначаемая как O (большое O), описывает, как время выполнения или использование памяти алгоритмом растёт в зависимости от размера входных данных при стремлении этого размера к бесконечности.
Читать ответQuickSort:
Читать ответСложность вставки элемента в массив структура данных: массив (статический или динамический) добавление в конец динамического массива: амортизированная сложность — O(1) добавление в начало либо середину: необходимо…
Читать ответСложность поиска в B-tree и Hash-индексе B-tree: сбалансированная структура с отсортированными ключами асимптотическая сложность поиска: O(log n) — определяется высотой дерева поиск выполняется переходами между…
Читать ответ