⏱️ Big O Breakdown

copy vs deepcopy. Где прячется скрытая мутация

Какой результат выведет код?

import copy

original = [[1, 2], [3, 4]]
shallow = copy.copy(original)

shallow[0][0] = 99

print(original)
print(shallow)

Варианты:
А) [[1, 2], [3, 4]] и [[99, 2], [3, 4]]
Б) [[99, 2], [3, 4]] и [[99, 2], [3, 4]]
В) [[1, 2], [3, 4]] и [[1, 2], [3, 4]]
Г) ошибка

Ответ: Б) Оба изменились

Поверхностная копия создаёт новый список — но вложенные объекты не копирует, а копирует ссылки на них.

original → [ref_a, ref_b]
shallow  → [ref_a, ref_b]  ← те же ссылки!

shallow[0][0] = 99
→ меняем объект по ref_a
→ original[0] тоже видит изменение

Фикс — глубокая копия:

deep = copy.deepcopy(original)

deep[0][0] = 99

print(original)  # [[1, 2], [3, 4]] — не изменился
print(deep)      # [[99, 2], [3, 4]]

deepcopy рекурсивно копирует все вложенные объекты. Полная независимость.

Цена deepcopy:

import timeit

timeit.timeit("copy.copy(data)", setup="import copy; data = [[1,2]]*1000", number=10000)
# ~0.05 сек

timeit.timeit("copy.deepcopy(data)", setup="import copy; data = [[1,2]]*1000", number=10000)
# ~2.5 сек — в 50 раз медленнее

deepcopy дорогой. Используй только когда реально нужна полная независимость.

Когда что:

copy.copy()      # плоские структуры — списки чисел, строк
copy.deepcopy()  # вложенные структуры — списки списков, словари словарей
lst[:]           # быстрая поверхностная копия списка без импорта

🐍Вопросы с собесов -> ProstoPython

🧩 Code Cleanup

Используй property вместо геттеров и сеттеров

Привычка из Java — писать геттеры и сеттеры явно:

class User:
    def __init__(self, name):
        self._name = name

    def get_name(self):
        return self._name

    def set_name(self, value):
        self._name = value

user = User("alice")
user.set_name("bob")
print(user.get_name())

В Python это антипаттерн. Код многословный, непитоничный.

После:

class User:
    def __init__(self, name):
        self._name = name

    @property
    def name(self):
        return self._name

    @name.setter
    def name(self, value):
        if not value:
            raise ValueError("Имя не может быть пустым")
        self._name = value

user = User("alice")
user.name = "bob"
print(user.name)

Обращаемся как к атрибуту — но под капотом работает логика.

Главный плюс — можно добавить логику позже:

Начал с простого атрибута:

class User:
    def __init__(self, name):
        self.name = name

Понадобилась валидация — добавил property без изменения интерфейса. Все кто писал "user.name" — ничего не заметят.

В Java пришлось бы сразу писать геттеры — иначе потом сломаешь API.

Только для чтения:

class Circle:
    def __init__(self, radius):
        self.radius = radius

    @property
    def area(self):
        return 3.14 * self.radius ** 2

c = Circle(5)
print(c.area)   # 78.5
c.area = 100    # AttributeError — нет сеттера

🐍Вопросы с собесов -> ProstoPython

📈 FROM O(...) TO O(...)

Подмассив с максимальной суммой: алгоритм Кадане

Задача: найти подмассив с максимальной суммой.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Ответ: 6 (подмассив [4, -1, 2, 1])

Наивное решение:

def max_subarray(nums):
    max_sum = float("-inf")
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            max_sum = max(max_sum, sum(nums[i:j+1]))
    return max_sum

Два цикла + sum внутри. O(n³) время.

С предвычисленными суммами можно до O(n²) — но это всё равно медленно.

Алгоритм Кадане — O(n):

def max_subarray(nums):
    max_sum = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)
    return max_sum

Один проход. Две переменные.

Идея:

На каждом шаге выбираем — продолжать текущий подмассив или начать новый с текущего элемента.

current = max(num, current + num)

Если current стал отрицательным — он только тянет вниз. Выгоднее начать заново с num.

nums:    -2   1  -3   4  -1   2   1  -5   4
current: -2   1  -2   4   3   5   6   1   5
max_sum: -2   1   1   4   4   5   6   6   6

От O(n³) до O(n) — смена подхода целиком.

Не перебираем все подмассивы. Спрашиваем на каждом шаге: стоит ли продолжать?

🐍Вопросы с собесов -> ProstoPython

🧠 Interview Thinking

Найди все уникальные пути в матрице

Задача: из левого верхнего угла в правый нижний. Двигаться можно только вправо или вниз. Сколько уникальных путей?

# Матрица 3x3
# S . .
# . . .
# . . E

# Ответ: 6

Как думает junior:

Рекурсия — перебрать все пути:

def count_paths(m, n):
    if m == 1 or n == 1:
        return 1
    return count_paths(m-1, n) + count_paths(n-1, m)

Много повторных вычислений. O(2^(m+n)) — экспоненциально.

Как думает strong middle:

Каждая клетка — сумма путей сверху и слева. Считаем снизу вверх.

def count_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

O(m·n) время, O(m·n) память.

Визуализация для 3x3:

1  1  1
1  2  3
1  3  6

Первая строка и столбец — всегда 1: путь только один — прямо или вниз. Каждая остальная клетка — сумма соседей сверху и слева.

Оптимизация по памяти до O(n):

def count_paths(m, n):
    row = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

Не храним всю матрицу — только одну строку.

Что хочет услышать интервьюер:

1. Назвал рекурсию и её проблему — повторные вычисления
2. Предложил DP — объяснил почему dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. Сам предложил оптимизацию по памяти
4. Проверил edge cases

count_paths(1, 1)  # 1 — уже на месте
count_paths(1, n)  # 1 — только прямо

🐍Вопросы с собесов -> ProstoPython

⏱️ Big O Breakdown

LRU Cache: что происходит когда кеш переполнен

Какова сложность операций get и put в LRU кеше?

from functools import lru_cache

@lru_cache(maxsize=3)
def heavy_compute(n):
    return n ** 2

heavy_compute(1)
heavy_compute(2)
heavy_compute(3)
heavy_compute(4)  # кеш переполнен — что вытесняется?
heavy_compute(1)  # попадёт в кеш или нет?

Варианты:
А) get O(1), put O(1) — вытесняется случайный элемент
Б) get O(n), put O(n) — вытесняется самый старый
В) get O(1), put O(1) — вытесняется давно не использованный
Г) get O(log n), put O(log n)

Ответ: В) get O(1), put O(1) — вытесняется давно не использованный

LRU — Least Recently Used. При переполнении вылетает тот элемент, к которому дольше всего не обращались.

Добавляем 1, 2, 3 → кеш: [1, 2, 3]
Добавляем 4       → вытесняем 1 (давно не использован)
                  → кеш: [2, 3, 4]
Запрашиваем 1     → промах, считаем заново
                  → вытесняем 2
                  → кеш: [3, 4, 1]

Как достигается O(1):

Под капотом — хеш-таблица + двусвязный список. Хеш-таблица даёт O(1) доступ, список отслеживает порядок использования.

# Реализация вручную через OrderedDict
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

move_to_end — O(1). popitem — O(1). Всё работает за константное время.

🐍Вопросы с собесов -> ProstoPython

🧩 Code Cleanup

Генераторы вместо списков — когда не нужно всё сразу

Типичный код:

def get_even_squares(nums):
    result = []
    for n in nums:
        if n % 2 == 0:
            result.append(n ** 2)
    return result

squares = get_even_squares(range(1_000_000))
for sq in squares:
    print(sq)

Создаём весь список в памяти — только чтобы сразу же итерироваться по нему.

После:

def get_even_squares(nums):
    for n in nums:
        if n % 2 == 0:
            yield n ** 2

squares = get_even_squares(range(1_000_000))
for sq in squares:
    print(sq)

Память — O(1). Значения вычисляются по одному, только когда нужны.

Или через выражение-генератор:

squares = (n ** 2 for n in range(1_000_000) if n % 2 == 0)

Одна строка, никакого списка в памяти.

Когда список всё же нужен:

# Нужен random access
squares = list(get_even_squares(nums))
print(squares[42])

# Нужно пройти несколько раз
squares = list(get_even_squares(nums))
for sq in squares: ...
for sq in squares: ...  # генератор был бы уже исчерпан

Сигнал что нужен генератор:

Функция возвращает список — и его сразу итерируют. Никто не обращается по индексу, никто не проходит дважды.

🐍Вопросы с собесов -> ProstoPython

📈 FROM O(...) TO O(...)

Подсчёт островов: от рекурсии к BFS

Задача: дана матрица из 0 и 1. Найти количество островов — связных групп единиц.

grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"],
]
# Ответ: 3

Наивное решение — рекурсивный DFS:

def num_islands(grid):
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == "1":
                dfs(grid, i, j)
                count += 1
    return count

def dfs(grid, i, j):
    if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
        return
    if grid[i][j] != "1":
        return
    grid[i][j] = "0"
    dfs(grid, i+1, j)
    dfs(grid, i-1, j)
    dfs(grid, i, j+1)
    dfs(grid, i, j-1)

O(m·n) время — но рекурсия накапливает стек вызовов. На большой матрице — RecursionError.

Итеративный BFS — O(m·n) время, O(min(m,n)) память:

from collections import deque

def num_islands(grid):
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == "1":
                bfs(grid, i, j)
                count += 1
    return count

def bfs(grid, i, j):
    queue = deque([(i, j)])
    grid[i][j] = "0"
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == "1":
                grid[nr][nc] = "0"
                queue.append((nr, nc))

Никакой рекурсии — явная очередь. Стек не растёт.

🐍Вопросы с собесов -> ProstoPython

⏱️ Big O Breakdown

GIL: почему потоки в Python не всегда ускоряют код

Какой код выполнится быстрее на многоядерном процессоре?

import threading

def count(n):
    while n > 0:
        n -= 1

# Вариант 1 — один поток
count(100_000_000)

# Вариант 2 — два потока
t1 = threading.Thread(target=count, args=(50_000_000,))
t2 = threading.Thread(target=count, args=(50_000_000,))
t1.start(); t2.start()
t1.join(); t2.join()

Варианты:
А) Вариант 2 в два раза быстрее
Б) Примерно одинаково или вариант 2 медленнее
В) Вариант 1 всегда быстрее
Г) Зависит от операционной системы

Ответ: Б) Примерно одинаково или вариант 2 медленнее

Причина — GIL. Global Interpreter Lock.

CPython не позволяет двум потокам одновременно выполнять Python-байткод. В каждый момент времени только один поток держит GIL. Второй ждёт.

Поток 1: [==GIL==]        [==GIL==]
Поток 2:         [==GIL==]         [==GIL==]
Ядро 1:  работает  пауза   работает   пауза
Ядро 2:  пауза   работает   пауза   работает

Два ядра есть — но используется только одно в каждый момент. Плюс накладные расходы на переключение контекста.

Когда потоки всё же помогают:

# I/O-bound задачи — сетевые запросы, файлы
# Пока один поток ждёт ответа — GIL отпускается
import requests
import threading

urls = [...]
threads = [threading.Thread(target=requests.get, args=(url,)) for url in urls]

Во время ожидания I/O GIL освобождается — другой поток может работать. Здесь многопоточность реально ускоряет.

Для CPU-bound задач — multiprocessing:

from multiprocessing import Process

# Каждый процесс имеет свой GIL
p1 = Process(target=count, args=(50_000_000,))
p2 = Process(target=count, args=(50_000_000,))

Разные процессы — разные интерпретаторы — разные GIL. Реальный параллелизм.

🐍Вопросы с собесов -> ProstoPython

git stash — команда для временного сохранения незакоммиченных изменений.

Что делает

🔹 убирает изменения из рабочего каталога
🔹 сохраняет их во внутреннем стеке (stash)
🔹 позволяет переключить ветку или обновить код

Когда использовать

🔹 нужно быстро переключиться на другую задачу
🔹 изменения ещё не готовы к коммиту

🐍Вопросы с собесов -> ProstoPython

⏱️ Big O Breakdown

Поиск в словаре по вложенным ключам. Где прячется KeyError

Какова сложность и что выведет код?

data = {
    "users": {
        "alice": {
            "age": 30
        }
    }
}

print(data["users"]["bob"]["age"])
print(data.get("users").get("bob").get("age"))

Варианты:
А) Оба выведут None
Б) Первый — KeyError, второй — None
В) Первый — KeyError, второй — AttributeError
Г) Оба бросят исключение

Ответ: В) Первый — KeyError, второй — AttributeError

Первый падает сразу — ключа "bob" нет.

Второй падает тоже — но по другой причине:

data.get("users")          # {"alice": {...}}
    .get("bob")            # None — ключа нет
    .get("age")            # AttributeError: None не имеет метода get

Цепочка get() не защищает от None в середине.

Правильные варианты:

# Вариант 1 — явная проверка
user = data.get("users", {}).get("bob", {}).get("age")
print(user)  # None — безопасно

# Вариант 2 — try/except
try:
    age = data["users"]["bob"]["age"]
except KeyError:
    age = None

# Вариант 3 — если структура глубокая, используй reduce
from functools import reduce

def deep_get(d, *keys):
    return reduce(lambda x, k: x.get(k, {}) if isinstance(x, dict) else {}, keys, d)

deep_get(data, "users", "bob", "age")  # {}

Сложность каждого обращения:

Каждый get или [] — O(1). Цепочка из n ключей — O(n) где n количество уровней вложенности, не размер словаря.

🐍Вопросы с собесов -> ProstoPython

🧩 Code Cleanup

Избавься от вложенных условий через ранний выход

Типичный код:

def process_order(order):
    if order:
        if order.is_paid():
            if order.items:
                if order.user.is_active():
                    ship(order)
                else:
                    raise UserInactiveError()
            else:
                raise EmptyOrderError()
        else:
            raise PaymentError()
    else:
        raise OrderNotFoundError()

Пирамида вложенности. Чтобы понять что происходит в центре — нужно держать в голове все условия снаружи.

После — инвертируй условия, выходи раньше:

def process_order(order):
    if not order:
        raise OrderNotFoundError()
    if not order.is_paid():
        raise PaymentError()
    if not order.items:
        raise EmptyOrderError()
    if not order.user.is_active():
        raise UserInactiveError()

    ship(order)

Та же логика — но читается сверху вниз. Каждая проверка независима. Основной сценарий — в самом конце, без вложенности.

Правило:

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

Это называется guard clauses — охранные условия.

Ещё пример — возврат значения:

# До
def get_discount(user):
    if user:
        if user.is_premium():
            return 0.3
        else:
            return 0.1
    else:
        return 0

# После
def get_discount(user):
    if not user:
        return 0
    if user.is_premium():
        return 0.3
    return 0.1

🐍Вопросы с собесов -> ProstoPython

❌ Rookie Mistakes

Не игнорируй типы возвращаемых значений

Частая ошибка — не проверять что возвращает функция:

nums = [3, 1, 2]
sorted_nums = nums.sort()
print(sorted_nums)  # None

list.sort() сортирует на месте и возвращает None. Многие ожидают отсортированный список.

Ещё примеры методов которые возвращают None:

result = my_list.append(5)     # None
result = my_list.reverse()     # None
result = my_dict.update({})    # None
result = my_set.add(1)         # None

Все методы которые мутируют объект — возвращают None. Это соглашение Python: либо мутируешь, либо возвращаешь новое.

Ловушка в цепочках:

# Пытаемся отсортировать и взять первый элемент
first = [3, 1, 2].sort()[0]  # TypeError: NoneType не поддерживает индексы

Правильно:

nums = [3, 1, 2]
nums.sort()
first = nums[0]  # 1

# Или через sorted() если нужен новый список
first = sorted(nums)[0]

Как не попасться:

Методы без возвращаемого значения в документации помечены как "-> None". Мутирующие методы никогда не возвращают результат.

Простое правило — если метод изменяет объект, он возвращает None. Если создаёт новый — возвращает его.

sorted(nums)      # создаёт новый → возвращает список
nums.sort()       # мутирует → возвращает None

"hello".upper()   # создаёт новую строку → возвращает строку

🐍Вопросы с собесов -> ProstoPython

Попробуйте ответить без запуска, что выведет код, разбор будет через 2 часа

🐍Вопросы с собесов -> ProstoPython

🧠 ЧТО ВЫВЕДЕТ КОД

Изменяемый аргумент по умолчанию. Ловушка которую все знают но все равно попадаются

def add_item(item, items=[]):
    items.append(item)
    return items

print(add_item("a"))
print(add_item("b"))
print(add_item("c"))

Варианты:
А) ["a"], ["b"], ["c"]
Б) ["a"], ["a", "b"], ["a", "b", "c"]
В) ["a"], ["b"], ["a", "b", "c"]
Г) ошибка

Ответ: Б) ["a"], ["a", "b"], ["a", "b", "c"]

Дефолтный аргумент создаётся один раз — при определении функции, а не при каждом вызове. Все вызовы без явного items делят один и тот же список.

print(add_item.__defaults__)  # (['a', 'b', 'c'],) — список живёт здесь

Ловушка:

Выглядит как "каждый раз новый список". На самом деле — один объект на все вызовы.

Фикс:

def add_item(item, items=None):
    if items is None:
        items = []
    items.append(item)
    return items

print(add_item("a"))  # ["a"]
print(add_item("b"))  # ["b"]
print(add_item("c"))  # ["c"]

None — иммутабельный. Каждый раз создаём новый список внутри функции.

То же самое с dict и set:

def add_tag(key, value, tags={}):  # та же ловушка
    tags[key] = value
    return tags

Любой мутабельный объект как дефолт — потенциальный баг.

🐍Вопросы с собесов -> ProstoPython

📈 FROM O(...) TO O(...)

Число перестановок: от рекурсии к итерации

Задача: сгенерировать все перестановки списка.

nums = [1, 2, 3]
# Ответ: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Наивное решение — рекурсия:

def permutations(nums):
    if len(nums) <= 1:
        return [nums[:]]
    result = []
    for i in range(len(nums)):
        rest = nums[:i] + nums[i+1:]
        for p in permutations(rest):
            result.append([nums[i]] + p)
    return result

O(n!) время — не избежать, перестановок именно столько. Но O(n!) памяти — храним все результаты сразу. На n=10 это 3 628 800 списков.

Генератор — O(n) дополнительной памяти:

from itertools import permutations

for p in permutations([1, 2, 3]):
    process(p)

Стандартная библиотека генерирует перестановки лениво — по одной. Не строит весь список в памяти.

Если нужна своя реализация — алгоритм Хипа:

def permutations(nums):
    def generate(k, arr):
        if k == 1:
            yield arr[:]
            return
        yield from generate(k-1, arr)
        for i in range(k-1):
            if k % 2 == 0:
                arr[i], arr[k-1] = arr[k-1], arr[i]
            else:
                arr[0], arr[k-1] = arr[k-1], arr[0]
            yield from generate(k-1, arr)

    yield from generate(len(nums), nums[:])

print(list(permutations([1, 2, 3])))

Генератор — каждая перестановка вычисляется только когда нужна.

Сравнение:

рекурсия с result[]  → O(n!) память — всё в RAM сразу
генератор            → O(n) память — одна перестановка за раз

🐍Вопросы с собесов -> ProstoPython

🧩 Code Cleanup

Используй ABC чтобы объявить контракт явно

Типичная ситуация — базовый класс который нужно наследовать:

class Animal:
    def speak(self):
        raise NotImplementedError

class Dog(Animal):
    def speak(self):
        return "woof"

class Cat(Animal):
    pass  # забыли реализовать speak

Ошибка проявится только в рантайме — когда вызовем cat.speak(). До этого момента Cat выглядит валидным классом.

После — ABC:

from abc import ABC, abstractmethod

class Animal(ABC):
    @abstractmethod
    def speak(self):
        pass

class Dog(Animal):
    def speak(self):
        return "woof"

class Cat(Animal):
    pass  # не реализовали speak

cat = Cat()  # TypeError прямо здесь — до любого вызова

Ошибка при создании объекта — не при вызове метода. Намного раньше и понятнее.

Несколько абстрактных методов:

class DataProcessor(ABC):
    @abstractmethod
    def load(self, path):
        pass

    @abstractmethod
    def process(self, data):
        pass

    @abstractmethod
    def save(self, result, path):
        pass

Любой наследник обязан реализовать все три. Это контракт — явный и проверяемый.

Можно миксовать с обычными методами:

class Animal(ABC):
    @abstractmethod
    def speak(self):
        pass

    def describe(self):
        return f"Я говорю: {self.speak()}"

describe — обычный метод с реализацией. speak — обязателен для наследника.

🐍Вопросы с собесов -> ProstoPython

⏱️ Big O Breakdown

Trie: поиск строк за O(m) вместо O(n·m)

Задача: есть словарь из n слов. Нужно проверять — есть ли слово в словаре, и находить все слова с заданным префиксом.

words = ["apple", "app", "application", "apply", "banana"]

# Есть ли "app"?
# Все слова с префиксом "app"?

Какова сложность для каждого подхода?

# Вариант 1 — список
"app" in words                          # поиск слова
[w for w in words if w.startswith("app")]  # поиск по префиксу

# Вариант 2 — Trie
trie.search("app")
trie.starts_with("app")

Варианты:
А) Оба O(m) где m — длина слова
Б) Список — O(n·m), Trie — O(m)
В) Список — O(n), Trie — O(m·n)
Г) Оба O(n)

Ответ: Б) Список — O(n·m), Trie — O(m)

Список перебирает все n слов, сравнивая каждое символ за символом — O(n·m).

Trie идёт по символам запроса — ровно m шагов. Размер словаря не важен.

Реализация:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

Визуализация для ["app", "apple"]:

root
└── a
    └── p
        └── p [end]
            └── l
                └── e [end]

Общий префикс хранится один раз.

Цена — память:

O(n·m) — каждый символ каждого слова. При большом словаре с короткими общими префиксами — дорого.

🐍Вопросы с собесов -> ProstoPython

📈 FROM O(...) TO O(...)

Union Find: от O(n) до O(α(n)) для задач на связность

Задача: есть n элементов и список связей. Нужно быстро отвечать — связаны ли два элемента?

# Элементы: 0, 1, 2, 3, 4
# Связи: (0,1), (1,2), (3,4)
# Связаны ли 0 и 2? → True
# Связаны ли 0 и 3? → False

Наивное решение — обход графа:

def are_connected(graph, a, b):
    visited = set()
    queue = [a]
    while queue:
        node = queue.pop()
        if node == b:
            return True
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])
    return False

O(n) на каждый запрос. При тысячах запросов — медленно.

Union Find — почти O(1) на запрос:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connected(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
uf.union(3, 4)

print(uf.connected(0, 2))  # True
print(uf.connected(0, 3))  # False

Две оптимизации:

Path compression — при find() делаем все узлы на пути дочерними корня напрямую. Дерево становится плоским.

Union by rank — присоединяем меньшее дерево к большему. Высота не растёт.

Вместе дают O(α(n)) — функция Акермана, растёт настолько медленно что практически константа.

Когда применять:

Задачи на связные компоненты, обнаружение циклов в графе, задача с островами если нужны множественные запросы.

🐍Вопросы с собесов -> ProstoPython

🧠 Interview Thinking

Минимальный путь в графе. BFS vs Dijkstra

Задача: найти кратчайший путь между двумя узлами.

# Граф с весами рёбер
graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("C", 2), ("D", 5)],
    "C": [("D", 1)],
    "D": []
}
# Кратчайший путь A → D?

Как думает junior:

BFS — он же находит кратчайший путь:

from collections import deque

def bfs(graph, start, end):
    queue = deque([(start, [start])])
    visited = set()
    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

Находит путь с наименьшим количеством рёбер — но игнорирует веса. A→B→C→D даст 3 ребра, но суммарный вес 4. A→C→D — 2 ребра, вес 5.

BFS не знает про веса.

Как думает strong middle:

Если рёбра с весами — нужен Dijkstra:

import heapq

def dijkstra(graph, start, end):
    heap = [(0, start, [start])]
    visited = set()
    while heap:
        cost, node, path = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        if node == end:
            return cost, path
        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                heapq.heappush(heap, (cost + weight, neighbor, path + [neighbor]))
    return float("inf"), []

cost, path = dijkstra(graph, "A", "D")
# cost=4, path=["A","B","C","D"]

O((V + E) log V) — приоритетная очередь выбирает узел с минимальной стоимостью.

Что хочет услышать интервьюер:

1. BFS — для невзвешенных графов или когда все веса равны
2. Dijkstra — для взвешенных с неотрицательными весами
3. Bellman-Ford — если веса могут быть отрицательными

🐍Вопросы с собесов -> ProstoPython

📈 FROM O(...) TO O(...)

Задача о рюкзаке: от O(2ⁿ) до O(n·W)

Задача: есть предметы с весом и ценностью. Рюкзак вмещает W кг. Максимизировать ценность.

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
W = 8
# Ответ: 10 (предметы 0+3: вес 2+5=7, ценность 3+6=9... или 1+2: 3+4=7, ценность 4+5=9)
# Правильный: предметы 0+1+? — нужно считать

Наивное решение — перебор всех подмножеств:

def knapsack_brute(weights, values, W):
    n = len(weights)
    best = 0
    for mask in range(1 << n):
        total_w = total_v = 0
        for i in range(n):
            if mask & (1 << i):
                total_w += weights[i]
                total_v += values[i]
        if total_w <= W:
            best = max(best, total_v)
    return best

O(2ⁿ) — на 40 предметах уже триллион комбинаций.

Динамическое программирование — O(n·W):

def knapsack(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

O(n·W) время, O(W) память.

Идея:

dp[w] — максимальная ценность при вместимости w. Для каждого предмета обновляем: брать или не брать?

dp[w] = max(
    dp[w],                          # не берём предмет
    dp[w - weights[i]] + values[i]  # берём предмет
)

Идём справа налево — чтобы не использовать предмет дважды.

Сравнение на n=20, W=100:

перебор:  2²⁰ = 1 048 576 операций
DP:       20 × 100 = 2 000 операций

В 500 раз быстрее.

🐍Вопросы с собесов -> ProstoPython