📊 Big O Notation (Оценка сложности алгоритмов)

Основные временные сложности:

• O(1) - Константное время (доступ по индексу в массиве, push/pop в стеке)
• O(log n) - Логарифмическое время (бинарный поиск)
• O(n) - Линейное время (линейный поиск, обход массива)
• O(n log n) - Линейно-логарифмическое время (быстрая сортировка, сортировка слиянием)
• O(n²) - Квадратичное время (пузырьковая сортировка, вложенные циклы)
• O(2ⁿ) - Экспоненциальное время (рекурсивный Фибоначчи)
• O(n!) - Факториальное время (задача коммивояжера)

🏗️ Структуры данных в Python

Список (List) - Сложность операций:

• Доступ по индексу: O(1)
• Поиск элемента: O(n)
• Добавление в конец: O(1)
• Вставка в начало/середину: O(n)

lst = [1, 2, 3]
lst.append(4)        # O(1) - добавление в конец
lst.pop()            # O(1) - удаление с конца
lst.insert(0, 0)     # O(n) - вставка в начало
3 in lst             # O(n) - проверка наличия

Словарь (Dict) - Сложность операций:

• Добавление/поиск/удаление: O(1) в среднем случае
• Копирование: O(n)

d = {'a': 1, 'b': 2, 'c': 3}
d['d'] = 4           # O(1) - добавление
value = d.get('a')   # O(1) - получение
del d['b']           # O(1) - удаление
'a' in d             # O(1) - проверка наличия ключа

Множество (Set) - Сложность операций:

• Добавление/удаление/проверка наличия: O(1)

🔄 Алгоритмы сортировки

Быстрая сортировка (QuickSort)

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Сортировка слиянием (MergeSort)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

🔍 Алгоритмы поиска

Бинарный поиск (требует отсортированный массив)

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Поиск в глубину (DFS)

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Поиск в ширину (BFS)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            for neighbor in graph.get(vertex, []):
                if neighbor not in visited:
                    queue.append(neighbor)

🎯 Популярные задачи на собеседованиях

1. Two Sum (LeetCode #1)

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

2. Проверка на палиндром

def is_palindrome(s):
    s = ''.join(c.lower() for c in s if c.isalnum())
    return s == s[::-1]

3. Реверс связного списка

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

💡 Советы для успешного собеседования

1. Говорите вслух - объясняйте ход своих мыслей интервьюеру
2. Уточняйте условия задачи - задавайте вопросы о входных данных и ограничениях
3. Рассматривайте краевые случаи - пустые массивы, один элемент, большие числа
4. Начинайте с простого решения - затем оптимизируйте его
5. Анализируйте сложность - оценивайте временную и пространственную сложность
6. Тестируйте на примерах - проверяйте решение на простых и сложных случаях
7. Знайте стандартные алгоритмы - сортировка, поиск, обходы графов
8. Практикуйтесь регулярно - используйте LeetCode, HackerRank, Codewars

🔗 Полезные ресурсы для подготовки:

• LeetCode (leetcode.com) - задачи по алгоритмам с решениями
• HackerRank (hackerrank.com) - практика программирования
• GeeksforGeeks (geeksforgeeks.org) - статьи и объяснения алгоритмов
• NeetCode (neetcode.io) - структурированные курсы подготовки
• Python документация (docs.python.org) - официальная документация

🎯 Задача 1: Two Sum (LeetCode #1)

📋 Описание задачи:

💡 Подход к решению:

⚡ Сложность алгоритма:

• Временная сложность: O(n) - один проход по массиву
• Пространственная сложность: O(n) - в худшем случае храним все элементы

📝 Пример кода:

def two_sum(nums, target):
    seen = {}  # Словарь для хранения чисел и их индексов
    for i, num in enumerate(nums):
        complement = target - num  # Число, которое нужно найти
        # Если complement уже есть в словаре, решение найдено
        if complement in seen:
            return [seen[complement], i]
        # Добавляем текущее число в словарь
        seen[num] = i
    return []  # Если решение не найдено

🚨 Краевые случаи:

1. Пустой массив - возвращаем пустой список
2. Один элемент - решение невозможно
3. Отрицательные числа - алгоритм работает корректно
4. Повторяющиеся числа - важно учитывать индексы
5. Нет решения - возвращаем пустой список

✅ Примеры использования:

# Пример 1: Основной случай
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
# Пример 2: С отрицательными числами
print(two_sum([-3, 4, 3, 90], 0))  # [0, 2]
# Пример 3: Один элемент
print(two_sum([5], 10))  # []
# Пример 4: Пустой массив
print(two_sum([], 10))   # []

🎯 Задача 2: Проверка строки на палиндром

📋 Описание задачи:

💡 Подход к решению:

⚡ Сложность алгоритма:

• Временная сложность: O(n) - один проход по строке для очистки + O(n) для сравнения
• Пространственная сложность: O(n) - создание новой очищенной строки

📝 Пример кода (метод с реверсом):

def is_palindrome(s):
    # Очищаем строку: оставляем только буквенно-цифровые символы, приводим к нижнему регистру
    cleaned = ''.join(char.lower() for char in s if char.isalnum())
    # Сравниваем с обратной версией
    return cleaned == cleaned[::-1]

📝 Пример кода (метод с двумя указателями):

def is_palindrome_two_pointers(s):
    # Очищаем строку
    cleaned = ''.join(char.lower() for char in s if char.isalnum())
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True

🚨 Краевые случаи:

1. Пустая строка - считается палиндромом (пустая строка == обратная пустая строка)
2. Один символ - всегда палиндром
3. Строка только с пробелами и знаками препинания - считается пустой строкой
4. Смешанный регистр - нужно приводить к одному регистру
5. Небуквенно-цифровые символы - должны игнорироваться

🎯 Задача 3: Реверс односвязного списка

📋 Описание задачи:

💡 Подход к решению:

⚡ Сложность алгоритма:

• Временная сложность: O(n) - один проход по всем узлам списка
• Пространственная сложность: O(1) - только несколько указателей

📝 Пример кода:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        # Сохраняем следующий узел
        next_node = current.next
        # Меняем направление ссылки
        current.next = prev
        # Перемещаем указатели
        prev = current
        current = next_node
    # prev теперь указывает на новую голову
    return prev

📝 Рекурсивная реализация:

def reverse_linked_list_recursive(head):
    if not head or not head.next:
        return head
    # Рекурсивно реверсируем остаток списка
    new_head = reverse_linked_list_recursive(head.next)
    # Меняем ссылки
    head.next.next = head
    head.next = None
    return new_head

🚨 Краевые случаи:

1. Пустой список (head = None) - возвращаем None
2. Список из одного элемента - возвращаем тот же элемент
3. Большой список - итеративный метод предпочтительнее из-за глубины рекурсии
4. Список с циклами - алгоритм не должен создавать бесконечный цикл

🎯 Задача 4: Быстрая сортировка (QuickSort)

📋 Описание задачи:

💡 Подход к решению:

1. Выбрать опорный элемент (pivot) из массива
2. Разбить массив на три части:
   • Элементы меньше опорного
   • Элементы равные опорному
   • Элементы больше опорного
3. Рекурсивно применить QuickSort к левой и правой частям
4. Объединить отсортированные части

⚡ Сложность алгоритма:

• Лучший случай: O(n log n) - когда pivot делит массив примерно пополам
• Средний случай: O(n log n)
• Худший случай: O(n²) - когда pivot всегда минимальный или максимальный элемент
• Пространственная сложность: O(log n) - глубина рекурсии

📝 Пример кода (рекурсивная реализация):

def quicksort(arr):
    """Рекурсивная реализация быстрой сортировки"""
    # Базовый случай: массивы длиной 0 или 1 уже отсортированы
    if len(arr) <= 1:
        return arr
    # Выбираем опорный элемент (середина массива)
    pivot = arr[len(arr) // 2]
    # Разделяем массив на три части
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    # Рекурсивно сортируем левую и правую части
    return quicksort(left) + middle + quicksort(right)

📝 Пример кода (in-place реализация):

def quicksort_inplace(arr, low=0, high=None):
    """In-place реализация быстрой сортировки"""
    if high is None:
        high = len(arr) - 1
    if low < high:
        # Находим индекс разделения
        pivot_index = partition(arr, low, high)
        # Рекурсивно сортируем элементы до и после разделения
        quicksort_inplace(arr, low, pivot_index - 1)
        quicksort_inplace(arr, pivot_index + 1, high)
    return arr

def partition(arr, low, high):
    """Разделение массива относительно опорного элемента"""
    # Выбираем последний элемент как опорный
    pivot = arr[high]
    i = low - 1  # Индекс меньшего элемента
    for j in range(low, high):
        # Если текущий элемент меньше или равен опорному
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    # Помещаем опорный элемент на правильную позицию
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

🚨 Краевые случаи:

1. Пустой массив - возвращаем пустой массив
2. Массив из одного элемента - возвращаем массив без изменений
3. Уже отсортированный массив - может быть худшим случаем для naive выбора pivot
4. Все элементы одинаковые - алгоритм должен корректно обрабатывать
5. Большие массивы - возможна ошибка максимальной глубины рекурсии

🎯 Задача 5: Сортировка слиянием (MergeSort)

📋 Описание задачи:

💡 Подход к решению:

1. Разделение: Рекурсивно разделить массив на две половины до тех пор, пока каждый подмассив не будет содержать один элемент (или пуст)
2. Слияние: Рекурсивно объединять отсортированные подмассивы в один отсортированный массив

⚡ Сложность алгоритма:

• Временная сложность: Всегда O(n log n)
• Пространственная сложность: O(n) - требуется дополнительный массив для слияния
• Стабильность: Да (сохраняет порядок равных элементов)
• Примечание: Всегда имеет O(n log n), нет худшего случая как у QuickSort

📝 Пример кода (рекурсивная реализация):

def merge_sort(arr):
    """Рекурсивная реализация сортировки слиянием"""
    # Базовый случай: массивы длиной 0 или 1 уже отсортированы
    if len(arr) <= 1:
        return arr
    # Находим середину массива
    mid = len(arr) // 2
    # Рекурсивно сортируем левую и правую половины
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    # Сливаем отсортированные половины
    return merge(left_half, right_half)

def merge(left, right):
    """Слияние двух отсортированных массивов в один"""
    result = []
    i = j = 0  # Указатели для левого и правого массивов
    # Сравниваем элементы из обоих массивов и добавляем меньший в результат
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Добавляем оставшиеся элементы из левого массива
    result.extend(left[i:])
    # Добавляем оставшиеся элементы из правого массива
    result.extend(right[j:])
    return result

📝 Пример кода (in-place реализация):

def merge_sort_inplace(arr, left=0, right=None, temp=None):
    """In-place реализация сортировки слиянием"""
    if right is None:
        right = len(arr) - 1
    if temp is None:
        temp = [0] * len(arr)
    if left < right:
        mid = (left + right) // 2
        # Рекурсивно сортируем левую и правую половины
        merge_sort_inplace(arr, left, mid, temp)
        merge_sort_inplace(arr, mid + 1, right, temp)
        # Сливаем отсортированные половины
        merge_inplace(arr, left, mid, right, temp)

def merge_inplace(arr, left, mid, right, temp):
    """In-place слияние двух отсортированных частей массива"""
    i, j, k = left, mid + 1, left
    # Копируем элементы во временный массив
    for idx in range(left, right + 1):
        temp[idx] = arr[idx]
    # Сливаем обратно в исходный массив
    while i <= mid and j <= right:
        if temp[i] <= temp[j]:
            arr[k] = temp[i]
            i += 1
        else:
            arr[k] = temp[j]
            j += 1
        k += 1
    # Копируем оставшиеся элементы из левой половины
    while i <= mid:
        arr[k] = temp[i]
        i += 1
        k += 1

🎯 Задача 6: Бинарный поиск (Binary Search)

📋 Описание задачи:

💡 Подход к решению:

⚡ Сложность алгоритма:

• Временная сложность: O(log n) — на каждом шаге область поиска уменьшается вдвое
• Пространственная сложность: O(1) — используется только несколько переменных
• Требование: Массив должен быть отсортирован

📝 Пример кода (итеративная реализация):

def binary_search(arr, target):
    """Итеративная реализация бинарного поиска"""
    left, right = 0, len(arr) - 1
    while left <= right:
        # Вычисляем средний индекс (предотвращаем переполнение)
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid  # Элемент найден
        elif arr[mid] < target:
            left = mid + 1  # Ищем в правой половине
        else:
            right = mid - 1  # Ищем в левой половине
    return -1  # Элемент не найден

📝 Пример кода (рекурсивная реализация):

def binary_search_recursive(arr, target, left=0, right=None):
    """Рекурсивная реализация бинарного поиска"""
    if right is None:
        right = len(arr) - 1
    # Базовый случай: элемент не найден
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid  # Элемент найден
    elif arr[mid] < target:
        # Рекурсивно ищем в правой половине
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        # Рекурсивно ищем в левой половине
        return binary_search_recursive(arr, target, left, mid - 1)

🚨 Краевые случаи:

1. Пустой массив - возвращаем -1
2. Массив из одного элемента - проверяем этот элемент
3. Элемент отсутствует - возвращаем -1
4. Повторяющиеся элементы - может вернуть любой индекс с этим значением
5. Неотсортированный массив - алгоритм не работает корректно

🎯 Задача 7: Поиск в глубину (Depth-First Search, DFS)

📋 Описание задачи:

💡 Подход к решению:

1. Начать с заданной вершины
2. Пометить вершину как посещенную
3. Рекурсивно посетить все непосещенные соседние вершины

⚡ Сложность алгоритма:

• Временная сложность: O(V + E), где V - количество вершин, E - количество ребер
• Пространственная сложность: O(V) - для хранения посещенных вершин и стека/стека вызовов
• Примечание: Работает для направленных и ненаправленных графов

📝 Пример кода (рекурсивная реализация):

def dfs_recursive(graph, start, visited=None):
    """Рекурсивная реализация DFS"""
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")  # Обработка вершины
    # Рекурсивно посещаем всех непосещенных соседей
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

📝 Пример кода (итеративная реализация со стеком):

def dfs_iterative(graph, start):
    """Итеративная реализация DFS с использованием стека"""
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=" ")  # Обработка вершины
            # Добавляем всех соседей в стек (в обратном порядке для порядка как у рекурсивного)
            for neighbor in reversed(graph.get(vertex, [])):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

📝 Пример кода (DFS с возвратом пути):

def dfs_path(graph, start, target):
    """DFS с поиском пути от start до target"""
    stack = [(start, [start])]  # (вершина, путь до нее)
    visited = set()
    while stack:
        vertex, path = stack.pop()
        if vertex == target:
            return path
        if vertex not in visited:
            visited.add(vertex)
            for neighbor in graph.get(vertex, []):
                if neighbor not in visited:
                    stack.append((neighbor, path + [neighbor]))
    return None  # Путь не найден

🎯 Задача 8: Поиск в ширину (Breadth-First Search, BFS)

📋 Описание задачи:

💡 Подход к решению:

1. Создать очередь и положить в нее начальную вершину
2. Пометить начальную вершину как посещенную
3. Пока очередь не пуста:
   • Извлечь вершину из начала очереди
   • Обработать вершину (например, добавить в результат)
   • Для каждого непосещенного соседа:
     • Пометить как посещенный
     • Добавить в конец очереди

⚡ Сложность алгоритма:

• Временная сложность: O(V + E), где V - количество вершин, E - количество ребер
• Пространственная сложность: O(V) - для хранения посещенных вершин и очереди
• Примечание: Всегда находит кратчайший путь в невзвешенном графе

📝 Пример кода (базовая реализация):

from collections import deque

def bfs(graph, start):
    """Базовая реализация BFS"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")  # Обработка вершины
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

📝 Пример кода (BFS с поиском кратчайшего пути):

def bfs_shortest_path(graph, start, target):
    """BFS с поиском кратчайшего пути"""
    if start == target:
        return [start]
    visited = set([start])
    queue = deque([(start, [start])])  # (вершина, путь до вершины)
    while queue:
        vertex, path = queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor == target:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None  # Путь не найден

📝 Пример кода (BFS по уровням):

def bfs_level_order(graph, start):
    """BFS с разделением по уровням"""
    if not graph:
        return []
    visited = set([start])
    queue = deque([start])
    levels = []
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            vertex = queue.popleft()
            current_level.append(vertex)
            for neighbor in graph.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        levels.append(current_level)
    return levels

🎉 Итог разобрано:

1. ✅ Two Sum - алгоритм поиска двух чисел с заданной суммой
2. ✅ Проверка на палиндром - определение симметричности строки
3. ✅ Реверс связного списка - разворот односвязного списка
4. ✅ Быстрая сортировка (QuickSort) - алгоритм сортировки "разделяй и властвуй"
5. ✅ Сортировка слиянием (MergeSort) - стабильный алгоритм сортировки
6. ✅ Бинарный поиск - эффективный поиск в отсортированном массиве
7. ✅ Поиск в глубину (DFS) - обход графа в глубину
8. ✅ Поиск в ширину (BFS) - обход графа в ширину

📊 Каждое решение содержит:

• 📋 Четкое описание задачи
• 💡 Подход к решению с объяснением алгоритма
• ⚡ Анализ временной и пространственной сложности
• 📝 Примеры кода с комментариями
• 🚨 Разбор краевых случаев
• ✅ Примеры использования
• 🎓 Альтернативные подходы и вариации

Желаем успеха на собеседовании!