Алгоритмы и структуры данных: вопросы на собеседовании

O-нотация описывает асимптотический рост числа операций при увеличении размера входа, отбрасывая константы и младшие члены. O(2n + 5) — это O(n).

Различайте три оценки: худший случай (обычно её и спрашивают), средний и лучший. Отдельно оценивается память — O(1) дополнительной памяти часто важнее скорости.

Задача: найти дубликат.

1. Два вложенных цикла — время O(n²), память O(1).
2. Сортировка и сравнение соседей — время O(n log n), память O(1) при сортировке на месте.
3. Хеш-множество — время O(n), память O(n).

function hasDuplicate(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Это и есть главный размен в алгоритмах — время против памяти. На собеседовании озвучьте оба варианта и объясните выбор.

Хеш-таблица — массив «корзин». Ключ пропускается через хеш-функцию, результат берётся по модулю размера массива и даёт индекс корзины.

Коллизии (разные ключи в одну корзину) решают двумя способами:

• цепочки — в корзине связный список или дерево;
• открытая адресация — ищем следующую свободную ячейку (линейное, квадратичное пробирование, двойное хеширование).

Сложность: при равномерном хеше и невысоком коэффициенте заполнения — O(1) в среднем. В худшем случае, когда все ключи попали в одну корзину, поиск вырождается в O(n). Реализации борются с этим: при превышении load factor (обычно 0.75) таблица рехешируется с удвоением размера — отсюда амортизированная O(1) на вставку. В Java 8+ длинная цепочка превращается в красно-чёрное дерево, давая O(log n).

Практика: ключ должен быть иммутабельным и иметь согласованные hashCode/equals — иначе объект «потеряется» в таблице.

Массив (динамический):

• доступ по индексу — O(1);
• вставка и удаление в середине — O(n) (сдвиг элементов);
• добавление в конец — амортизированно O(1);
• данные лежат непрерывно → отличная локальность кеша, реальная скорость часто выше теоретической.

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

• доступ по индексу — O(n);
• вставка и удаление — O(1), если у вас уже есть ссылка на узел;
• на каждый элемент — накладные расходы на указатели, элементы разбросаны по памяти → промахи кеша.

Вывод: по умолчанию берите массив. Связный список оправдан, когда вы часто удаляете и вставляете элементы, имея ссылку на узел — например, LRU-кеш (двусвязный список + хеш-таблица), реализация очереди, списки свободных блоков в аллокаторах.

На практике ArrayList обгоняет LinkedList даже на вставках в середину при небольших размерах — из-за кеша процессора.

Бинарный поиск работает только на отсортированных данных, сложность O(log n).

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Классические ошибки:

1. (lo + hi) / 2 — переполнение в языках с фиксированным int. Пишите lo + (hi - lo) / 2.
2. while (lo < hi) вместо <= при границе hi = length - 1 — потеря последнего элемента.
3. lo = mid вместо lo = mid + 1 — бесконечный цикл.

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

Quick sort. Выбираем опорный элемент, разделяем массив на меньшие и большие, рекурсивно сортируем части.

• Время: O(n log n) в среднем, O(n²) в худшем (плохой выбор опорного на уже отсортированных данных).
• Память: O(log n) на стек рекурсии, сортирует на месте.
• Не стабильна.
• На практике самая быстрая из-за локальности кеша.

Merge sort. Делим пополам, рекурсивно сортируем, сливаем.

• Время: O(n log n) гарантированно, в любом случае.
• Память: O(n) на буфер слияния.
• Стабильна — сохраняет относительный порядок равных элементов.
• Единственный разумный выбор для связных списков и внешней сортировки файлов, не влезающих в память.

Что используется в реальности: гибриды. Timsort (Python, Java для объектов) — merge + insertion, использует уже отсортированные участки. Introsort (C++ std::sort) — quick с переходом на heap sort при глубокой рекурсии, чтобы гарантировать O(n log n).