Вопросы на собеседовании: Инженер-программист

Нотация Big O показывает, как время работы или потребление памяти алгоритма растёт вместе с размером входных данных.

• Она отбрасывает константы и младшие члены, чтобы инженеры могли сравнивать подходы независимо от железа.
• Проход за O(n) с ростом данных обгонит вложенный цикл за O(n^2), даже если на маленьком входе второй вариант быстрее.
• Она помогает заранее понять, когда код для 100 строк станет слишком медленным или прожорливым на миллионе строк.

Массив удобен для быстрого доступа по индексу, а связный список для вставки или удаления уже известных узлов.

• Массив хранит элементы непрерывно, поэтому даёт доступ по индексу за O(1) и эффективно использует кэш.
• Вставка в середину массива стоит O(n) из-за сдвига элементов, а изменение связного списка у известного узла занимает O(1).
• Доступ к k-му узлу списка требует O(n), поэтому массив выбирают для произвольного доступа, а список для частых изменений в известных позициях.

Хеш-таблица достигает среднего поиска за O(1), вычисляя по ключу индекс корзины в базовом массиве.

• Прямой переход к корзине избавляет от просмотра всех записей.
• Равномерное хеширование и низкий коэффициент заполнения оставляют в каждой корзине лишь несколько записей.
• O(1) является средней оценкой, а не гарантией, поскольку плохой хеш или высокая заполненность могут ухудшить поиск до O(n).

Коллизия в хеш-таблице возникает, когда разные ключи попадают в один индекс корзины.

• При раздельном сцеплении конфликтующие записи хранятся в небольшой коллекции внутри корзины и просматриваются при поиске.
• При открытой адресации таблица проверяет другие ячейки с помощью линейного, квадратичного или двойного хеширования.
• Java HashMap использует сцепление и может превращать длинные цепочки в сбалансированные деревья, сохраняя худший поиск около O(log n).

Стек извлекает элементы по принципу LIFO, а очередь по принципу FIFO.

• Стек первым возвращает последний добавленный элемент, как при вложенных вызовах функций или переходе назад в браузере.
• Очередь первой возвращает самую раннюю задачу, как в очереди печати или пуле воркеров.
• Обе структуры могут давать вставку и удаление за O(1), но забирают элементы с разных концов последовательности.

Бинарный поиск находит значение в отсортированных данных, отбрасывая половину оставшегося диапазона после каждого сравнения.

• Он сравнивает искомое значение со средним элементом и работает за O(log n).
• Данные должны быть заранее отсортированы по ключу поиска, иначе нельзя правильно выбрать отбрасываемую половину.
• Предварительная сортировка стоит O(n log n), поэтому бинарный поиск особенно выгоден для повторных запросов к одним отсортированным данным.

Поиск в сбалансированном двоичном дереве занимает O(log n), потому что каждое сравнение отбрасывает целое поддерево.

• Число шагов поиска ограничено полной высотой дерева от корня до листа.
• В сбалансированном дереве высота остаётся пропорциональной log n.
• Разбалансированное дерево может выродиться в связный список с поиском за O(n), поэтому AVL- и красно-чёрные деревья поддерживают баланс.

Рекурсия представляет собой решение задачи через вызов той же функции для уменьшенной версии этой задачи.

• Базовый случай должен гарантированно останавливать дальнейшую цепочку рекурсивных вызовов.
• Рекурсивный случай должен уменьшать вход и приближаться к базовому случаю.
• Отсутствующий или недостижимый базовый случай вызывает бесконечные вызовы и переполнение стека, поскольку каждый вызов расходует память.

Дерево является ограниченным видом графа, а граф может описывать более общие связи.

• Граф состоит из узлов и рёбер и может быть ориентированным или неориентированным, с циклами или без них.
• Дерево связно, не содержит циклов и имеет ровно один путь между каждой парой узлов.
• В дереве из n узлов есть n минус одно ребро, поэтому каждое дерево является графом, но не каждый граф является деревом.

Поиск в ширину обходит граф по уровням, а поиск в глубину идёт по одной ветке до возврата назад.

• BFS использует очередь и находит кратчайшие пути в невзвешенном графе.
• DFS использует стек или рекурсию и подходит для поиска циклов, топологической сортировки и перебора всех путей.
• Оба работают за O(V + E), но память BFS зависит от самого широкого уровня, а память DFS от самого глубокого пути.

Quicksort разбивает массив относительно опорного элемента и рекурсивно сортирует две полученные части.

• Элементы меньше опорного перемещаются влево, а элементы больше него вправо.
• Удачные опорные элементы делят массив примерно поровну и дают среднюю сложность O(n log n).
• Постоянный выбор крайнего элемента приводит к O(n^2), хотя случайный выбор или медиана из трёх делают это маловероятным на практике.

Стабильный алгоритм сортировки сохраняет взаимный порядок элементов, равных по ключу сравнения.

• Стабильность важна, когда сортировки последовательно применяются по нескольким ключам.
• После сортировки по дате и стабильной сортировки по имени записи с одинаковыми именами сохраняют порядок дат.
• Сортировка слиянием стабильна, а наивный quicksort нет, поэтому выбор алгоритма влияет на сохранение предыдущего порядка.

Стек хранит краткоживущие данные вызовов, а куча хранит динамически выделенные данные с более гибким временем жизни.

• Стек содержит кадры вызовов, локальные переменные и адреса возврата и автоматически очищается в порядке LIFO.
• Выделение в стеке быстрое, но его размер ограничен, тогда как куча больше, медленнее и подвержена фрагментации и утечкам.
• Данные в куче могут пережить создавшую их функцию, а данные стека обычно привязаны к области видимости и времени вызова.

Я бы проверил палиндром двумя указателями, которые движутся к центру строки с противоположных концов.

• На каждом шаге сравнивается пара символов, а первое несовпадение сразу даёт false.
• Подход работает за O(n) времени и O(1) дополнительной памяти, в отличие от развёрнутой копии с O(n) лишней памяти.
• Если этого требует определение палиндрома, я бы сначала выровнял регистр и исключил неалфавитно-цифровые символы.

Алгоритм черепахи и зайца Флойда обнаруживает цикл в связном списке без дополнительного хранилища.

• Один указатель продвигается на один узел за шаг, а второй на два.
• При наличии цикла быстрый указатель догонит медленный, а достижение null означает отсутствие цикла.
• Алгоритм работает за O(n) времени и O(1) памяти, тогда как множество посещённых узлов потребовало бы O(n) памяти.

Стек естественно подходит для отмены, потому что последнее действие нужно обратить первым.

• Каждое действие кладёт предыдущее состояние или обратную команду на стек отмены.
• Операция отмены извлекает и применяет верхнюю запись в порядке LIFO.
• Второй стек поддерживает повтор, сохраняя отменённые действия до их нового применения.

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

• Заполненный массив обычно удваивает ёмкость и копирует все n элементов за O(n).
• Экспоненциальный рост оставляет много дешёвых добавлений за O(1) между расширениями.
• Распределение общей стоимости копирования между всеми добавлениями даёт постоянную среднюю цену операции.

Множество представляет собой неупорядоченную коллекцию уникальных элементов с быстрой проверкой принадлежности.

• Множество на основе хеш-таблицы обычно проверяет наличие за O(1), тогда как списку нужен проход за O(n).
• Множество лучше списка, когда требуется удалить дубликаты или многократно проверять наличие значения.
• Типичные примеры включают удаление повторных ID пользователей и учёт посещённых значений при обходе графа.

Повторное склеивание строк часто медленно, поскольку неизменяемая строка при каждом добавлении копируется в новое значение.

• В Java и Python такое построение растущей строки в цикле может суммарно стоить O(n^2).
• Изменяемый буфер вроде StringBuilder в Java или список с последующим str.join в Python дёшево накапливает части.
• Однократное создание итоговой строки в конце снижает общую стоимость до O(n).

Куча является очередью с приоритетом, которая держит наименьший или наибольший элемент в корне.

• Она даёт доступ к крайнему элементу за O(1), а вставку и удаление за O(log n).
• Она эффективно возвращает следующий по приоритету элемент без полной сортировки всех данных.
• Кучу применяют для планирования задач, слияния отсортированных потоков и выбора ближайшего непосещённого узла в алгоритме Дейкстры.