🧰 Code Cleanup: «Не ищи значение дважды»

❌ Плохой код

users = {
    1: "Alice",
    2: "Bob",
    3: "Charlie",
}

for user_id in users.keys():
    print(users[user_id])

✅ Улучшенный код

for name in users.values():
    print(name)

Или, если нужен и ключ, и значение:

for user_id, name in users.items():
    print(user_id, name)

💥 Объяснение
В первом варианте ты:
получаешь ключ;
затем снова обращаешься к словарю, чтобы найти значение.
Хотя словарь уже умеет отдавать всё сразу.

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

❌ Rookie Mistakes: sort() vs sorted()

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

❌ Ошибка

nums = [3, 1, 2]

result = nums.sort()

print(result)
print(nums)

🤔 Ожидание

[1, 2, 3]
[1, 2, 3]

💥 Реальность

None
[1, 2, 3]

🧠 Почему так?

Метод sort() сортирует список на месте и ничего не возвращает.

Поэтому:

result = nums.sort()

в result окажется None.

✅ Правильно

Если нужно изменить исходный список:

nums.sort()

Если нужен новый отсортированный список:

result = sorted(nums)

⚡️ Вывод

Запомни простое правило:
sort() — изменяет существующий список.
sorted() — создаёт новый.

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

🔍 Under the Hood: почему append — это O(1), хотя список растёт

list.append(x) мы делаем не задумываясь. Но список — это массив фиксированного размера в памяти. Как он «дорастает» до нужной длины, не переписываясь каждый раз?

И почему это всё-таки O(1)?

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

1) выделить новый блок побольше
2) скопировать в него все старые элементы   ← это O(n)!
3) дописать новый

Копирование всех элементов — O(n). Если бы это случалось на каждый append, список бы строился за O(n²). Но не случается. Почему?

Трюк: список выделяет память с запасом
Когда места не хватает, Python выделяет не «+1 ячейку», а сразу заметно больше — примерно в 1.125 раза (растёт по мере надобности). Освободившиеся слоты стоят пустыми и ждут будущих append.

len=4, ёмкость=4  →  [1][2][3][4]              полный
append(5):
   выделяем ёмкость 8, копируем, дописываем
len=5, ёмкость=8  →  [1][2][3][4][5][_][_][_]  есть запас!

append(6), append(7), append(8):  ложатся в готовые слоты — БЕЗ копирования

То есть дорогое копирование происходит редко — только когда запас кончился. Между такими моментами куча дешёвых append за O(1).

Почему это «амортизированный O(1)»
Разложим стоимость на всю серию из n добавлений:

дешёвые append (в готовый слот):  O(1)   — большинство
редкие append (с копированием):   O(n)   — но всё реже и реже

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

суммарно n добавлений  →  O(n)
на одну операцию       →  O(n) / n = O(1) амортизированно

«Амортизированный» — значит «в среднем по серии», а не «всегда». Отдельный append иногда может быть O(n) (в момент расширения), но серия в целом — линейна.

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

🧰 Code Cleanup: индексы в range(len(...)) → enumerate / zip

Плохой код

for i in range(len(names)):
    print(f"{i + 1}. {names[i]}")

И где-то рядом — параллельный обход двух списков по индексу:

for i in range(len(names)):
    print(f"{names[i]} — {scores[i]}")

Работает. Но range(len(...)) — это почти всегда признак, что ты пишешь на Python как на C: крутишь индекс, чтобы потом лезть по нему в список. Индекс тут — лишний посредник.

Чистый вариант
Когда нужен и элемент, и его номер — enumerate:

for i, name in enumerate(names, start=1):
    print(f"{i}. {name}")

Когда идёшь по двум спискам параллельно — zip:

for name, score in zip(names, scores):
    print(f"{name} — {score}")

Объяснение
enumerate отдаёт пары (индекс, элемент) — не надо ни range, ни len, ни names[i]. А start=1 убирает вечное i + 1 для человекочитаемой нумерации.
zip берёт по одному элементу из каждого списка и отдаёт кортежем. Обход двух коллекций «в ногу» становится очевидным — и распаковка name, score сразу показывает, что с чем в паре.
Что меняется по сути:

range(len(x)):  крутим ЧИСЛА, потом лезем x[i]  → индекс как посредник
enumerate/zip:  крутим сами ЭЛЕМЕНТЫ            → работаем с данными напрямую

Пропадает целый класс ошибок: выход за границу, names[i] при рассинхроне длин, опечатка i вместо j. И читается как обычный текст: «для каждого имени и его счёта…».

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

📈 From O(n) to O(1)

Задача
Дано положительное число n. Определи, является ли оно степенью двойки (1, 2, 4, 8, 16, …).

Наивное решение
«Буду делить на 2, пока делится. Если в конце осталась единица — это степень двойки.»

def is_power_of_two(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Корректно. Но это цикл: для n мы делаем примерно log₂(n) итераций — O(log n).

Проблема
Мы работаем с числом как с десятичным и крутим цикл. А в этой задаче есть красивая структура, которую видно только в двоичном виде.

Оптимизированное решение
Посмотри, как степени двойки выглядят в битах:

1   →  0001
2   →  0010
4   →  0100
8   →  1000

Закономерность: у степени двойки ровно один бит равен 1. Всё.
Теперь трюк. Вычтем единицу:

   8  →  1000
   7  →  0111
        ------
n & (n-1):
1000
0111
& ----
0000   →  ноль!

Вычитание единицы «переворачивает» единственную единицу в нули справа от неё. Поэтому n и n-1 не имеют общих единичных битов — их & даёт 0. И это верно только для степеней двойки.

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

O(1) — одна битовая операция, без цикла.

Объяснение
Проверим на не-степени, скажем 6:

   6  →  110    (два единичных бита)
   5  →  101
        -----
   &  →  100    ≠ 0   →  НЕ степень двойки ✅


n & (n-1) — это классический приём «снять самый младший единичный бит». Если после снятия единственного бита осталось 0, значит бит был один → степень двойки.
Условие n > 0 обязательно: для n = 0 формула тоже дала бы 0, но ноль степенью двойки не является.

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

🧠 Что выведет код

print(True + True + True)
print(True == 1)
print(["a", "b", "c"][False])
print(sum([True, False, True, True]))

Что выведет каждая строка?

Ответы:

3
True
"a"
3

Если хоть одна строка удивила — читай дальше, тут прячется важное про устройство Python.

Разбор

Ключевой факт: в Python bool — это подкласс `int`. Не «похож на число», а буквально является числом.

isinstance(True, int)    # True
True == 1                # True
False == 0               # True

Внутри True — это 1, False — это 0. Полноценные целые, просто с красивыми именами и печатью.

Разберём по строкам:

True + True + True   →  1 + 1 + 1        →  3
True == 1            →  1 == 1           →  True
lst[False]           →  lst[0]           →  "a"   (False как индекс = 0!)
sum([T, F, T, T])    →  1 + 0 + 1 + 1    →  3

Третья строка — самая коварная: False спокойно работает как индекс 0, а True — как 1. lst[True] вернул бы "b".

Где это реально полезно

sum булевых значений — это идиома «посчитать, сколько раз условие истинно»:

# сколько чисел больше 10?
count = sum(x > 10 for x in nums)

# сколько строк непустые?
count = sum(bool(s) for s in strings)

Каждое True добавляет 1, каждое False — 0. Коротко и читаемо, без ручного счётчика в цикле.

Где это подводит

bool — подкласс int, поэтому type() == их путает при неаккуратной проверке, а как ключи словаря True и 1 — один и тот же ключ:

d = {1: "один", True: "правда"}
print(d)          # {1: 'правда'}  — True перезаписал 1 !
print(len(d))     # 1

True и 1 равны и дают одинаковый хеш → для словаря это один ключ.

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

🎭 Red Flag: raise без from — потеря исходной ошибки

Плохой пример

def load_user(user_id):
    try:
        data = cache[user_id]
    except KeyError:
        raise UserNotFoundError(f"Юзер {user_id} не найден")

Выглядит аккуратно: поймали низкоуровневый KeyError, бросили осмысленный доменный UserNotFoundError. Но так ты прячешь улики — и однажды это выйдет боком.

Что не так

Когда исключение возникает внутри блока except, Python по умолчанию цепляет его к исходному. Но в трейсбеке это выглядит запутанно:

KeyError: 42

During handling of the above exception, another exception occurred:

UserNotFoundError: Юзер 42 не найден

Формулировка «During handling of the above exception» намекает, что новая ошибка выскочила случайно, во время обработки — как будто в твоём обработчике баг. А ты-то преобразовал ошибку намеренно. Смысл связи потерян.

Хуже, когда исходную ошибку глушат совсем:

except KeyError:
    raise UserNotFoundError(...)  # а если тут не KeyError, а TypeError?

Если бы внутри try была другая, неожиданная ошибка — понять её первопричину по логам станет тяжело.

Как надо

Явно свяжи новое исключение с исходным через raise ... from:

def load_user(user_id):
    try:
        data = cache[user_id]
    except KeyError as e:
        raise UserNotFoundError(f"Юзер {user_id} не найден") from e

Теперь трейсбек говорит правду о причинно-следственной связи:

KeyError: 42

The above exception was the direct cause of the following exception:

UserNotFoundError: Юзер 42 не найден

«The direct cause» — ты явно сказал: «этот UserNotFoundError вызван вот этим `KeyError`». Отладка сохраняет всю цепочку.

Когда исходную ошибку стоит подавить

Иногда низкоуровневая причина — шум, и её нужно осознанно скрыть (например, деталь реализации, которую не должен видеть вызывающий). Для этого есть from None:

except KeyError:
    raise UserNotFoundError(f"Юзер {user_id} не найден") from None

Это тоже явное решение — «я намеренно обрываю цепочку», в отличие от случайной потери контекста при голом raise.

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

🧠 Interview Thinking: Two Sum

Классика, с которой начинается почти любой собес. И именно на ней видно, отличает ли кандидат «перебор» от «правильной структуры данных».

Задача

Дан массив чисел и target. Найди индексы двух элементов, дающих в сумме target.
Пример: nums = [2, 7, 11, 15], target = 9 → [0, 1] (2 + 7 = 9).

Как думает junior
«Переберу все пары, проверю каждую сумму.»

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Работает. Но два вложенных цикла — O(n²). На собесе сразу: «А быстрее?»

Как думает сильный кандидат

Инсайт-переворот: я ищу не «две подходящие пары», а для каждого числа — одно конкретное дополнение.
Если сейчас у меня x, то мне нужен ровно target − x. Вопрос сужается до: «встречал ли я уже target − x?» А «встречал ли уже» — это O(1) через словарь.
Иду один раз, по пути запоминаю каждое число и его индекс. Для нового x сначала проверяю, не лежит ли уже его дополнение:

def two_sum(nums, target):
    seen = {}                       # число → его индекс
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i

O(n) время, O(n) память. Один проход.

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

💾 Memory Footprint

def has_pair_summing(nums, target):
    for i in range(len(nums)):
        rest = nums[i + 1:]          # «остаток» массива
        for x in rest:
            if nums[i] + x == target:
                return True
    return False

Ищем пару с нужной суммой.

Какая сложность по ПАМЯТИ?

A) O(1)
B) O(n)
C) O(n²)
D) O(log n)

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

Мало кто замечает: срез — это не «взгляд на кусок массива», а новый список.

Разбор
nums[i+1:] выглядит как «просто хвост массива». Но срез списка в Python всегда создаёт копию — выделяет новый список и копирует туда элементы.

nums[i+1:]  →  новый список из (n - i - 1) элементов
               (не ссылка на кусок оригинала — КОПИЯ)

А делаем мы этот срез на каждой итерации внешнего цикла:

i=0:  копия длины n-1
i=1:  копия длины n-2
i=2:  копия длины n-3
...

суммарно скопировано: (n-1)+(n-2)+...+1  =  O(n²) элементов

Да, старые копии собирает garbage collector, но пиковая работа с памятью и лишние аллокации никуда не деваются — на каждом шаге мы создаём и выбрасываем целый список. Это бьёт и по памяти, и по скорости (само копирование — тоже O(n) на итерацию).

Как починить — O(1) лишней памяти
Нам не нужна копия хвоста. Нужен лишь индекс, с которого начинать внутренний цикл:

def has_pair_summing(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):   # индекс вместо среза
            if nums[i] + nums[j] == target:
                return True
    return False
nums[i+1:]:        копия хвоста каждый раз  →  O(n²) памяти
range(i+1, len):   просто числа-индексы     →  O(1) памяти

Никаких копий — ходим по оригиналу по индексам.

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

⚖️ This vs That: sorted() vs list.sort()

Обе сортируют список. Разница выглядит косметической — а стоила многим часов отладки.

Что делает list.sort()
Сортирует список на месте, меняя оригинал. И возвращает None.

nums = [3, 1, 2]
nums.sort()
print(nums)    # [1, 2, 3]  — сам список изменился

Что делает sorted()
Не трогает оригинал. Создаёт и возвращает новый отсортированный список.

nums = [3, 1, 2]
result = sorted(nums)
print(result)    # [1, 2, 3]
print(nums)      # [3, 1, 2]  — оригинал цел

Главное отличие в одной фразе
.sort()

меняет список и возвращает

None

.

sorted()

не трогает оригинал и возвращает новый список.

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

❌ Rookie Mistakes: мутабельный атрибут на уровне класса

class Cart:
    items = []          # список прямо в теле класса

    def add(self, item):
        self.items.append(item)


a = Cart()
b = Cart()

a.add("яблоко")
print(b.items)      # ['яблоко']   ← откуда?!

Две разные корзины. Кладём в первую — товар появляется во второй.

Почему это ошибка
items = [] в теле класса создаёт атрибут класса, а не экземпляра. Список создаётся один раз — при определении класса — и принадлежит самому классу, а не объектам.

Cart.items ──► ['яблоко']
                  ▲   ▲
                  │   │
                  a   b     ← оба смотрят на ОДИН список


a.items не находит атрибут в самом объекте a → поднимается к классу → находит там общий список. То же для b. append мутирует этот единственный список — и его видят все экземпляры.

Тут кроется вторая тонкость. Почему self.items.append(...) не создал атрибут у объекта? Потому что append — это мутация, а не присваивание. Присваивание бы создало:

self.items = []        # создаёт СВОЙ атрибут у экземпляра
self.items.append(x)   # мутирует ОБЩИЙ список класса

Именно поэтому баг с неизменяемыми атрибутами не возникает: count = 0 в классе безопасен, ведь self.count += 1 — это присваивание, и оно создаст личный атрибут.

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

⏱️ Big O Breakdown

# Вариант A
def process_a(items):
    for x in items:
        handle(x)
    for x in items:
        report(x)

# Вариант B
def process_b(items):
    for x in items:
        for y in items:
            compare(x, y)


n — длина items. handle, report, compare работают за O(1).

Какие сложности у A и B?
A) A: O(n), B: O(n)
B) A: O(2n), B: O(n²)
C) A: O(n), B: O(n²)
D) A: O(n²), B: O(n²)

Правильный ответ: C — A: O(n), B: O(n²)

Вопрос кажется тривиальным. Но ловушек тут две, и на обеих спотыкаются.

Разбор
Ловушка 1: циклы ПОДРЯД складываются, а не умножаются.

цикл 1:  n операций
цикл 2:  n операций
итого:   n + n = 2n

Это O(n), а не O(n²). Ключевое слово — «подряд»: второй цикл начинается после того, как первый полностью закончился. Работа складывается.
А вложенные циклы умножаются: внутренний прогоняется целиком на каждой итерации внешнего.

подряд:    n + n   = 2n    →  O(n)
вложенные: n × n   = n²    →  O(n²)

Ловушка 2: «O(2n)» — так не пишут.
Вариант B в ответах — приманка. Константы в Big O отбрасываются:

O(2n)    →  O(n)
O(n/2)   →  O(n)
O(3n+5)  →  O(n)

Big O описывает скорость роста, а не точное число операций. Удвоишь n — время удвоится, независимо от того, 2n там или 100n. Это принципиально иначе, чем n², где удвоение n даёт четырёхкратный рост.
Поэтому даже сто циклов подряд — это всё ещё O(n):

for x in items: ...   # ×100 раз
# → O(100n) = O(n)

Что действительно важно
Смотри не на количество циклов, а на их вложенность:

циклы рядом    →  складывай  →  берётся максимум
циклы внутри   →  умножай

И если циклы идут подряд, но с разной сложностью — берётся самое дорогое:

for x in items:        # O(n)
    ...
sorted(items)          # O(n log n)   ← доминирует
# итого: O(n log n)

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

🔍 Under the Hood: property — как атрибут превращается в метод

Проблема, которую он решает
Есть класс, у него публичный атрибут:

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

Код по всему проекту читает c.radius. А теперь надо добавить валидацию: радиус не может быть отрицательным.
Наивный путь — превратить в метод:

def get_radius(self): ...
def set_radius(self, value): ...

Но тогда весь код в проекте ломается: везде надо переписать c.radius на c.get_radius(). Именно поэтому в Java/C++ геттеры пишут заранее, «на всякий случай».

Что делает property
Позволяет подменить обращение к атрибуту вызовом метода — не меняя синтаксис снаружи.

class Circle:
    def __init__(self, radius):
        self.radius = radius        # это уже пойдёт через сеттер!

    @property
    def radius(self):
        return self._radius

    @radius.setter
    def radius(self, value):
        if value < 0:
            raise ValueError("Радиус не может быть отрицательным")
        self._radius = value

Снаружи ничего не изменилось:

c = Circle(5)
c.radius          # 5      → незаметно вызвался геттер
c.radius = 10     # ок     → незаметно вызвался сеттер
c.radius = -1     # ValueError !
c.radius      →  Python видит property  →  вызывает метод-геттер
c.radius = x  →  Python видит property  →  вызывает метод-сеттер

Обычное присваивание, а под ним — код с проверками.

Второе применение: вычисляемые атрибуты
Значение, которое зависит от других полей и не должно храниться отдельно:

class Circle:
    @property
    def area(self):
        return 3.14159 * self._radius ** 2
c.area      # считается на лету, скобок нет

Меняешь радиус — площадь автоматически «обновляется», потому что она не хранится, а вычисляется при каждом обращении. Никакого рассинхрона между radius и area.

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

📈 From O(n²) to O(n)

Задача
Дан массив чисел (могут быть отрицательные). Найди максимальную сумму непрерывного подмассива.

Пример: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (это [4, -1, 2, 1]).

Наивное решение
«Переберу все подмассивы, посчитаю сумму каждого.»

def max_subarray(nums):
    best = float("-inf")
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            best = max(best, total)
    return best

Корректно, O(n²). Каждый старт i — новый проход вправо.

Проблема
Мы заново рассматриваем все возможные начала. Но интуиция подсказывает: если накопленная сумма ушла в минус, тащить её дальше бессмысленно — она только испортит любое продолжение.

Оптимизированное решение (алгоритм Кадане)
Ключевой вопрос на каждом элементе:

«Продолжить предыдущий подмассив — или начать новый прямо с этого элемента?»

Ответ прост: если накопленная сумма отрицательна, она мешает. Отбрасываем её и стартуем заново.

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)   # начать заново или продолжить?
        best = max(best, current)
    return best

O(n) время, O(1) память. Один проход, две переменные.

Объяснение
current — лучшая сумма подмассива, заканчивающегося на текущем элементе. best — лучший ответ среди всех, что видели.
Трассировка [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

x:        -2    1   -3    4   -1    2    1   -5    4
current:  -2    1   -2    4    3    5    6    1    5
best:     -2    1    1    4    4    5    6    6    6
              ↑              ↑                ↑
        -2+1=-1 < 1      -2+4=2 < 4       максимум!
        начинаем заново   начинаем заново

Смотри на x = 1 (второй элемент): current + x дало бы −1, а сам x — это 1. Тянуть отрицательный хвост невыгодно → отбрасываем прошлое, начинаем новый подмассив.
В этом вся суть: отрицательный префикс никогда не помогает.

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

🧠 Что выведет код

print("" or "default")
print(0 or [])
print("hello" and 42)
print(0 and 1/0)

Что выведет каждая строка?

Ответы:

"default"
[]
42
0

Ни одного True/False. Многие ждут булев результат — а получают сами операнды.

Разбор
and и or в Python не возвращают bool. Они возвращают один из операндов — тот, на котором остановились.
or — возвращает первый истинный операнд. Если все ложные — последний:

""  or "default"   →  "" ложь → идём дальше → "default"
0   or []          →  0 ложь → идём дальше → [] (последний, хоть и ложный)


and — возвращает первый ложный операнд. Если все истинные — последний:

"hello" and 42     →  "hello" истина → идём дальше → 42
0       and 1/0    →  0 ложь → СРАЗУ возвращаем 0

Четвёртая строка — самая показательная. 1/0 — это ZeroDivisionError. Но ошибки нет! Потому что Python до неё не дошёл:

0 and 1/0
↑
ложь → результат уже известен → правую часть НЕ вычисляем

Это короткое замыкание (short-circuit): вычисление обрывается, как только результат ясен.

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

💾 Memory Footprint: рекурсия и стек вызовов

def sum_list(nums, i=0):
    if i == len(nums):
        return 0
    return nums[i] + sum_list(nums, i + 1)

Суммируем список рекурсивно. Ни одного нового списка, ни словаря, ни множества — только числа. n — длина списка.

Какая сложность по ПАМЯТИ?

A) O(1) — мы же не создаём структур данных
B) O(log n)
C) O(n)
D) O(n²)

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

Память тратится там, где её не видно в коде.

Разбор
Каждый вызов функции кладёт на стек вызовов новый фрейм: локальные переменные, аргументы, адрес возврата. Фрейм живёт, пока функция не вернула результат.
А тут ни один вызов не может вернуться, пока не вернулся вложенный:

sum_list(nums, 0)  ждёт →
  sum_list(nums, 1)  ждёт →
    sum_list(nums, 2)  ждёт →
      ...
        sum_list(nums, n)  → 0

В момент самого глубокого вызова на стеке лежат все n фреймов одновременно. Это O(n) памяти — просто не в куче, а на стеке.

итеративный цикл:  один фрейм, переменные перезаписываются  →  O(1)
рекурсия глубины n: n фреймов ждут друг друга               →  O(n)

И это не абстракция — Python упадёт

У стека есть жёсткий лимит (по умолчанию ~1000 вызовов):

sum_list(list(range(10_000)))
# RecursionError: maximum recursion depth exceeded

На списке в 10 000 элементов код падает. Не из-за времени — из-за глубины стека.

Как починить
Разверни рекурсию в цикл — тогда фрейм один, а память O(1):

def sum_list(nums):
    total = 0
    for x in nums:
        total += x
    return total

Важный нюанс: не всякая рекурсия — это O(n)

Смотри на глубину, а не на число вызовов:

линейная рекурсия (сумма списка):   глубина n       →  O(n) памяти
бинарный поиск рекурсивно:          глубина log n   →  O(log n)
обход сбалансированного дерева:     глубина log n   →  O(log n)
обход вырожденного дерева-цепочки:  глубина n       →  O(n)

Именно поэтому у рекурсивного merge sort память O(n) (плюс буферы), а у бинарного поиска — O(log n): дерево вызовов глубокое или мелкое.

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

🧠 Interview Thinking

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

Пример: "A man, a plan, a canal: Panama" → True.

Как думает junior
«Почищу строку, разверну и сравню.»

def is_palindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Работает, и это O(n) по времени. Отличный старт — на многих собесах этого хватит.

Но интервьюер добавит: «А без дополнительной памяти?»
И тут junior обычно теряется — ведь по времени-то уже линия, куда быстрее?

Как думает сильный кандидат

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

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1                                  # пропускаем мусор слева
        while left < right and not s[right].isalnum():
            right -= 1                                 # пропускаем мусор справа
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

O(n) время, O(1) память. Ни одной копии.

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

⏱️ Big O Breakdown

def count_common(users, banned):
    count = 0
    for user in users:
        if user in banned:      # banned — это список
            count += 1
    return count

Считаем, сколько пользователей в бан-листе. n — число users, m — размер banned.

Какая общая сложность по времени?
A) O(n)
B) O(n + m)
C) O(n · m)
D) O(n log m)

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

Цикл один, и кажется, что O(n). Но in по списку прячет второй цикл внутри.

Разбор
Всё зависит от того, что такое banned. Если это список — user in banned делает линейный поиск: перебирает элементы по одному, пока не найдёт (или не дойдёт до конца).

user in banned (список)  →  до m сравнений

И эту проверку мы делаем на каждом из n пользователей:

n пользователей × до m сравнений каждый  =  O(n · m)

Один видимый цикл for, но in по списку — это скрытый второй цикл.

Магия одной строки
Меняем banned со списка на множество — и сложность падает:

def count_common(users, banned):
    banned = set(banned)        # ← превращаем в множество
    count = 0
    for user in users:
        if user in banned:      # теперь O(1)
            count += 1
    return count


in по множеству — это O(1) (хеш-таблица: вычисляем хеш, прыгаем в ячейку, не перебирая). Общая сложность становится:

построение set: O(m)   (один раз)
n проверок × O(1):  O(n)
итого: O(n + m)
banned — список:     n × O(m) = O(n·m)
banned — множество:  O(m) + n × O(1) = O(n + m)

Для n = m = 10 000 разница между 10⁸ и 2·10⁴ операций — это секунды против мгновения.

Важный нюанс — когда set не окупается
Построение множества стоит O(m). Если проверок мало — скажем, всего одна — конвертировать нет смысла: O(m) на построение съест всю экономию.

одна проверка:      list  →  O(m),  set  →  O(m) на построение + O(1) = O(m)
                    (одинаково, конвертация не нужна)
много проверок (n): list  →  O(n·m),  set  →  O(m + n)
                    (set выигрывает тем сильнее, чем больше n)

Множество окупается, когда по одной и той же коллекции проверяешь принадлежность многократно.

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

🔍 Under the Hood: MRO и почему super() — это не «родитель»

Почти все думают: super() вызывает родительский класс. При простом наследовании — да. При множественном — нет.

Загадка

class A:
    def greet(self):
        print("A")

class B(A):
    def greet(self):
        print("B")
        super().greet()

class C(A):
    def greet(self):
        print("C")
        super().greet()

class D(B, C):
    def greet(self):
        print("D")
        super().greet()

D().greet()

Интуиция говорит D → B → A. А на деле:

D
B
C      ← откуда C?! B же не наследует C
A

Что происходит
У каждого класса есть MRO — линейный список, в каком порядке искать методы:

D.__mro__
# (D, B, C, A, object)

Ключевой факт:
super()

вызывает не родителя, а следующий класс в MRO относительно текущего.

MRO:  D → B → C → A → object

D.greet → super → B
B.greet → super → C   ← вот почему C
C.greet → super → A
A.greet → стоп


super() в B смотрит не на «своего родителя A», а на позицию B в MRO этого объекта — а там дальше C.

Зачем так — проблема ромба

    A
   / \
  B   C
   \ /
    D


D наследует и B, и C, оба — от A. Если бы каждый звал своего родителя, A.greet вызвался бы дважды. MRO выстраивает всех в линию так, что каждый предок посещается ровно один раз — A в самом конце.

Порядок строит алгоритм C3-линеаризации: потомки идут раньше предков, порядок базовых классов из объявления сохраняется. Если согласованного порядка нет — Python падает с TypeError при определении класса.

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

🧠 Что выведет код

x = [1, 2, 3]

def modify(lst):
    lst = lst + [4]

def mutate(lst):
    lst.append(4)

modify(x)
print(x)

mutate(x)
print(x)

Варианты:
A) [1, 2, 3, 4] и [1, 2, 3, 4]
B) [1, 2, 3] и [1, 2, 3, 4]
C) [1, 2, 3, 4] и [1, 2, 3, 4, 4]
D) [1, 2, 3] и [1, 2, 3]


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

Одна функция «меняет» список, другая — нет. Почему?

Разбор
Python передаёт аргументы не по значению и не по ссылке, а по модели «передача ссылки на объект» (pass by object reference). Параметр функции — это новое имя, указывающее на тот же объект.

x ──► [1, 2, 3]
        ▲
lst ────┘   ← lst и x смотрят на ОДИН объект

Дальше всё решает: ты переприсваиваешь имя или мутируешь объект.
modify: lst = lst + [4]
lst + [4] создаёт новый список. Присваивание lst = ... перевешивает локальное имя lst на этот новый объект. Связь с x рвётся. Оригинал не тронут.

lst = lst + [4]

x   ──► [1, 2, 3]        ← оригинал цел
lst ──► [1, 2, 3, 4]     ← новый объект, только внутри функции

Присваивание меняет имя, а не объект. Наружу это не видно.
mutate: lst.append(4)
append мутирует сам объект — тот, на который смотрит и lst, и x. Имя не трогаем — меняем то, на что оно указывает.

lst.append(4)

x   ──► [1, 2, 3, 4]     ← тот же объект, изменён
lst ──┘

Суть в одной строке

lst = ...        →  переприсваивание ИМЕНИ  →  оригинал не виден снаружи
lst.append(...)  →  мутация ОБЪЕКТА         →  видно везде, где есть ссылка

Функция может изменить переданный объект только через мутацию. Присваивание нового значения параметру наружу не протекает — оно лишь перевешивает локальное имя.

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

🧰 Code Cleanup: ручная проверка ключа → dict.get и setdefault

Плохой код

# достать значение с дефолтом
if "timeout" in config:
    timeout = config["timeout"]
else:
    timeout = 30

# накопить в словарь списков
if key in groups:
    groups[key].append(value)
else:
    groups[key] = [value]

Работает. Но каждое обращение к словарю — это четыре строки на «а вдруг ключа нет». Проверка in, потом снова доступ по тому же ключу — дублирование.

Чистый вариант

# дефолт в одну строку
timeout = config.get("timeout", 30)

# накопление без ветвлений
groups.setdefault(key, []).append(value)

Объяснение
dict.get(key, default) возвращает значение по ключу, а если ключа нет — default. Никакого if in, никакого второго обращения:

if key in d: x = d[key] else: x = default
        ↓
x = d.get(key, default)


dict.setdefault(key, default) хитрее: если ключа нет — вставляет его со значением default и возвращает это значение; если есть — просто возвращает существующее. Поэтому setdefault(key, []).append(value) работает в обоих случаях:

ключа нет:  вставили [], вернули его, добавили value  →  [value]
ключ есть:  вернули текущий список, добавили value    →  [..., value]

Важная тонкость про get — не путай «ключа нет» и «значение ложное»:

config = {"retries": 0}

config.get("retries", 3)      # 0   — ключ есть, вернётся его значение
config.get("retries") or 3    # 3   — ой! 0 ложен, or его отбросил


get с дефолтом смотрит на наличие ключа, а or — на истинность значения. Для 0, "", [] это разные вещи. Нужен именно «ключ отсутствует» — бери get(key, default), а не get(key) or default.

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