43 вопроса по теме «структуры данных и алгоритмы» на собеседовании

Короткий ответ: Big O описывает, как растёт время работы или потребление памяти алгоритма при увеличении размера входных данных n, отбрасывая константы и младшие члены. Это верхняя оценка скорости роста.

Подробно:

Big O отвечает на вопрос «что произойдёт, когда n станет очень большим?». Нас не интересует точное число операций, а только характер роста. Поэтому O(2n + 100) упрощается до O(n), а O(3n² + n) — до O(n²).

Основные классы роста (от лучшего к худшему):

# O(1) — константа: не зависит от n
def first(arr):
    return arr[0] if arr else None

# O(log n) — логарифм: каждый шаг делит задачу пополам (бинарный поиск)
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# O(n) — линейная: один проход
def total(arr):
    s = 0
    for x in arr:        # n итераций
        s += x
    return s

# O(n log n) — эффективные сортировки (merge, quick, Timsort)
def sort_it(arr):
    return sorted(arr)

# O(n^2) — квадрат: вложенный цикл
def has_dup_naive(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# O(2^n) — экспонента: наивный Фибоначчи, перебор подмножеств
def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

Ориентир по росту при n = 1 000 000: O(1) — 1 операция, O(log n) — ~20, O(n) — миллион, O(n log n) — ~20 млн, O(n²) — триллион (уже слишком), O(2^n) — нереально даже при n = 50.

⚠️ Ловушка: Big O — это про асимптотику (поведение при больших n), а не про реальное время. O(n) алгоритм может быть медленнее O(n²) на маленьких данных из-за больших констант. Также путают: Big O (верхняя граница, Ω — нижняя, Θ — точная), в собесах под «O» обычно подразумевают Θ.

Короткий ответ: Time complexity — как растёт время (число операций), space complexity — как растёт дополнительная память, которую использует алгоритм помимо входных данных.

Подробно:

Эти две метрики оцениваются независимо, и часто между ними есть компромисс (time-space tradeoff): можно ускорить ценой памяти и наоборот.

# Time O(n), Space O(1) — считаем на месте, лишней памяти нет
def sum_inplace(arr):
    s = 0
    for x in arr:
        s += x
    return s

# Time O(n), Space O(n) — кешируем виденные элементы ради скорости поиска
def has_dup_fast(arr):
    seen = set()          # доп. память растёт с n -> O(n)
    for x in arr:
        if x in seen:     # поиск в set O(1)
            return True
        seen.add(x)
    return False

Во втором примере мы пожертвовали памятью (set на n элементов), чтобы получить O(n) по времени вместо O(n²) наивного перебора. Это классический tradeoff.

Для рекурсии space обычно включает глубину стека вызовов: рекурсивный обход дерева — O(h) памяти, где h — высота.

⚠️ Ловушка: входные данные обычно не считаются в space complexity — считается только дополнительная память. Также часто забывают про стек рекурсии: «итеративный» алгоритм с O(1) доп. памяти после переписывания в рекурсию становится O(n) по памяти.

Короткий ответ: Амортизированная сложность — это средняя стоимость операции в худшем случае, усреднённая по длинной последовательности операций. Отдельная операция может быть дорогой, но «в среднем» дёшево.

Подробно:

Классический пример — list.append() в Python. Обычно это O(1), но иногда массив переполняется и нужно выделить новый блок памяти и скопировать всё → O(n). Однако расширения происходят редко (размер растёт мультипликативно), поэтому амортизированно append — O(1).

# n операций append
lst = []
for i in range(n):
    lst.append(i)   # каждая в среднем O(1), хотя редкие — O(n)
# суммарно O(n), а не O(n^2)

Логика: если массив каждый раз увеличивается, например, в ~1.125 раза (CPython), то общая стоимость всех копирований при n вставках — O(n). Делим на n операций → O(1) на операцию.

⚠️ Ловушка: амортизированная O(1) ≠ гарантированная O(1). Если важна предсказуемая задержка (real-time системы), отдельный append может «застрять» на O(n). Не путать амортизированную сложность со средним случаем (average case) — это разные понятия: средний случай про распределение входов, амортизация про последовательность операций.

Короткий ответ: Это оценки сложности при разных входных данных: best case — самый удачный вход, worst case — самый неудачный, average case — усреднённый по типичному распределению. В собесах и продакшене обычно ориентируются на worst и average.

Подробно:

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

Для линейного поиска:

• Best case O(1) — элемент в начале.
• Worst case O(n) — элемента нет или он в конце.
• Average case O(n) — в среднем проходим половину, но это всё равно O(n).

Яркий пример расхождения — quick sort: средний случай O(n log n), но худший O(n²) при неудачном выборе опорного элемента (например, уже отсортированный массив с pivot = первый элемент).

⚠️ Ловушка: при проектировании систем закладывайтесь на худший случай, особенно если вход может контролировать злоумышленник (Hash DoS-атаки эксплуатируют worst case хеш-таблиц, заставляя все ключи коллизироваться → O(n)).

Короткий ответ: Big O позволяет предсказать, как код поведёт себя при росте данных, и заранее выбрать структуру/алгоритм, который не «упрётся» в производительность. Константы важнее на маленьких и фиксированных n.

Подробно:

На практике Big O спасает от ситуаций «работало на 100 записях, легло на 10 миллионах». Пример: проверка наличия элемента в list — O(n), в set/dict — O(1). На больших данных замена list на set для членских проверок даёт кратное ускорение.

# ПЛОХО: O(n*m) — для каждого из n запросов линейный поиск в списке
allowed_list = [...]              # m элементов
result = [q for q in queries if q in allowed_list]

# ХОРОШО: O(n) — поиск в set амортизированно O(1)
allowed = set(allowed_list)
result = [q for q in queries if q in allowed]

Когда константы важнее асимптотики:

• n маленькое и фиксированное (например, всегда ≤ 10) — простой O(n²) может быть быстрее и читаемее «умного» O(n log n).
• Скрытые константы велики: алгоритм с лучшей асимптотикой может иметь огромный накладной расход (сложные структуры данных, кеш-промахи).
• Линейный проход по непрерывному массиву часто быстрее «теоретически лучшего» обхода связной структуры из-за локальности кеша процессора.

⚠️ Ловушка: преждевременная оптимизация по Big O без профилирования. Сначала измерьте, где реальное узкое место — иногда O(n²) на 50 элементах не стоит внимания, а O(n) запрос в БД внутри цикла убивает всё.

Короткий ответ: Python list — это динамический массив: непрерывный блок памяти с указателями на объекты. Доступ по индексу O(1), потому что адрес элемента вычисляется арифметически: base + index * size.

Подробно:

arr = [10, 20, 30, 40]
arr[2]          # O(1): сразу считаем адрес, без перебора
arr[-1]         # O(1): len-1
arr.append(5)   # амортизированно O(1) — добавление в конец
arr.pop()       # O(1) — удаление с конца
arr.insert(0, 99)  # O(n)! сдвиг всех элементов вправо
arr.pop(0)         # O(n)! сдвиг всех элементов влево
99 in arr          # O(n) — линейный поиск

Сложности list:

• Доступ/изменение по индексу — O(1).
• append/pop с конца — амортизированно O(1).
• insert/pop в начале или середине — O(n) (сдвиг элементов).
• Поиск (in, index) — O(n).

⚠️ Ловушка: list.pop(0) и list.insert(0, x) — это O(n), а не O(1). Если нужны частые операции с обоих концов — используйте collections.deque (O(1) с обоих концов).

Короткий ответ: Когда массив заполняется, выделяется новый блок памяти большего размера (мультипликативный рост) и элементы копируются. Так как расширения редки, средняя стоимость append — O(1).

Подробно:

CPython хранит для list текущий размер (ob_size) и выделенную ёмкость (allocated). Пока size < allocated, append просто пишет элемент — O(1). Когда место кончается, ёмкость увеличивается по формуле примерно new = size + (size >> 3) + 6 (рост ~12.5%), и происходит копирование — O(n).

Почему амортизированно O(1): суммарная стоимость всех копирований при n вставках образует геометрическую прогрессию и в сумме даёт O(n). Делим на n операций → O(1) на одну.

import sys
lst = []
prev = -1
for i in range(20):
    lst.append(i)
    cap = sys.getsizeof(lst)   # видно ступенчатый рост ёмкости
    if cap != prev:
        print(len(lst), cap)
        prev = cap

Если заранее известен размер, эффективнее аллоцировать сразу: list comprehension или [None] * n избегают промежуточных перевыделений.

⚠️ Ловушка: не путать амортизированное O(1) с тем, что отдельный append всегда дёшев — при попадании на расширение он O(n). Также: рост мультипликативный (в разы), а не на константу — иначе append стал бы O(n) амортизированно.

Короткий ответ: Связный список хранит элементы как узлы, каждый ссылается на следующий (singly) или на следующий и предыдущий (doubly). Вставка/удаление при известном узле — O(1), но доступ по индексу и поиск — O(n).

Подробно:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None      # singly: только вперёд
        # self.prev = None    # doubly: + назад

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, val):     # O(1)
        node = Node(val)
        node.next = self.head
        self.head = node

    def find(self, val):           # O(n)
        cur = self.head
        while cur:
            if cur.val == val:
                return cur
            cur = cur.next
        return None

Сложности:

• Вставка/удаление в голову — O(1).
• Вставка/удаление при наличии ссылки на узел — O(1) (для удаления в singly нужен предыдущий узел, в doubly — нет).
• Доступ по индексу k — O(n) (нет арифметики адресов, идём по ссылкам).
• Поиск — O(n).

Singly vs doubly: doubly позволяет идти в обе стороны и удалять узел за O(1) по ссылке, но тратит дополнительную память на указатель prev.

⚠️ Ловушка: в Python связный список почти никогда не нужен — встроенный list (динамический массив) и deque (двусвязный список под капотом) покрывают потребности. Связный список спрашивают как тему алгоритмов (разворот, поиск цикла). Также: у связного списка плохая локальность кеша — узлы разбросаны в памяти.

Короткий ответ: Массив — когда нужен быстрый доступ по индексу и хорошая локальность памяти. Связный список — когда часто вставляете/удаляете в середине/начале и есть ссылка на узел.

Подробно:

На практике в Python почти всегда выигрывает list или deque, потому что:

• доступ по индексу нужен чаще, чем кажется;
• непрерывная память даёт огромный выигрыш за счёт кеша CPU;
• константы у массива меньше.

Связный список оправдан, когда нужны O(1) вставки/удаления в произвольной позиции при уже имеющейся ссылке (например, LRU-кеш — OrderedDict или doubly linked list).

⚠️ Ловушка: «связный список лучше для вставок» — верно только если у вас уже есть ссылка на нужный узел. Если позицию надо ещё найти, то поиск O(n) съедает преимущество, и массив часто оказывается быстрее на практике.

Короткий ответ: Стек — LIFO (последний пришёл — первый ушёл), очередь — FIFO (первый пришёл — первый ушёл). Дек (deque) — двусторонняя очередь. В Python всё реализуется через collections.deque за O(1).

Подробно:

from collections import deque

# СТЕК (LIFO): push/pop с одного конца
stack = []
stack.append(1)      # push, O(1)
stack.append(2)
stack.pop()          # -> 2, O(1)
# list годится для стека: append/pop с конца дёшевы

# ОЧЕРЕДЬ (FIFO): добавляем в конец, забираем из начала
queue = deque()
queue.append(1)      # enqueue, O(1)
queue.append(2)
queue.popleft()      # -> 1, O(1)
# НЕ используйте list: list.pop(0) -> O(n)!

# ДЕК (двусторонняя очередь): O(1) с обоих концов
dq = deque()
dq.appendleft(0)     # O(1)
dq.append(1)         # O(1)
dq.popleft(); dq.pop()

Применения:

• Стек: обход DFS, отмена операций (undo), вычисление выражений, проверка скобок, стек вызовов функций.
• Очередь: обход BFS, планировщики задач, буферы, обработка событий в порядке поступления.
• Дек: скользящее окно максимума, очередь с двумя концами.

⚠️ Ловушка: для очереди не используйте list с pop(0) — это O(n) на операцию, очередь из n элементов станет O(n²). Всегда collections.deque. Для потокобезопасной очереди между потоками — queue.Queue.

Короткий ответ: Hash map хранит пары ключ-значение в массиве «корзин» (buckets). Хеш-функция превращает ключ в индекс корзины. Когда два ключа дают один индекс — это коллизия, разрешается chaining или open addressing.

Подробно:

Алгоритм поиска по ключу:

1. Вычислить hash(key) — целое число.
2. Свести к индексу: index = hash(key) % capacity.
3. Перейти в корзину index, найти точное совпадение ключа.

Разрешение коллизий:

• Chaining (цепочки): в каждой корзине — список элементов с одинаковым индексом. Поиск внутри корзины линейный.
• Open addressing (открытая адресация): при коллизии ищем следующую свободную ячейку по правилу пробирования. CPython dict использует именно открытую адресацию.

Load factor = (число элементов) / (число корзин). Когда он превышает порог (~2/3 в CPython), таблица рехешируется — выделяется массив побольше и все элементы перераспределяются. Это держит коллизии редкими.

d = {}
d["apple"] = 1       # вставка, амортизированно O(1)
d["apple"]           # доступ, O(1) средн.
"apple" in d         # проверка, O(1) средн.
del d["apple"]       # удаление, O(1) средн.

# Ключ должен быть hashable (неизменяемый)
d[(1, 2)] = "ok"     # кортеж — можно
# d[[1, 2]] = "no"   # TypeError: list не hashable

⚠️ Ловушка: ключи dict должны быть хешируемыми (иметь __hash__, обычно неизменяемые типы). list, dict, set нельзя использовать как ключи; кортеж — можно (если внутри только хешируемое). Если переопределяете __eq__, обязательно согласованно переопределите __hash__.

Короткий ответ: O(1) потому что хеш-функция даёт прямой адрес корзины без перебора. Деградирует до O(n), когда множество ключей даёт одинаковые хеши (коллизии), и поиск превращается в линейный обход.

Подробно:

В среднем случае с хорошей хеш-функцией и контролируемым load factor доступ/вставка/удаление — O(1). Хеш равномерно «размазывает» ключи по корзинам, и в каждой их мало.

Деградация до O(n) в худшем случае:

• Все ключи коллизируются (попадают в одну корзину/цепочку) → поиск линейный.
• Это можно вызвать намеренно (Hash DoS): подобрать входы с одинаковым хешем. Поэтому Python с версии 3.3 включает рандомизацию хеша строк (PYTHONHASHSEED).

# Плохая (искусственная) хеш-функция -> всё в одну корзину
class BadKey:
    def __init__(self, v): self.v = v
    def __hash__(self): return 1          # ВСЕ коллизируют!
    def __eq__(self, o): return self.v == o.v
# dict из таких ключей выродится в O(n) на операцию

В реальности с встроенными типами (int, str, tuple) хеш хороший, и dict стабильно O(1).

⚠️ Ловушка: «dict всегда O(1)» — неточно. Это средний/амортизированный случай. Рехеширование при росте — редкая O(n) операция (амортизируется). Худший случай при патологических коллизиях — O(n).

Короткий ответ: set — неупорядоченная коллекция уникальных хешируемых элементов, реализованная как hash map без значений. Даёт O(1) проверку принадлежности, добавление и удаление.

Подробно:

s = {1, 2, 3}
s.add(4)         # O(1) средн.
s.discard(2)     # O(1) средн., без ошибки если нет
3 in s           # O(1) средн. — главная польза set!

# Множественные операции
a, b = {1, 2, 3}, {2, 3, 4}
a & b            # пересечение -> {2, 3}
a | b            # объединение -> {1, 2, 3, 4}
a - b            # разность   -> {1}
a ^ b            # симм. разность -> {1, 4}

# Дедупликация за O(n)
unique = list(set([1, 1, 2, 3, 3]))

Применения: убрать дубликаты, быстрая проверка «видели ли уже», операции над множествами, отслеживание посещённых вершин в графе.

⚠️ Ловушка: set не сохраняет порядок и не индексируется (s[0] — ошибка). Если нужен уникальный набор с сохранением порядка вставки — используйте dict.fromkeys(...) (dict с Python 3.7 хранит порядок) или list(dict.fromkeys(items)).

Короткий ответ: Бинарное дерево — структура, где у каждого узла не более двух потомков. BST (binary search tree) — бинарное дерево с инвариантом: левое поддерево < узел < правое поддерево, что даёт поиск за O(log n) в сбалансированном случае.

Подробно:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bst_insert(root, val):           # O(h), h = высота
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    else:
        root.right = bst_insert(root.right, val)
    return root

def bst_search(root, val):           # O(h)
    while root:
        if val == root.val:
            return root
        root = root.left if val < root.val else root.right
    return None

В сбалансированном BST высота h ≈ log n, поэтому поиск/вставка/удаление — O(log n). В вырожденном случае (вставка отсортированных данных) дерево превращается в «список», h = n, и операции становятся O(n).

⚠️ Ловушка: обычный BST не самобалансирующийся. Вставка уже отсортированной последовательности (1, 2, 3, 4...) даёт вырожденное дерево с O(n). Чтобы гарантировать O(log n), нужны самобалансирующиеся деревья (AVL, red-black).

Короткий ответ: DFS-обходы (in/pre/post-order) идут вглубь и различаются моментом обработки узла. BFS обходит по уровням слева направо. Для BST in-order даёт отсортированный порядок.

Подробно:

from collections import deque

# DFS — рекурсия (стек вызовов)
def preorder(node):    # узел -> лево -> право
    if not node: return
    print(node.val); preorder(node.left); preorder(node.right)

def inorder(node):     # лево -> узел -> право  (для BST = отсортировано!)
    if not node: return
    inorder(node.left); print(node.val); inorder(node.right)

def postorder(node):   # лево -> право -> узел  (удаление дерева, выражения)
    if not node: return
    postorder(node.left); postorder(node.right); print(node.val)

# BFS — по уровням, через очередь
def bfs(root):
    if not root: return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

Все обходы — O(n) по времени (посещаем каждый узел). Память: DFS — O(h) (стек), BFS — O(w) (ширина уровня, в худшем O(n)).

Применения: in-order — отсортированный вывод BST; pre-order — копирование/сериализация дерева; post-order — удаление узлов, вычисление выражений; BFS — поиск кратчайшего пути по числу рёбер, обход по уровням.

⚠️ Ловушка: глубокая рекурсия DFS может переполнить стек (Python лимит ~1000). Для очень глубоких деревьев используйте итеративный DFS с явным стеком или повысьте sys.setrecursionlimit.

Короткий ответ: Самобалансирующиеся BST автоматически поддерживают высоту O(log n) при вставках/удалениях через повороты. AVL строго сбалансированы (быстрее поиск), red-black слабее сбалансированы (быстрее вставки).

Подробно:

Проблема обычного BST — вырождение в список при неудачном порядке вставки. Сбалансированные деревья решают это, перестраивая структуру:

• AVL-дерево: инвариант — разница высот поддеревьев каждого узла ≤ 1. После вставки/удаления выполняются повороты (rotations) для восстановления баланса. Жёстко сбалансировано → быстрый поиск, но больше поворотов при модификациях.
• Red-black дерево: узлы окрашены в красный/чёрный, набор правил гарантирует высоту ≤ 2 log n. Менее строгий баланс → меньше поворотов при вставке/удалении, поэтому используется там, где много модификаций (например, в реализациях map/set в C++ STL, Java TreeMap).

Все операции (поиск, вставка, удаление) — гарантированно O(log n).

# В Python нет встроенного сбалансированного дерева.
# Если нужна отсортированная структура с O(log n) — sortedcontainers:
from sortedcontainers import SortedList
sl = SortedList([5, 1, 3])
sl.add(2)            # O(log n) поддержка порядка
sl.bisect_left(3)    # O(log n) поиск позиции

⚠️ Ловушка: в Python нет встроенного балансированного дерева, и в собесах часто ждут, что вместо «дерева» вы используете dict/set (хеш, O(1)) или heapq (куча). Сбалансированные деревья нужны, когда требуется упорядоченность (диапазонные запросы, ближайший меньший/больший), чего хеш не даёт.

Короткий ответ: Куча — бинарное дерево в массиве, где родитель ≤ потомков (min-heap) или ≥ (max-heap). Даёт O(1) доступ к минимуму/максимуму и O(log n) вставку/извлечение. Реализует приоритетную очередь.

Подробно:

import heapq

# heapq реализует MIN-heap на обычном списке
h = []
heapq.heappush(h, 5)      # O(log n)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappop(h)          # -> 1, извлечь минимум, O(log n)
h[0]                      # -> минимум без извлечения, O(1)
heapq.heapify(arr)        # построить кучу из списка, O(n)!

# MAX-heap: храним отрицания
heapq.heappush(h, -val)
-heapq.heappop(h)

Сложности: построение кучи из массива — O(n) (не O(n log n)!), push/pop — O(log n), peek минимума — O(1).

Применение — Top K за O(n log k) вместо полной сортировки O(n log n):

# K самых больших элементов
def top_k(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)        # min-heap размера k
        if len(h) > k:
            heapq.heappop(h)        # выкидываем наименьший
    return h
# Или просто: heapq.nlargest(k, nums)

Другие применения: алгоритм Дейкстры, слияние k отсортированных списков, планировщик задач по приоритету, медиана потока (две кучи).

⚠️ Ловушка: heapq — только min-heap; для max-heap инвертируйте знаки. При хранении кортежей (priority, item) Python сравнивает по второму элементу при равных приоритетах — если item несравним, будет TypeError; добавляйте уникальный счётчик: (priority, counter, item).

Короткий ответ: Trie — дерево, где каждый путь от корня кодирует строку, а узлы соответствуют префиксам. Поиск/вставка слова — O(L), где L — длина слова, независимо от числа слов.

Подробно:

class TrieNode:
    def __init__(self):
        self.children = {}      # символ -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):              # O(L)
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):              # O(L)
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):       # O(L)
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Применения: автодополнение, проверка орфографии, поиск по префиксу, T9, IP-роутинг. Преимущество над хеш-таблицей — эффективные префиксные запросы и упорядоченный обход.

⚠️ Ловушка: trie может занимать много памяти (узел на каждый символ). Если нужны только точные совпадения без префиксных запросов — set/dict проще и компактнее.

Короткий ответ: Матрица смежности — двумерный массив V×V, быстрая проверка ребра O(1), но O(V²) памяти. Список смежности — для каждой вершины список соседей, O(V+E) памяти, эффективен для разреженных графов.

Подробно:

# Список смежности (чаще всего) — O(V + E) памяти
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [],
}
# для взвешенного: 0: [(1, 5), (2, 3)]  # (сосед, вес)

# Матрица смежности — O(V^2) памяти
V = 4
matrix = [[0] * V for _ in range(V)]
matrix[0][1] = 1        # ребро 0->1
# проверка ребра matrix[u][v] -> O(1)

⚠️ Ловушка: для разреженных графов (рёбер мало, E << V²) — почти всегда список смежности. Матрица оправдана для плотных графов или когда нужны очень частые проверки «есть ли ребро». Направленный граф: u->v не означает v->u; ненаправленный — добавляйте ребро в обе стороны.

Короткий ответ: BFS обходит вширь через очередь (находит кратчайший путь по числу рёбер), DFS — вглубь через стек/рекурсию. Оба O(V+E). Цикл ищется через отслеживание состояний вершин.

Подробно:

from collections import deque

def bfs(graph, start):                    # O(V + E)
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)           # помечаем ДО добавления!
                q.append(nb)
    return visited

def dfs(graph, start, visited=None):      # O(V + E)
    if visited is None:
        visited = set()
    visited.add(start)
    for nb in graph[start]:
        if nb not in visited:
            dfs(graph, nb, visited)
    return visited

# Поиск цикла в НАПРАВЛЕННОМ графе (три цвета)
def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph}
    def dfs(v):
        color[v] = GRAY                   # в процессе обработки
        for nb in graph[v]:
            if color[nb] == GRAY:         # ребро в "серую" -> цикл
                return True
            if color[nb] == WHITE and dfs(nb):
                return True
        color[v] = BLACK                  # обработан полностью
        return False
    return any(color[v] == WHITE and dfs(v) for v in graph)

Ключевое отличие: BFS гарантирует кратчайший путь в невзвешенном графе; DFS удобен для топологической сортировки, поиска компонент связности, обнаружения циклов. Для ненаправленного графа цикл проще: при DFS нашли уже посещённую вершину, не являющуюся родителем.

⚠️ Ловушка: в BFS помечайте вершину посещённой при добавлении в очередь, а не при извлечении — иначе одна вершина попадёт в очередь много раз. Для взвешенного графа кратчайший путь — это Дейкстра (heapq), а не обычный BFS.

Короткий ответ: Простые (bubble, selection, insertion) — O(n²), годятся для маленьких/почти отсортированных данных. Эффективные (merge, quick, heap) — O(n log n). Различаются по стабильности и памяти.

Подробно:

# Insertion sort — O(n^2), но O(n) на почти отсортированных, стабильная
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key, j = arr[i], i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Selection sort — всегда O(n^2), нестабильная, O(1) памяти
def selection_sort(arr):
    for i in range(len(arr)):
        m = min(range(i, len(arr)), key=lambda k: arr[k])
        arr[i], arr[m] = arr[m], arr[i]
    return arr

Stable (стабильная) сортировка сохраняет относительный порядок равных элементов — важно при многоуровневой сортировке.

⚠️ Ловушка: «O(n²) сортировки бесполезны» — неверно. Insertion sort быстрее на малых n (поэтому Timsort использует его на маленьких блоках) и O(n) на почти отсортированных данных. Selection sort минимизирует число обменов.

Короткий ответ: Merge sort — стабильный, гарантированный O(n log n), но O(n) доп. памяти. Quick sort — in-place (O(log n) стека), быстр на практике, но худший случай O(n²) и нестабилен.

Подробно:

# MERGE SORT: разделяй (пополам) и властвуй (слияние)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # слияние двух отсортированных — O(n)
    res, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= -> стабильность
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res

# QUICK SORT: выбираем pivot, разбиваем, рекурсия
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

• Merge sort: всегда O(n log n), стабильна, предсказуема. Минус — O(n) память. Хорош для связных списков и внешней сортировки (данные не влезают в память).
• Quick sort: в среднем O(n log n) с малыми константами (быстрее merge на практике), in-place. Минус — худший O(n²) при плохом pivot (минимизируется случайным выбором или «медиана трёх»), нестабилен.

⚠️ Ловушка: худший случай quick sort O(n²) возникает на уже отсортированном массиве, если pivot — крайний элемент. На собесе упомяните рандомизацию pivot. Наивная реализация выше создаёт новые списки (O(n) память) — настоящий quick sort разбивает in-place.

Короткий ответ: Timsort — гибридный алгоритм (merge + insertion sort), используемый в sorted() и list.sort(). O(n log n) в худшем, O(n) на почти отсортированных данных, стабильный.

Подробно:

Timsort находит уже отсортированные участки («runs»), при необходимости расширяет их insertion sort'ом, затем сливает их как в merge sort. Это даёт огромный выигрыш на реальных данных, которые часто частично упорядочены.

sorted([3, 1, 2])                 # -> [1, 2, 3], O(n log n), стабильная
sorted(words, key=len)            # сортировка по ключу
sorted(data, key=lambda x: (x.age, x.name))   # многоуровневая
sorted(arr, reverse=True)         # по убыванию
arr.sort()                        # in-place, экономит память

Свойства: стабильный (сохраняет порядок равных), адаптивный (O(n) на отсортированных), O(n) доп. памяти.

⚠️ Ловушка: list.sort() сортирует на месте и возвращает None; sorted() возвращает новый список. Частая ошибка: x = mylist.sort() → x будет None. Стабильность Timsort позволяет сортировать по нескольким ключам последовательно (но эффективнее одним ключом-кортежем).

Короткий ответ: Линейный поиск перебирает все элементы — O(n), работает на любых данных. Бинарный поиск делит диапазон пополам — O(log n), но требует отсортированного массива.

Подробно:

def linear_search(arr, target):       # O(n), данные любые
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

import bisect
arr = [1, 3, 5, 7, 9]
i = bisect.bisect_left(arr, 5)        # O(log n), позиция 5 -> 2
found = i < len(arr) and arr[i] == 5  # проверка наличия
bisect.insort(arr, 4)                 # вставка с сохранением порядка

Бинарный поиск O(log n): каждое сравнение отбрасывает половину кандидатов. Для n = 1 000 000 достаточно ~20 шагов.

⚠️ Ловушка: бинарный поиск работает только на отсортированных данных. Если массив не отсортирован, сначала сортировка O(n log n) — и тогда для одного поиска проще линейный O(n). Бинарный выгоден при многократных поисках по одному отсортированному массиву.

Короткий ответ: Главные источники багов — границы цикла (< vs <=), вычисление середины и обновление границ. Используйте инвариант полузакрытого интервала и согласованные обновления.

Подробно:

# Вариант 1: закрытый интервал [lo, hi], условие lo <= hi
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                    # <= ! иначе пропустим случай lo==hi
        mid = lo + (hi - lo) // 2      # без переполнения (в Python не критично)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1               # +1 !
        else:
            hi = mid - 1               # -1 !
    return -1

# Вариант 2: полуоткрытый [lo, hi), условие lo < hi — обобщается на "первый >= x"
def lower_bound(arr, target):
    lo, hi = 0, len(arr)               # hi = len, НЕ len-1
    while lo < hi:                     # строго <
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid                   # БЕЗ -1
    return lo                          # первая позиция >= target

Правила без багов:

1. Чётко зафиксируйте инвариант интервала (закрытый [lo, hi] или полуоткрытый [lo, hi)) и держитесь его.
2. Условие цикла и обновление границ должны соответствовать инварианту.
3. mid = lo + (hi - lo) // 2 избегает переполнения (важно в C/Java).
4. Убедитесь, что интервал уменьшается на каждой итерации, иначе бесконечный цикл.

⚠️ Ловушка: бесконечный цикл, если hi = mid при условии lo <= hi — границы перестают сходиться. На практике используйте bisect из стандартной библиотеки вместо ручной реализации. Самые частые баги: < vs <=, забытый +1/-1, неверный mid.

Короткий ответ: Рекурсия — функция, вызывающая саму себя. Нужны база (условие останова) и рекурсивный шаг (сведение к меньшей задаче). Каждый вызов кладёт фрейм в стек вызовов — слишком глубокая рекурсия переполняет стек.

Подробно:

def factorial(n):
    if n <= 1:               # БАЗА — без неё бесконечная рекурсия
        return 1
    return n * factorial(n - 1)   # ШАГ — задача меньше

# Стек вызовов растёт: factorial(3) -> factorial(2) -> factorial(1)
# Глубина = n -> память O(n) на стек

import sys
sys.setrecursionlimit(10000)      # дефолт ~1000, поднимаем при глубокой рекурсии

Каждый рекурсивный вызов сохраняет в стеке свои локальные переменные и точку возврата. Глубина рекурсии = высота стека = O(глубины) памяти.

Рекурсия vs итерация: рекурсия часто читаемее для древовидных/делимых задач (деревья, divide&conquer), но итерация эффективнее по памяти (нет фреймов) и не переполняет стек. Любую рекурсию можно переписать в цикл с явным стеком.

⚠️ Ловушка: забытая или недостижимая база → RecursionError: maximum recursion depth exceeded. Python лимит ~1000 фреймов. Для глубоких структур (длинный связный список, глубокое дерево) предпочитайте итеративный подход с явным стеком.

Короткий ответ: Хвостовая рекурсия — когда рекурсивный вызов является последней операцией функции. Некоторые языки оптимизируют её в цикл (TCO), но Python намеренно этого не делает — каждый вызов всё равно создаёт фрейм.

Подробно:

# Хвостовая форма: рекурсивный вызов — последнее действие
def fact_tail(n, acc=1):
    if n <= 1:
        return acc
    return fact_tail(n - 1, acc * n)   # ничего после вызова

# В Python это всё равно O(n) памяти на стек и упадёт на больших n!
# fact_tail(100000) -> RecursionError

Гвидо ван Россум сознательно отказался от TCO в Python по причинам:

1. Читаемость трассировок: при TCO теряются промежуточные фреймы в traceback, отладка усложняется.
2. Философия: Python предпочитает явные циклы рекурсии («плоское лучше вложенного»).
3. Это потребовало бы усложнения и неоднозначности (что именно считать хвостовым вызовом).

Поэтому в Python хвостовую рекурсию переписывают в обычный цикл:

def fact_iter(n):
    acc = 1
    for i in range(2, n + 1):
        acc *= i
    return acc          # O(1) памяти, без лимита стека

⚠️ Ловушка: не полагайтесь на хвостовую рекурсию в Python для глубоких вычислений — она не оптимизируется и упрётся в лимит стека. В Scheme/Scala/Haskell — оптимизируется, в Python и Java — нет.

Короткий ответ: DP решает задачи с перекрывающимися подзадачами и оптимальной подструктурой, кешируя результаты. Мемоизация — top-down (рекурсия + кеш), табуляция — bottom-up (заполнение таблицы итеративно).

Подробно:

Признаки применимости DP: (1) перекрывающиеся подзадачи (одни и те же подзадачи решаются многократно), (2) оптимальная подструктура (решение строится из решений подзадач).

# Наивный Фибоначчи: O(2^n) — пересчитывает одно и то же
def fib_slow(n):
    return n if n < 2 else fib_slow(n-1) + fib_slow(n-2)

# МЕМОИЗАЦИЯ (top-down): рекурсия + кеш -> O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n-1) + fib_memo(n-2)

# ТАБУЛЯЦИЯ (bottom-up): заполняем таблицу -> O(n) время, O(1) память
def fib_tab(n):
    if n < 2: return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Классические задачи:

• Рюкзак (knapsack): максимизировать ценность при ограничении веса, O(n*W).
• LCS (longest common subsequence): длиннейшая общая подпоследовательность, O(n*m).
• Лестница/монеты/edit distance — все на DP.

# 0/1 рюкзак: dp[w] = макс ценность при вместимости w
def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):   # обратный порядок!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

Мемоизация vs табуляция: мемоизация естественнее (просто добавь кеш к рекурсии), вычисляет только нужные подзадачи, но рискует переполнить стек. Табуляция без рекурсии, часто экономнее по памяти (можно хранить только последние строки), но вычисляет все подзадачи.

⚠️ Ловушка: DP применим только при перекрывающихся подзадачах — если их нет (merge sort), это просто divide&conquer, кеш не поможет. В рюкзаке порядок обхода веса (обратный для 0/1, прямой для unbounded) критичен.

Короткий ответ: Жадный алгоритм на каждом шаге делает локально оптимальный выбор, не пересматривая его. DP перебирает варианты и комбинирует подзадачи. Greedy быстрее, но корректен лишь при свойстве жадного выбора.

Подробно:

# Greedy: размен монетами (работает для "канонических" систем)
def coin_change_greedy(amount, coins=[25, 10, 5, 1]):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c          # берём как можно больше крупных
        amount %= c
    return count
# Для [25,10,5,1] greedy верен. Для [1,3,4] и amount=6:
# greedy -> 4+1+1 = 3 монеты, но оптимум 3+3 = 2 монеты -> нужен DP!

• Greedy корректен, когда задача обладает свойством жадного выбора (локальный оптимум ведёт к глобальному) и оптимальной подструктурой. Примеры: задача о выборе заявок (activity selection), кодирование Хаффмана, MST (Краскал/Прим), Дейкстра.
• DP нужен, когда жадность ошибается — приходится рассматривать комбинации подзадач (как в размене [1,3,4] выше).

Greedy обычно O(n log n) (часто из-за сортировки), DP — O(n*k) и больше. Greedy проще и быстрее, но требует доказательства корректности.

⚠️ Ловушка: жадность кажется правильной, но часто даёт неоптимальный ответ. Всегда проверяйте контрпримером или докажите свойство жадного выбора. Если greedy не доказывается — берите DP.

Короткий ответ: Два указателя — два индекса, движущиеся по массиву (с разных концов или с разной скоростью), снижают O(n²) до O(n). Скользящее окно — частный случай для подотрезков.

Подробно:

# ДВА УКАЗАТЕЛЯ: пара с заданной суммой в ОТСОРТИРОВАННОМ массиве -> O(n)
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1            # нужно больше -> двигаем левый
        else:
            hi -= 1            # нужно меньше -> двигаем правый
    return None

# СКОЛЬЗЯЩЕЕ ОКНО: длиннейшая подстрока без повторов -> O(n)
def longest_unique(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1      # сжимаем окно слева
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

# Окно фиксированного размера k: сумма подмассива -> O(n)
def max_sum_window(arr, k):
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]    # добавили новый, убрали старый
        best = max(best, window)
    return best

Паттерны: два указателя — для отсортированных массивов, пар, разворотов, удаления дубликатов на месте. Скользящее окно — для подотрезков/подстрок с условием (макс сумма, без повторов, минимальное окно).

⚠️ Ловушка: для two sum через два указателя массив должен быть отсортирован (иначе используйте хеш-таблицу, см. ниже). В скользящем окне следите за корректным сжатием левой границы — частая ошибка: не двигать left, когда условие нарушено.

Короткий ответ: Хеш-таблица позволяет за O(1) проверять «видели ли мы нужное число». Классика — two sum: для каждого элемента ищем дополнение target - x в множестве уже виденных за O(n).

Подробно:

# Two Sum на НЕотсортированном массиве -> O(n) время, O(n) память
def two_sum(nums, target):
    seen = {}                          # значение -> индекс
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:         # O(1) проверка!
            return (seen[complement], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)

Идея универсальна: вместо вложенного цикла O(n²) мы за один проход запоминаем виденное в хеш-таблице и проверяем условие за O(1). Применяется в: поиске дубликатов, подсчёте частот, группировке (анаграммы), кешировании.

⚠️ Ловушка: хеш-решение тратит O(n) памяти — это time-space tradeoff против O(1)-памяти решения двумя указателями (но то требует сортировки O(n log n)). Выбор зависит от того, отсортированы ли данные и важна ли память.

Короткий ответ: Backtracking — систематический перебор с возвратом: строим решение по шагам, и если текущий путь не ведёт к решению — откатываемся и пробуем другой. Применяется для комбинаторных задач.

Подробно:

# Все перестановки -> O(n!)
def permutations(nums):
    res = []
    def backtrack(path, remaining):
        if not remaining:
            res.append(path[:])        # нашли полное решение
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # выбор
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()                             # ОТКАТ (backtrack)
    backtrack([], nums)
    return res

# Подмножества -> O(2^n)
def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

Применения: перестановки/комбинации/подмножества, N ферзей, судоку, генерация скобок, поиск пути в лабиринте. Часто ускоряется отсечением (pruning) — отбрасываем заведомо тупиковые ветки рано.

⚠️ Ловушка: backtracking экспоненциален (O(2^n), O(n!)) — годится только для небольших n. Обязательно делайте откат (path.pop()) симметрично выбору, иначе состояние «потечёт» между ветками. Добавляйте отсечения, чтобы не перебирать всё.

Короткий ответ: Понять → примеры → brute force → оптимизация → код → тесты (UEBOCT). Не бросайтесь писать код сразу — проговорите подход вслух.

Подробно:

1. Understand (понять): уточните вход/выход, ограничения (n, диапазоны, дубликаты, отсортированность), краевые случаи. Переформулируйте задачу своими словами.
2. Examples (примеры): разберите 1-2 примера руками, включая краевые (пустой вход, один элемент, отрицательные).
3. Brute force: опишите наивное решение и его сложность — это показывает понимание и даёт «нижнюю планку».
4. Optimize: ищите узкое место. Подумайте о структурах данных (хеш для O(1) поиска, куча для top-k, два указателя/окно) и паттернах. Озвучьте tradeoffs.
5. Code: пишите чисто, осмысленные имена, маленькими шагами.
6. Test: прогоните на примерах и краевых случаях, проверьте off-by-one.

Подсказки по выбору метода: «отсортированный массив» → бинарный поиск / два указателя; «подотрезок/подстрока» → скользящее окно; «пара/дополнение/частота» → хеш-таблица; «top K / приоритет» → куча; «все варианты/перестановки» → backtracking; «оптимум с подзадачами» → DP.

⚠️ Ловушка: молчаливое кодирование — антипаттерн на собесе. Думайте вслух, проговаривайте варианты и компромиссы. И всегда уточняйте ограничения до кода — они подсказывают целевую сложность (n ≤ 20 → можно экспоненту; n ≤ 10^6 → нужно O(n)/O(n log n)).

Короткий ответ: Строки/списки разворачиваются срезом [::-1] (O(n)) или двумя указателями на месте. Связный список — переразвешиванием указателей next.

Подробно:

# Строка (неизменяема -> новый объект)
s = "hello"
s[::-1]                       # "olleh", O(n) время и память

# Список на месте двумя указателями -> O(1) доп. памяти
def reverse_inplace(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1; hi -= 1
    return arr

# Разворот связного списка -> O(n)
def reverse_linked_list(head):
    prev = None
    while head:
        nxt = head.next       # сохранить следующий
        head.next = prev      # развернуть указатель
        prev = head           # сдвинуть prev
        head = nxt            # сдвинуть head
    return prev               # новая голова

⚠️ Ловушка: в развороте связного списка обязательно сохраняйте next до переприсваивания, иначе потеряете остаток списка. Срез [::-1] прост, но создаёт копию (O(n) памяти) — для разворота на месте нужны два указателя.

Короткий ответ: Дубликаты ищутся через set за O(n). Анаграммы проверяются сортировкой (O(n log n)) или подсчётом частот символов (O(n)).

Подробно:

# Есть ли дубликат -> O(n) время, O(n) память
def has_duplicate(arr):
    return len(set(arr)) != len(arr)

# Анаграммы: сортировка -> O(n log n)
def is_anagram_sort(a, b):
    return sorted(a) == sorted(b)

# Анаграммы: подсчёт частот -> O(n)
from collections import Counter
def is_anagram(a, b):
    return Counter(a) == Counter(b)

# Группировка анаграмм -> O(n * k log k)
def group_anagrams(words):
    groups = {}
    for w in words:
        key = "".join(sorted(w))        # ключ — отсортированные буквы
        groups.setdefault(key, []).append(w)
    return list(groups.values())

⚠️ Ловушка: для анаграмм через подсчёт Counter — O(n), против сортировки O(n log n). Уточните: учитывать ли регистр, пробелы, юникод. Counter(a) == Counter(b) — самый чистый способ в Python.

Короткий ответ: Вывести числа 1..n, заменяя кратные 3 на «Fizz», кратные 5 на «Buzz», кратные 15 на «FizzBuzz». Классическая проверка базовой логики.

Подробно:

def fizzbuzz(n):
    for i in range(1, n + 1):
        if i % 15 == 0:          # 15 ПЕРВЫМ (кратно и 3, и 5)
            print("FizzBuzz")
        elif i % 3 == 0:
            print("Fizz")
        elif i % 5 == 0:
            print("Buzz")
        else:
            print(i)

# Альтернатива через конкатенацию (расширяемо)
def fizzbuzz2(n):
    for i in range(1, n + 1):
        out = ("Fizz" if i % 3 == 0 else "") + ("Buzz" if i % 5 == 0 else "")
        print(out or i)

O(n) время.

⚠️ Ловушка: проверять % 15 (или оба условия вместе) до отдельных % 3 и % 5 — иначе кратные 15 выведутся как «Fizz». Это главный отсев FizzBuzz.

Короткий ответ: Используем стек: при открывающей скобке кладём её, при закрывающей проверяем верх стека. В конце стек должен быть пуст. O(n).

Подробно:

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)                 # открывающая -> в стек
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False                 # нет пары или не совпала
    return not stack                         # пусто -> всё закрыто

is_valid("()[]{}")     # True
is_valid("([)]")       # False — неверная вложенность
is_valid("(")          # False — остался незакрытый

O(n) время, O(n) память (стек).

⚠️ Ловушка: не забудьте проверить, что стек пуст в конце (( → остался незакрытым) и что стек не пуст перед pop () без открывающей). Оба краевых случая часто упускают.

Короткий ответ: Алгоритм Флойда («черепаха и заяц») использует два указателя с разной скоростью. Если есть цикл, быстрый догонит медленного. O(n) время, O(1) память.

Подробно:

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # на 1 шаг
        fast = fast.next.next       # на 2 шага
        if slow is fast:            # встретились -> цикл
            return True
    return False                    # fast дошёл до конца -> цикла нет

# Найти НАЧАЛО цикла
def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None
    slow = head                     # один указатель в начало
    while slow is not fast:         # двигаем оба по 1 шагу
        slow, fast = slow.next, fast.next
    return slow                     # точка входа в цикл

Почему работает: если есть цикл, быстрый указатель «нагоняет» медленного на 1 узел за итерацию и неизбежно совпадёт. Альтернатива — set посещённых узлов (O(n) память), но Флойд элегантнее (O(1)).

⚠️ Ловушка: проверяйте fast and fast.next перед fast.next.next — иначе AttributeError на конце списка. Сравнивайте узлы по is (идентичность), а не == (значения могут совпадать у разных узлов).

Короткий ответ: Когда n гарантированно мало (например, ≤ 1000-5000), когда код выполняется редко, или когда простота важнее производительности и нет узкого места.

Подробно:

O(n²) выполняет ~n² операций. Грубый ориентир (при ~10^8 простых операций в секунду):

• n = 100 → 10 000 операций — мгновенно.
• n = 1 000 → 10^6 — доли миллисекунды.
• n = 10 000 → 10^8 — около секунды, граница приемлемого.
• n = 100 000 → 10^10 — десятки секунд, уже неприемлемо.

O(n²) оправдан когда:

• размер входа жёстко ограничен сверху и мал;
• алгоритм проще и читаемее, чем оптимальный (поддерживаемость > микросекунды);
• это не горячий путь (запускается раз в день, а не в цикле на запрос);
• константы у O(n²)-решения настолько малы, что на реальных n оно быстрее «умного».

⚠️ Ловушка: скрытый O(n²). Классика — x in list внутри цикла по списку, или конкатенация строк в цикле (s += ... создаёт новую строку каждый раз → O(n²); используйте "".join(...)). Эти ловушки незаметны на тестах и взрываются на проде. Всегда уточняйте ограничения на n, прежде чем соглашаться на O(n²).

Выбор определяется не названием структуры, а требуемым порядком исследования. Линейный поиск работает в любых данных; бинарный требует сортировки и каждый раз отбрасывает половину диапазона. BFS использует очередь и находит кратчайшее число рёбер в невзвешенном графе, DFS использует стек/рекурсию и удобен для компонент связности, циклов и топологического обхода.

BFS: start ─► весь слой 1 ─► весь слой 2 ─► ...
DFS: start ─► идём вглубь ─► тупик ─► backtrack

⚠️ В графе всегда храните visited: без него цикл заставит обход повторять вершины бесконечно. Для Дейкстры отрицательное ребро нарушает жадное доказательство; тогда нужен Bellman–Ford или другой подход.