Алгоритмы и структуры данных: полный разбор для собеседований

Алгоритмы и структуры данных: то, что спрашивают на собеседованиях Big O, сортировки, хеш-таблицы, деревья — без этого не обходится ни одно техническое собеседование в продуктовые компании. Разберём с примерами. Нотация Big O Big O описывает, как растёт время выполнения алгоритма при увеличении входных данных. Нас интересует худший случай. O(1) — константное время: доступ к элементу массива по индексу O(log n) — логарифмическое: бинарный поиск O(n) — линейное: обход массива O(n log n) — быстрая сортировка, merge sort O(n²) — пузырьковая сортировка, вложенные циклы

Merge Sort — разбор по шагам Merge Sort — алгоритм «разделяй и властвуй». Сложность O(n log n) в любом случае, что делает его надёжным выбором. 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 return result + left[i:] + right[j:] Хеш-таблицы Хеш-таблица (dict в Python, Map в JS) даёт O(1) на вставку, удаление и поиск в среднем случае. Незаменима для задач на уникальность и подсчёт. # Задача: найти два числа, сумма которых равна target 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 [] # O(n) время, O(n) память — намного лучше O(n²) с двумя циклами

Бинарное дерево поиска (BST) В BST для каждого узла: все левые потомки меньше, все правые — больше. Поиск, вставка, удаление — O(log n) при сбалансированном дереве. class Node: def __init__(self, val): self.val = val self.left = self.right = None def insert(root, val): if not root: return Node(val) if val < root.val: root.left = insert(root.left, val) else: root.right = insert(root.right, val) return root def inorder(root): """Обход в порядке возрастания""" if root: yield from inorder(root.left) yield root.val yield from inorder(root.right) Что готовить к собеседованию Массивы и строки: sliding window, two pointers Связные списки: разворот, нахождение цикла Деревья: DFS, BFS, LCA Динамическое программирование: fibonacci, knapsack, LCS Графы: DFS/BFS, Dijkstra для взвешенных Рекомендую решать по 1–2 задачи в день на LeetCode, начиная с Easy, затем Medium.