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

Часть 1: Строки, Простые списки, Числа, Матрицы

1. Строки: Проверка на палиндром

Задача: Определить, является ли строка палиндромом (читается одинаково слева направо и справа налево). Игнорируем регистр и пробелы.

Принцип решения: Сравниваем строку с её перевёрнутой версией. Для этого очищаем строку от лишних символов и приводим к одному регистру.

def is_palindrome(s: str) -> bool:
    """
    Проверяет, является ли строка палиндромом.
    """
    # 1. Очищаем строку: убираем пробелы и приводим к нижнему регистру
    cleaned_str = ''.join(ch.lower() for ch in s if ch.isalnum())

    # 2. Сравниваем очищенную строку с её перевёрнутой версией
    return cleaned_str == cleaned_str[::-1]  # [::-1] — это срез для разворота строки


# Примеры использования
print(is_palindrome("А роза упала на лапу Азора"))  # True
print(is_palindrome("Hello"))                      # False
print(is_palindrome("racecar"))                    # True

2. Простые списки (массивы): Поиск второго максимального элемента

Задача: Найти второй по величине элемент в списке чисел. Список содержит не менее двух уникальных элементов.

Принцип решения: Проходим по списку один раз, отслеживая наибольший (max1) и второй наибольший (max2) элементы.

def second_max(arr: list) -> int:
    """
    Находит второй максимальный элемент в списке.
    """
    # Инициализируем два наименьших возможных значения
    max1 = max2 = float('-inf')  # -бесконечность

    for num in arr:
        if num > max1:
            # Нашли новый максимум, старый максимум становится вторым
            max2 = max1
            max1 = num
        elif num > max2 and num != max1:
            # Число меньше максимума, но больше текущего второго максимума
            max2 = num

    return max2


# Пример использования
numbers = [3, 5, 1, 7, 2, 7, 4]
print(second_max(numbers))  # Вывод: 5 (второй максимум после 7)

3. Числа: Проверка числа на простоту

Задача: Определить, является ли натуральное число простым (делится только на 1 и на себя).

Принцип решения: Проверяем делители числа от 2 до квадратного корня из числа. Если хотя бы один делитель найден — число составное.

import math

def is_prime(n: int) -> bool:
    """
    Проверяет, является ли число простым.
    """
    if n < 2:
        return False
    if n == 2:  # 2 — единственное чётное простое число
        return True
    if n % 2 == 0:  # Отсекаем все остальные чётные числа
        return False

    # Проверяем нечётные делители от 3 до корня из n
    limit = int(math.isqrt(n))  # Квадратный корень, округлённый вниз
    for i in range(3, limit + 1, 2):  # Шаг 2 — только нечётные
        if n % i == 0:
            return False
    return True


# Примеры использования
print(is_prime(17))   # True
print(is_prime(100))  # False
print(is_prime(2))    # True

4. Матрицы: Поворот матрицы на 90 градусов

Задача: Повернуть квадратную матрицу (список списков) на 90 градусов по часовой стрелке.

Принцип решения: Создаём новую матрицу, где элементы из исходной матрицы переставляются по правилу: new_matrix[i][j] = old_matrix[n-1-j][i].

def rotate_matrix(matrix: list[list]) -> list[list]:
    """
    Поворачивает квадратную матрицу на 90 градусов по часовой стрелке.
    """
    n = len(matrix)  # Размер квадратной матрицы (n x n)
    
    # Создаём новую матрицу такого же размера, заполненную нулями
    rotated = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            # Ключевая формула поворота:
            # Элемент в строке i, столбце j новой матрицы берётся
            # из строки n-1-j, столбца i исходной матрицы
            rotated[i][j] = matrix[n - 1 - j][i]
    
    return rotated


# Пример использования
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print("Исходная матрица:")
for row in matrix:
    print(row)

print("\nПовёрнутая матрица:")
for row in rotate_matrix(matrix):
    print(row)
# Вывод:
# [7, 4, 1]
# [8, 5, 2]
# [9, 6, 3]

Часть 2: Связанные списки, Деревья, Кучи (очереди с приоритетом)

5. Связанные списки: Разворот односвязного списка

Задача: Развернуть односвязный список (изменить направление ссылок на противоположное).

Принцип решения: Итеративно проходим по списку, меняя направление ссылок. Нужно хранить три указателя: на предыдущий, текущий и следующий узлы.

class ListNode:
    """Узел односвязного списка."""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_list(head: ListNode) -> ListNode:
    """
    Разворачивает односвязный список и возвращает новую голову.
    """
    prev = None  # Предыдущий узел, изначально None
    current = head  # Текущий узел

    while current:
        # Сохраняем следующий узел, чтобы не потерять
        next_node = current.next
        
        # Меняем направление ссылки: текущий узел теперь указывает на предыдущий
        current.next = prev
        
        # Сдвигаем указатели: предыдущий становится текущим,
        # текущий становится следующим
        prev = current
        current = next_node
    
    # В конце prev указывает на новую голову (бывший хвост)
    return prev


# Вспомогательная функция для создания и печати списка
def create_list(values):
    """Создаёт связанный список из списка значений."""
    dummy = ListNode()
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

def print_list(head):
    """Печатает значения связанного списка."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    print(" -> ".join(map(str, result)))


# Пример использования
original = create_list([1, 2, 3, 4, 5])
print("Исходный список:")
print_list(original)

reversed_head = reverse_list(original)
print("\nРазвёрнутый список:")
print_list(reversed_head)  # 5 -> 4 -> 3 -> 2 -> 1

6. Деревья: Поиск в глубину (DFS) в бинарном дереве

Задача: Обойти все узлы бинарного дерева в порядке "корень-левый-правый" (pre-order traversal).

Принцип решения: Рекурсивно посещаем корень, затем левое поддерево, затем правое поддерево.

class TreeNode:
    """Узел бинарного дерева."""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def dfs_preorder(root: TreeNode) -> list:
    """
    Возвращает значения узлов в порядке pre-order (корень-левый-правый).
    """
    result = []
    
    def traverse(node):
        if not node:
            return
        # 1. Посещаем корень (добавляем значение)
        result.append(node.val)
        # 2. Рекурсивно обходим левое поддерево
        traverse(node.left)
        # 3. Рекурсивно обходим правое поддерево
        traverse(node.right)
    
    traverse(root)
    return result


# Создаём бинарное дерево:
#       1
#      / \
#     2   3
#    / \
#   4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Pre-order обход (DFS):")
print(dfs_preorder(root))  # [1, 2, 4, 5, 3]

7. Кучи: Реализация минимальной кучи (Min-Heap)

Задача: Реализовать минимальную кучу (min-heap) с основными операциями: добавление элемента и извлечение минимума.

Принцип решения: Используем список для хранения элементов. Поддерживаем свойство кучи: родитель всегда меньше своих потомков.

class MinHeap:
    """
    Реализация минимальной кучи (min-heap).
    """
    def __init__(self):
        self.heap = []
    
    def parent_index(self, i):
        """Индекс родителя узла i."""
        return (i - 1) // 2
    
    def left_child_index(self, i):
        """Индекс левого потомка узла i."""
        return 2 * i + 1
    
    def right_child_index(self, i):
        """Индекс правого потомка узла i."""
        return 2 * i + 2
    
    def insert(self, value):
        """Добавляет элемент в кучу."""
        # 1. Добавляем элемент в конец списка
        self.heap.append(value)
        # 2. Восстанавливаем свойство кучи, "поднимая" элемент
        self._sift_up(len(self.heap) - 1)
    
    def _sift_up(self, i):
        """Поднимает элемент на правильную позицию."""
        while i > 0 and self.heap[i] < self.heap[self.parent_index(i)]:
            # Меняем местами с родителем, если родитель больше
            parent_idx = self.parent_index(i)
            self.heap[i], self.heap[parent_idx] = self.heap[parent_idx], self.heap[i]
            i = parent_idx
    
    def extract_min(self):
        """Извлекает и возвращает минимальный элемент (корень кучи)."""
        if not self.heap:
            return None
        
        # 1. Сохраняем минимум (это корень)
        min_val = self.heap[0]
        
        # 2. Перемещаем последний элемент в корень
        last_val = self.heap.pop()
        if self.heap:  # Если куча не пуста после извлечения
            self.heap[0] = last_val
            # 3. Восстанавливаем свойство кучи, "опуская" корень
            self._sift_down(0)
        
        return min_val
    
    def _sift_down(self, i):
        """Опускает элемент на правильную позицию."""
        size = len(self.heap)
        while True:
            left = self.left_child_index(i)
            right = self.right_child_index(i)
            smallest = i
            
            # Ищем наименьший среди текущего узла и его потомков
            if left < size and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < size and self.heap[right] < self.heap[smallest]:
                smallest = right
            
            # Если текущий узел уже наименьший — свойство кучи восстановлено
            if smallest == i:
                break
            
            # Меняем местами с наименьшим потомком
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest  # Продолжаем проверку с новой позиции


# Пример использования
heap = MinHeap()
heap.insert(5)
heap.insert(3)
heap.insert(8)
heap.insert(1)
heap.insert(2)

print("Извлечение элементов из min-heap в порядке возрастания:")
for _ in range(5):
    print(heap.extract_min(), end=" ")  # 1 2 3 5 8
print()

8. Графы: Поиск в ширину (BFS) — простейший вариант

Задача: Обойти все узлы невзвешенного графа, начиная с заданной вершины, в порядке увеличения расстояния от неё.

Принцип решения: Используем очередь. Посещаем вершину, добавляем всех её непосещённых соседей в очередь.

from collections import deque

def bfs(graph, start):
    """
    Поиск в ширину (BFS) по графу, представленному списками смежности.
    Возвращает вершины в порядке их посещения.
    """
    visited = set()      # Множество посещённых вершин
    queue = deque([start])  # Очередь для BFS
    result = []          # Результат обхода
    
    visited.add(start)
    
    while queue:
        # Извлекаем вершину из начала очереди
        vertex = queue.popleft()
        result.append(vertex)
        
        # Добавляем всех непосещённых соседей в конец очереди
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result


# Граф представлен списками смежности
# Индексы: 0:A, 1:B, 2:C, 3:D, 4:E
graph = {
    0: [1, 2],    # A соединена с B и C
    1: [0, 3, 4], # B соединена с A, D и E
    2: [0, 4],    # C соединена с A и E
    3: [1],       # D соединена с B
    4: [1, 2]     # E соединена с B и C
}

print("BFS обход графа, начиная с вершины 0:")
print(bfs(graph, 0))  # [0, 1, 2, 3, 4] или [0, 2, 1, 4, 3] — зависит от порядка соседей

Ключевые выводы:

1. Строки: Используйте срезы [::-1] для разворота
2. Списки: Часто достаточно одного прохода с несколькими переменными
3. Числа: Для простоты проверяйте делители до корня
4. Матрицы: Формула [n-1-j][i] для поворота на 90°
5. Списки: Три указателя — ключ к развороту связного списка
6. Деревья: Рекурсия — естественный способ обхода
7. Кучи: Поддержание свойства кучи через "подъем" и "спуск"
8. Графы: Очередь обеспечивает обход по уровням

Эти задачи охватывают фундаментальные алгоритмические концепции и часто встречаются на собеседованиях. Их понимание даст прочную основу для решения более сложных задач.