17 разобранных вопросов по теме «Алгоритмы». Каждый — с правильным ответом и пояснением.

• Как работает бинарный поиск?

  Только для отсортированного массива. Берём середину, сравниваем с искомым. Если меньше — ищем в левой половине, больше — в правой. Каждая итерация — ÷2. Сложность O(log n).

• Как устроена хэш-таблица и как разрешаются коллизии?

  Массив бакетов. По хэшу ключа определяется индекс. Две стратегии разрешения коллизий: (1) Chaining (цепочки) — в бакете связный список (или дерево). (2) Open addressing (открытая адресация) — элемент ищет следующий свободный слот в самом массиве (линейное/квадратичное пробирование, double hashing).

• Какая сложность у бинарного поиска?

  O(log n). Каждая итерация уменьшает область поиска вдвое.

• Какие сортировки знаешь?

  Простые O(n²): пузырёк (bubble), выбор (selection), вставка (insertion). Эффективные O(n log n): merge sort (через слияние), quick sort (через разбиение), heap sort (через кучу). Специфичные: counting sort O(n+k). При этом quick sort в худшем случае деградирует до O(n²), а merge sort требует O(n) доп. памяти.

• Какую сортировку использует Java по умолчанию?

  Для массивов примитивов — Dual-Pivot Quicksort. Для объектов — Timsort (гибрид merge и insertion sort, разработан для Python, перенесён в Java). Timsort стабилен и эффективен на реальных данных, а для примитивов стабильность не важна — важна скорость.

• Что делаешь, если задача непонятна?

  Алгоритм: (1) Перечитываю требования, формулирую вопрос. (2) Гуглю / читаю документацию. (3) Спрашиваю коллегу или ментора. (4) Не пропадаю на полдня молча — приношу промежуточный результат и обсуждаю, чтобы проактивно прояснить неопределённость.

• Что такое AVL и красно-чёрное дерево?

  Самобалансирующиеся BST. После каждой вставки/удаления выполняется ребалансировка через повороты — гарантия O(log n). AVL — строже балансируется (быстрее поиск, медленнее вставка), красно-чёрное балансируется слабее (дешевле вставки, чуть медленнее поиск).

• Что такое BFS и DFS?

  BFS (Breadth-First Search) — обход в ширину: идёт по уровням через очередь, даёт кратчайший путь в невзвешенном графе. DFS (Depth-First Search) — обход в глубину: уходит вглубь ветви через стек или рекурсию.

• Что такое Big-O?

  Способ описать асимптотическую сложность алгоритма — как растёт время (или память) с ростом входа, без учёта констант, железа и языка. O(1) — константа, O(log n) — логарифм (бинарный поиск), O(n) — линейная (один проход), O(n^2) — квадратичная.

• Что такое бинарное дерево поиска (BST)?

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

• Что такое дек?

  Двусторонняя очередь. Можно добавлять и удалять с обоих концов. В Java — Deque interface, реализация ArrayDeque. Универсальная — может работать как стек и как очередь.

• Что такое жадный алгоритм?

  На каждом шаге делаешь локально оптимальный выбор, надеясь, что в итоге получится глобально оптимальное решение. Работает не всегда (нужно доказывать)! Пример где работает: размен сдачи стандартными монетами.

• Что такое метод двух указателей?

  Используем два индекса, движущиеся по массиву по правилам. Часто для отсортированного массива: пара с заданной суммой, разворот строки, проверка палиндрома. Сложность обычно O(n).

• Что такое очередь и где применяется?

  FIFO (First In, First Out). Используется в: (1) Обход графа в ширину (BFS). (2) Планировщик задач. (3) Producer-consumer (BlockingQueue). В Java — LinkedList, ArrayDeque, или ConcurrentLinkedQueue для многопоточности.

• Что такое префиксная сумма?

  Массив, где prefix[i] = sum(arr[0..i]). Позволяет за O(1) узнать сумму на отрезке [l..r]: sum(l..r) = prefix[r] - prefix[l-1]. Полезно когда много запросов сумм на разных отрезках одного массива.

• Что такое скользящее окно?

  Поддерживаем «окно» — диапазон [left, right] в массиве. Двигаем right (расширяем), при нарушении условия — двигаем left (сужаем). Используется для подстрок без повторов, максимума в окне фиксированного размера. Сложность O(n).

• Что такое стек и где применяется?

  LIFO (Last In, First Out). Используется в: (1) вызовы функций в JVM (stack frames). (2) Undo / отмена операций. (3) Парсинг (проверка корректности скобок). (4) Обход дерева в глубину (DFS).