Раздел 1: Основы и сложность (Basics & Complexity)
1. Вопрос: Что такое алгоритм?
Ответ: Алгоритм — это конечная последовательность точных инструкций, предназначенная для решения определенной задачи или класса задач. Он должен быть однозначным, конечным и эффективным.
2. Вопрос: Что такое «О-большое» (Big O notation)?
Ответ: Это математическая нотация, используемая для описания асимптотической верхней границы времени выполнения или потребляемой памяти алгоритма. Она показывает, как растет время работы алгоритма относительно увеличения размера входных данных (n), игнорируя константы и младшие члены (например, O(n), O(log n), O(n²)).
3. Вопрос: В чем разница между временной сложностью O(log n) и O(n)?
Ответ: O(log n) означает логарифмическую сложность. На каждой итерации объем работы сокращается вдвое (как в бинарном поиске). O(n) — линейная сложность, где время выполнения пропорционально количеству элементов. O(log n) значительно быстрее для больших n.
4. Вопрос: Что такое «жадный алгоритм» (Greedy algorithm)?
Ответ: Это алгоритм, который принимает локально оптимальное решение на каждом этапе, надеясь, что итоговое решение будет глобально оптимальным. Он не пересматривает принятые решения. Примеры: алгоритм Дейкстры, задача о размене монет (в некоторых валютах).
Раздел 2: Сортировка и Поиск (Sorting & Searching)
5. Вопрос: Назовите разницу между алгоритмами Быстрая сортировка (QuickSort) и Сортировка слиянием (MergeSort).
Ответ:
- QuickSort: Работает в среднем за O(n log n), в худшем случае O(n²). Не требует дополнительной памяти (in-place). Нестабильная (зависит от реализации).
- MergeSort: Всегда работает за O(n log n). Требует O(n) дополнительной памяти. Стабильная. Гарантированная производительность.
6. Вопрос: Как работает бинарный поиск (Binary Search) и какие требования предъявляются к данным?
Ответ: Бинарный поиск работает путем многократного деления отсортированного массива пополам и сравнения искомого значения со средним элементом. Требование: массив должен быть отсортирован. Временная сложность: O(log n).
7. Вопрос: Почему Timsort считается хорошим алгоритмом сортировки в реальных задачах?
Ответ: Timsort — гибридный алгоритм (сортировка слиянием + вставками). Он оптимизирован для реальных данных, которые часто содержат уже упорядоченные подпоследовательности (runs). Он используется в Python, Java и имеет сложность O(n) для частично отсортированных массивов.
Раздел 3: Структуры данных (Data Structures)
8. Вопрос: В чем разница между стеком (Stack) и очередью (Queue)?
Ответ:
- Стек: LIFO (Last In, First Out — «последним пришел, первым ушел»). Пример: стопка тарелок.
- Очередь: FIFO (First In, First Out — «первым пришел, первым ушел»). Пример: живая очередь в магазине.
9. Вопрос: Что такое хеш-таблица (Hash Table) и как решаются коллизии?
Ответ: Хеш-таблица — структура данных, которая сопоставляет ключи значениям, используя хеш-функцию. Коллизии (когда двум ключам присвоен один хэш) решаются методами:
- Цепочки (Chaining): В ячейке хранится связный список.
- Открытая адресация (Open Addressing): Поиск другой свободной ячейки.
10. Вопрос: Что такое бинарное дерево поиска (BST)?
Ответ: Это древовидная структура данных, где у каждого узла не более двух детей. При этом значение левого потомка всегда меньше значения родителя, а правого — больше. Это позволяет быстро искать элементы.
11. Вопрос: В чем преимущество кучи (Heap) над отсортированным массивом?
Ответ: В куче (особенно в двоичной) операция вставки элемента и удаления максимума/минимума выполняется за O(log n), в то время как в отсортированном массиве вставка в середину требует O(n) сдвигов.
Раздел 4: Графы (Graphs)
12. Вопрос: В чем разница между BFS (обход в ширину) и DFS (обход в глубину)?
Ответ:
- BFS: Использует очередь. Ищет слой за слоем. Гарантирует кратчайший путь в невзвешенном графе.
- DFS: Использует стек (рекурсию). Идет до конца ветки, затем возвращается. Использует меньше памяти, если граф глубок, но не гарантирует кратчайший путь.
13. Вопрос: Для чего используется алгоритм Дейкстры?
Ответ: Для нахождения кратчайших путей от одной вершины до всех остальных во взвешенном графе с неотрицательными весами ребер. Сложность: O((V+E) log V) с использованием приоритетной очереди.
14. Вопрос: Когда нужно использовать алгоритм Флойда-Уоршелла, а не Дейкстру?
Ответ: Алгоритм Флойда-Уоршелла используется, когда нужно найти кратчайшие пути между всеми парами вершин. Он также работает с отрицательными весами (но без отрицательных циклов).
15. Вопрос: Что такое топологическая сортировка?
Ответ: Это упорядочивание вершин ориентированного графа без циклов (DAG) в такой последовательности, что для каждого направленного ребра (u -> v) вершина u находится перед v. Применяется для планирования задач (сборка проекта, учебный план).
Раздел 5: Динамическое программирование и рекурсия (DP & Recursion)
16. Вопрос: В чем суть динамического программирования (DP)?
Ответ: Это метод оптимизации, который разбивает сложную задачу на более простые подзадачи, решает каждую подзадачу один раз и сохраняет результат в таблице (мемоизация), чтобы избежать повторных вычислений.
17. Вопрос: В чем разница между нисходящим (top-down) и восходящим (bottom-up) DP?
Ответ:
- Top-down: Начинаем с большой задачи, рекурсивно спускаемся вниз, кешируем результаты. Проще писать.
- Bottom-up: Начинаем с решения самых маленьких подзадач и идем вверх, заполняя таблицу. Обычно быстрее и не использует рекурсию (нет риска переполнения стека).
18. Вопрос: Приведите классический пример задачи на рекурсию.
Ответ: Вычисление чисел Фибоначчи или вычисление факториала. Также классикой является задача «Ханойская башня».
Раздел 6: Конкретные алгоритмы и техники
19. Вопрос: Как работает алгоритм поиска в ширину (BFS) для поиска выхода из лабиринта?
Ответ: Мы ставим в очередь стартовую клетку. Пока очередь не пуста, извлекаем клетку и смотрим на ее 4 соседей. Если сосед — выход, мы нашли путь. Если сосед — проход и мы там еще не были, помечаем его посещенным и добавляем в очередь. BFS гарантирует, что первый найденный выход будет достигнут за минимальное количество шагов.
20. Вопрос: Что такое алгоритм «Разделяй и властвуй» (Divide and Conquer)?
Ответ: Парадигма, при которой задача рекурсивно разбивается на несколько подзадач того же типа, результаты которых затем объединяются. Примеры: Merge Sort, Quick Sort, бинарный поиск (хотя его часто считают «уменьшай и властвуй»).
21. Вопрос: Для чего используется алгоритм Кнута-Морриса-Пратта (КМП)?
Ответ: Для поиска подстроки в строке. Его преимущество в том, что он не требует отката во входной строке при несовпадении благодаря использованию префикс-функции. Сложность: O(n+m), где n — длина текста, m — длина паттерна.
22. Вопрос: В чем суть кэширования (Caching) и алгоритма LRU?
Ответ: Кэширование хранит часто используемые данные в быстрой памяти. LRU (Least Recently Used) — это политика вытеснения, которая удаляет элемент, к которому дольше всего не обращались. Реализуется через HashMap + двусвязный список (или OrderedDict в Python) для операций O(1).
Раздел 7: Анализ и практика
23. Вопрос: Что означает термин «инвариант цикла»?
Ответ: Это логическое утверждение (условие), которое остается истинным перед каждой итерацией цикла. Оно используется для доказательства корректности алгоритма. Пример: в пузырьковой сортировке после i итераций последние i элементов находятся на своих местах.
24. Вопрос: Почему для некоторых задач (например, раскрой графа) невозможно применить точный алгоритм для больших данных?
Ответ: Потому что эти задачи являются NP-полными. Для них неизвестен (и скорее всего не существует) алгоритм, решающий задачу за полиномиальное время. Для больших n время выполнения точного решения (например, полный перебор) становится астрономическим, поэтому используют эвристики или приближенные алгоритмы.
25. Вопрос: Как выбрать между использованием ArrayList (динамический массив) и LinkedList (связный список)?
Ответ:
- ArrayList: Используем, если нужно часто обращаться к элементам по индексу (O(1)). Добавление в конец амортизировано быстро, но вставка/удаление в середине — медленно (O(n)).
- LinkedList: Используем, если часто добавляем/удаляем элементы в начале или середине списка, но редко обращаемся по индексу (доступ по индексу — O(n)).
Страховка на собеседовании
Знание есть, но стресс мешает?
Бесплатное сообщество для прокачки карьеры в IT
Подпишись на https://t.me/IT_Interview_Partner_Bot
Подпишись на https://t.me/LyakhovEugene