← Назад к курсу
Общее описание 30 типовых алгоритмических задач для собеседований на Python
В этом уроке содержится общее описание 30 типовых алгоритмических задач для собеседований на Python. Чтобы было проще ориентироваться, задачи сгруппированы по основным техникам и структурам данных, которые для них используются.
📌 1. Массивы и строки
Эти задачи проверяют базовые навыки работы с линейными структурами и часто решаются с помощью известных шаблонов.
| Техника / Паттерн | Название задачи | Словесное описание решения |
|---|---|---|
| Two Pointers (Два указателя) |
Слияние двух отсортированных массивов | Создайте третий массив. Двигайтесь двумя указателями по началам исходных массивов, сравнивайте текущие элементы и всегда добавляйте в результат меньший из них, сдвигая соответствующий указатель. |
| Проверка, является ли строка/число палиндромом | Поставьте один указатель в начало строки, другой — в конец. Двигайтесь к центру, сравнивая символы. Если все пары совпали — это палиндром. | |
| Sliding Window (Скользящее окно) |
Поиск минимальной подстроки, содержащей все нужные символы | Используйте два указателя как границы окна. Расширяйте правую границу, пока в окне не окажутся все искомые символы. Затем сужайте левую, пока это условие выполняется, и так двигайтесь по всей строке. |
| Максимальная сумма подмассива фиксированной длины k | Найдите сумму первых k элементов. Затем двигайте окно на один элемент вправо, вычитая уходящий элемент и добавляя новый, отслеживая максимальную сумму. | |
| Поиск в отсортированном массиве | Бинарный поиск | Убедитесь, что массив отсортирован. Сравните искомый элемент со средним элементом массива. Если элемент больше — ищите в правой половине, если меньше — в левой. Повторяйте, пока не найдете элемент или границы не схлопнутся. |
| Поиск поворотной точки (pivot) в сдвинутом отсортированном массиве | Используйте модифицированный бинарный поиск. Сравнивайте средний элемент с крайними, чтобы определить, в какой половине порядок нарушен, и продолжайте поиск в ней. | |
| Вращение и перестановки | Развернуть число | Преобразуйте число в строку и используйте срез с шагом -1 ([::-1]) для разворота. |
| Изменить порядок слов в строке на обратный | Разделите строку на слова, уберите лишние пробелы, затем разверните порядок слов с помощью срезов или итерации с конца. |
📌 2. Хеш-таблицы (словари и множества)
Эти структуры данных позволяют оптимизировать поиск до O(1) и часто используются для подсчета или проверки наличия элементов.
| Название задачи | Словесное описание решения |
|---|---|
| Найти два числа в массиве, дающих в сумме заданное значение | Пройдитесь по массиву. Для каждого элемента вычисляйте, какое второе число нужно для получения суммы. Проверяйте, встречалось ли уже это второе число, используя множество (set). |
| Проверка, является ли строка анаграммой другой | Посчитайте частоту появления каждого символа в первой строке, используя словарь (или collections.Counter). Пройдитесь по второй строке, уменьшая счетчики. Если в конце все счетчики равны нулю — это анаграмма. |
| Поиск первого неповторяющегося символа в строке | Создайте словарь для подсчета частот всех символов в строке. Затем пройдитесь по строке второй раз и найдите первый символ с частотой 1. |
| Определить, содержит ли массив дубликаты | Добавляйте элементы во множество (set) по мере итерации. Если элемент уже есть в множестве — дубликат найден. |
📌 3. Связанные списки
Задачи на списки проверяют понимание структур данных с последовательным доступом и умение манипулировать указателями.
| Название задачи | Словесное описание решения |
|---|---|
| Развернуть односвязный список | Итерируйтесь по списку, меняя у каждого узла направление ссылки next. Для этого вам понадобятся три указателя: на текущий, предыдущий и следующий узлы. |
| Обнаружение цикла в списке (Floyd's Algorithm) |
Используйте два указателя («черепаху» и «зайца»), движущихся с разной скоростью. Если в списке есть цикл, они обязательно встретятся. |
| Найти узел пересечения двух списков | Вычислите длины обоих списков. Выровняйте начальные позиции, сдвинув указатель на более длинном списке. Затем двигайте оба указателя одновременно, пока они не встретятся в одном узле. |
| Объединить два отсортированных связанных списка | Создайте фиктивный головной узел. Сравнивайте текущие узлы двух списков, прикрепляя к результату меньший и сдвигая соответствующий указатель, пока один из списков не закончится. |
📌 4. Деревья
Задачи на деревья проверяют знание рекурсии и алгоритмов обхода.
| Тип обхода | Название задачи | Словесное описание решения |
|---|---|---|
| Обход в глубину (DFS) | Проверить, является ли двоичное дерево сбалансированным | Рекурсивно проверяйте высоту левого и правого поддеревьев для каждого узла. Если разница высот больше 1, дерево не сбалансировано. |
| Найти максимальную/минимальную глубину дерева | Если узел пустой (None), его глубина равна 0. Иначе глубина равна 1 + максимум из глубин левого и правого поддеревьев. | |
| Найти наименьшего общего предка (LCA) двух узлов | Рекурсивно ищите оба узла в дереве. Узел, в левом и правом поддеревьях которого найдены искомые узлы, и будет их LCA. | |
| Обход в ширину (BFS) | Обход дерева по уровням | Используйте очередь (queue). Начиная с корня, обрабатывайте узел, добавляйте в результат его значение, а затем ставьте в очередь его левого и правого потомка. |
| Найти правый вид двоичного дерева | Модифицируйте BFS. На каждом уровне дерева берите последний элемент в очереди — это и будет крайний правый узел для этого уровня. |
📌 5. Рекурсия и динамическое программирование (DP)
DP помогает решать сложные задачи путем разбиения на более простые подзадачи и запоминания их результатов.
| Название задачи | Словесное описание решения |
|---|---|
| Вычисление n-го числа Фибоначчи | Базовые случаи: F(0)=0, F(1)=1. Для n > 1: F(n) = F(n-1) + F(n-2). Для эффективности используйте мемоизацию (кэширование результатов). |
| Задача о рюкзаке (0/1 Knapsack) | Для каждого предмета решите: брать его или нет. Создайте таблицу DP, где строка — предмет, а столбец — возможный вес. Значение в ячейке — максимальная стоимость для данного веса с учетом текущих предметов. |
| Наибольшая возрастающая подпоследовательность (LIS) | Поддерживайте массив, где на i-й позиции хранится наименьший возможный последний элемент возрастающей подпоследовательности длины i+1. Для каждого нового числа найдите его место в этом массиве бинарным поиском. |
| Подсчет уникальных путей в сетке (Robot Paths) | Создайте 2D-таблицу DP. Количество путей до клетки (i, j) равно сумме путей до клетки сверху (i-1, j) и слева (i, j-1). |
📌 6. Прочие ключевые алгоритмы и задачи
| Категория | Название задачи | Словесное описание решения |
|---|---|---|
| Сортировка и поиск | Реализовать быструю сортировку (quicksort) | Выберите опорный элемент (pivot). Перераспределите массив так, чтобы элементы меньше опорного оказались слева, а больше — справа. Рекурсивно примените алгоритм к левой и правой частям. |
| Найти k-й по величине элемент в массиве | Используйте модификацию алгоритма быстрой сортировки (quickselect). После разделения массива опорным элементом рекурсивно ищите элемент только в той части, где он должен находиться. | |
| Математические и логические | Проверка на простое число | Число простое, если оно больше 1 и не делится без остатка ни на одно число от 2 до квадратного корня из этого числа. |
| Разложение числа на простые множители | Делите заданное число на наименьший возможный простой делитель (начиная с 2), пока число не станет равным 1. Все делители и будут простыми множителями. | |
| Графы | Поиск в глубину (DFS) для графа | Начните с заданной вершины, отметьте ее как посещенную. Рекурсивно посетите все смежные с ней еще не посещенные вершины. |
| Поиск в ширину (BFS) для графа | Используйте очередь. Начните с заданной вершины, отметьте ее. Пока очередь не пуста, извлекайте вершину, обрабатывайте и добавляйте в очередь всех ее непосещенных соседей. | |
| Продвинутые строки | Поиск самого длинного палиндрома в строке (Алгоритм Манакера) |
Алгоритм использует симметрию палиндромов. Он обрабатывает строку, рассматривая каждый символ как центр потенциального палиндрома и эффективно использует уже вычисленную информацию для нахождения границ. |
| Жадные алгоритмы | Задача о покрытии точек отрезками (антенны) | Отсортируйте точки. Установите первую антенну так, чтобы покрыть как можно больше точек справа. Повторяйте процесс для оставшихся непокрытых точек. |
💡 Как эффективно готовиться
- Начинайте с основ: освойте массивы, строки, хеш-таблицы, прежде чем переходить к деревьям и графам.
- Учите шаблоны: такие как два указателя, скользящее окно, BFS/DFS. Найдите задачи по этим тегам на LeetCode и решайте их группами.
- Практикуйтесь системно: используйте готовые планы, например, LeetCode Top 100 Liked или Top Interview 150.
- Анализируйте неудачи: если не можете решить задачу за 30-40 минут, изучите готовое решение, а через время попробуйте решить ее снова.
Этот список покрывает большинство тем, с которыми вы можете столкнуться. Удачи в подготовке