📈 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

🧠 Interview Thinking

Похоже на классику про акции, но правило одно меняет всё — и на этом ловят.

Задача

Дан массив prices — цена акции по дням. Теперь можно совершать сколько угодно сделок: покупать и продавать много раз (но держать не больше одной акции одновременно). Максимизируй суммарную прибыль.

Пример: [7, 1, 5, 3, 6, 4] → 7.

Как думает junior

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

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

Сначала — разбор задачи на бумаге, до кода. Что значит «неограниченно много сделок»?
Ключевое наблюдение: раз ограничений на число сделок нет, я могу «поймать» каждый участок роста. А любой рост с A до B через промежуточные точки можно разложить на сумму дневных приростов:

цена 1 → 5:  прибыль 4
это то же, что:  (2−1) + (3−2) + (4−3) + (5−4) = 4

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

def max_profit(prices):
    return sum(
        prices[i] - prices[i - 1]
        for i in range(1, len(prices))
        if prices[i] > prices[i - 1]
    )

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

Смысл: «покупай перед каждым днём роста, продавай после». Все восходящие отрезки собираются автоматически.
Трассировка [7, 1, 5, 3, 6, 4]:

день:    7   1   5   3   6   4
разница:   -6  +4  -2  +3  -1
берём:      —   4    —   3   —

сумма положительных: 4 + 3 = 7

Отрицательные разницы (падения) просто игнорируем — в эти дни мы акцию не держим.

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

❌ Rookie Mistakes: except ловит не то, что кажется

try:
    config = load_config()
    value = config["timeout"]
    result = process(value)
except KeyError:
    print("В конфиге нет ключа timeout")
    result = default_result()

Логика ясная: если в конфиге нет timeout — берём дефолт. Но однажды process внутри себя тоже кинет KeyError — по совсем другой причине. И этот блок его проглотит, напечатав неверное сообщение.

Почему это ошибка
except KeyError ловит любой KeyError, возникший где угодно в блоке try — не только тот, что ты имел в виду.

try:
    config = load_config()
    value = config["timeout"]      # ← ждём KeyError отсюда
    result = process(value)        # ← а он прилетит ОТСЮДА
except KeyError:                   # ловит оба, не различая
    ...

Если process внутри обратится к несуществующему ключу словаря — вылетит KeyError, но не про timeout. А обработчик уверенно скажет «нет ключа timeout» и подсунет дефолт. Настоящий баг в process замаскирован, сообщение врёт, отладка превращается в ад.

Суть ошибки: try обнимает слишком много кода. Чем больше строк под ним, тем выше шанс, что тип исключения совпадёт случайно, не по той причине.

Исправленный вариант
Оборачивай в try ровно ту строку, чьё исключение ты ждёшь:

config = load_config()

try:
    value = config["timeout"]      # только эта строка
except KeyError:
    print("В конфиге нет ключа timeout")
    value = 30

result = process(value)            # его ошибки НЕ ловятся здесь

Теперь KeyError из process полетит наверх — как и должен, с честным трейсбеком.

А для «достать значение с дефолтом» вообще не нужен try:

value = config.get("timeout", 30)   # ключа нет → 30, без исключений
result = process(value)

Общее правило узкого try

широкий try:   try { A; B; C } except E   ← E от A, B или C — не различить
узкий try:     try { B } except E          ← точно знаем: это про B

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

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

⚖️ This vs That: list vs tuple

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

Что делает list
Изменяемая последовательность. Можно добавлять, удалять, менять элементы:

items = [1, 2, 3]
items.append(4)
items[0] = 99      # ок

Что делает tuple
Неизменяемая последовательность. После создания — только чтение:

point = (1, 2, 3)
point[0] = 99      # TypeError: 'tuple' object does not support item assignment

Главное отличие в одной фразе
list

— изменяемый,

tuple

— нет. Но следствия из этого важнее самого факта.

Следствие 1: хешируемость
Кортеж можно использовать как ключ словаря и элемент множества. Список — нельзя:

cache = {(1, 2): "результат"}     # ок
cache = {[1, 2]: "результат"}     # TypeError: unhashable type: 'list'

Причина: хеш должен быть стабильным. Изменяемый объект менял бы хеш после мутации — и ключ бы «терялся» в хеш-таблице. Поэтому мутабельные типы нехешируемы по определению.

Это главная практическая причина брать кортеж — координаты, составные ключи, пары в set.

Следствие 2: смысл, а не только форма
Есть негласная семантическая конвенция:

list   →  однородная коллекция ПЕРЕМЕННОЙ длины
          [user1, user2, user3] — «много одинакового»

tuple  →  фиксированная структура, где важна ПОЗИЦИЯ
          (x, y) — координата; (name, age, city) — запись

Поэтому функции возвращают кортежи: return name, age — это одна структура из разных по смыслу полей, а не «список из двух штук».

Следствие 3: память и скорость
Кортеж знает свой размер навсегда — ему не нужен запас под рост:

list:  выделяет память С ЗАПАСОМ под будущие append
tuple: ровно под n элементов

Отсюда кортеж компактнее и чуть быстрее в создании/обходе. На миллионах мелких записей разница заметна.

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

📈 From O(n log n) to O(n)

Задача
Дан массив из n чисел. Верни k наибольших. Обычно k сильно меньше n (топ-10 из миллиона).

Наивное решение
«Отсортирую и возьму хвост.»

def top_k(nums, k):
    return sorted(nums, reverse=True)[:k]

Коротко и корректно. Но сложность — O(n log n): мы упорядочили весь массив, хотя нужны всего k элементов.

Проблема
Мы делаем гораздо больше работы, чем требует задача. Порядок остальных n − k элементов нас не интересует вообще — а мы за него заплатили.

Оптимизированное решение
Куча (heap) размера k. Держим min-heap ровно из k элементов — текущего топа. Новый элемент сравниваем с минимумом кучи: если он больше — минимум вылетает, новый заходит.

import heapq

def top_k(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)              # O(k)
    for x in nums[k:]:
        if x > heap[0]:              # heap[0] — минимум кучи, O(1)
            heapq.heapreplace(heap, x)   # выкинуть min, вставить x: O(log k)
    return heap

Сложность: O(n log k). Когда k мало и почти константа — это фактически O(n).
По памяти — O(k) вместо O(n) на копию для сортировки. Важно, если данные идут потоком и не влезают в память целиком.

Объяснение
Min-heap — структура, где минимум всегда на вершине и доступен за O(1). Это ровно то, что нужно: «самый слабый в топе» — кандидат на вылет.
Трассировка nums = [3, 1, 5, 12, 2, 11], k = 3:

куча из первых 3:  [1, 3, 5]        min = 1

x=12:  12 > 1  → выкидываем 1  → [3, 12, 5]    min = 3
x=2:   2 < 3   → пропускаем     → [3, 12, 5]
x=11:  11 > 3  → выкидываем 3  → [5, 12, 11]   min = 5

топ-3: [5, 12, 11]

Куча в любой момент содержит k лучших из просмотренного. Элементы меньше текущего минимума отбрасываются мгновенно, за одно сравнение.

В стандартной библиотеке это уже завёрнуто:

heapq.nlargest(k, nums)     # то же самое, готовое

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

🎭 Red Flag: изменение списка, по которому идёт цикл

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

def remove_inactive(users):
    for user in users:
        if not user.is_active:
            users.remove(user)      # удаляем прямо во время итерации


users = [alice, bob, carol, dave]   # bob и carol неактивны
remove_inactive(users)
print([u.name for u in users])      # ['alice', 'carol', 'dave']  ← carol выжила!

Код выглядит очевидно правильным. Но неактивный carol остался в списке. И — что коварно — никакой ошибки не было. Просто тихо неверный результат.

Что не так
Итератор списка ходит по индексам, а не по элементам «логически». Он помнит: «я на позиции i». Когда ты удаляешь элемент — все, что правее, сдвигаются влево, и следующий элемент проскакивает мимо.

users: [alice, bob, carol, dave]
         i=0    i=1    i=2    i=3

i=1: bob неактивен → remove(bob)
     список сдвинулся:
     [alice, carol, dave]
              ↑
     а итератор идёт на i=2 → это dave, НЕ carol
     carol пропущена!

Удалил элемент → сосед занял его место → итератор перешагнул через соседа. Каждое удаление «прячет» следующий элемент от проверки.
Со словарём и множеством такое хотя бы честно падает с RuntimeError. А список молчит и возвращает мусор — это опаснее всего: баг проходит тесты на «удобных» данных и стреляет в проде.

Как надо
Не мутируй то, что перебираешь. Построй новый список из того, что нужно оставить:

def remove_inactive(users):
    return [user for user in users if user.is_active]

Если по контракту надо изменить тот же объект (на него есть ссылки снаружи) — перезапиши его содержимое срезом:

def remove_inactive(users):
    users[:] = [user for user in users if user.is_active]   # мутируем на месте, но безопасно


users[:] = ... заменяет содержимое существующего списка — ссылки снаружи увидят изменение, но итерации по живому списку во время удаления нет.
Ещё вариант, если очень нужен цикл, — итерируйся по копии, а меняй оригинал:

for user in list(users):        # копия ключей/элементов
    if not user.is_active:
        users.remove(user)

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

for i in range(len(users) - 1, -1, -1):
    if not users[i].is_active:
        del users[i]

Но это менее читаемо, чем comprehension. Comprehension почти всегда лучше.

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

⏱️ Big O Breakdown: рекурсивный Фибоначчи

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Классика из учебника. Выглядит элегантно. n — входное число.

Какая сложность по времени?
A) O(n)
B) O(n²)
C) O(2ⁿ)
D) O(n log n)


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

Три строки кода, а под ними — экспоненциальный взрыв.

Разбор
Каждый вызов fib(n) порождает два новых вызова: fib(n-1) и fib(n-2). Те — ещё по два. Дерево вызовов удваивается на каждом уровне.

                fib(5)
              /        \
         fib(4)        fib(3)
challenged /    \       /    \
     fib(3)  fib(2)  fib(2) fib(1)
      /  \    /  \    /  \
    ...  ... ...  ... ... ...

Глубина дерева — примерно n, а на каждом уровне число вызовов удваивается → всего порядка 2ⁿ вызовов. Для fib(50) это больше триллиона вызовов. Программа зависнет.

Где именно взрыв

Смотри на дерево: fib(3) считается дважды, fib(2) — трижды. Мы решаем одни и те же подзадачи снова и снова, с нуля. Вот источник экспоненты — не сама рекурсия, а повторный пересчёт.

fib(2) вызывается: в fib(4) и в fib(3) и ещё... — многократно
каждый раз считается заново, хотя ответ один и тот же

Как починить — мемоизация
Запоминаем уже посчитанное. Каждое fib(k) считается один раз:

from functools import cache

@cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

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

без кэша:  каждая подзадача считается многократно  →  O(2ⁿ)
с кэшем:   каждая подзадача считается один раз      →  O(n)

Одна строка cache превращает триллион вызовов в n.
Или итеративно, двумя переменными — и O(1) памяти вместо стека рекурсии:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

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

❌ Rookie Mistakes: list *= n с вложенными списками

На первый взгляд кажется, что ты создаёшь несколько независимых списков.
Но это одна из самых коварных ловушек Python.

❌ Ошибка

matrix = [[0] * 3] * 3

matrix[0][1] = 1

print(matrix)

🤔 Ожидание

[
    [0, 1, 0],
    [0, 0, 0],
    [0, 0, 0]
]

💥 Реальность

[
    [0, 1, 0],
    [0, 1, 0],
    [0, 1, 0]
]

🧠 Почему так?

Оператор * не создаёт новые вложенные списки.
Он копирует ссылку на один и тот же объект.
В итоге все строки матрицы указывают на один список.

✅ Правильно

matrix = [[0] * 3 for _ in range(3)]

matrix[0][1] = 1

print(matrix)

⚡️ Вывод
Если создаёшь вложенные списки, не используй * для внешнего списка.
[[0] * n for _ in range(n)] — безопасный вариант, который должен войти в привычку.

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

🧰 Code Cleanup: «Не используй list(), если можно сразу создать список»

❌ Плохой код

result = list()

for i in range(10):
    result.append(i * i)

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

result = [i * i for i in range(10)]

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

⚡️ Правило
Если задача — создать новый список, а не изменять существующий, используй list comprehension. Код становится компактнее и легче читается.

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

🧠 Interview Thinking: «Не оптимизируй то, что не является проблемой»

📌 Задача
Проверить, является ли строка палиндромом.

👶 Как думает junior
Сразу пишет решение с двумя указателями:

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

«Так эффективнее.»

🧠 Как думает сильный кандидат
Сначала оценивает задачу.
Если дополнительных требований нет, решение может быть намного проще:

def is_palindrome(s):
    return s == s[::-1]

А затем добавляет:

«Если бы интервьюер запретил дополнительную память, тогда я бы использовал два указателя.»

🎯 Что хочет интервьюер
Не увидеть самое сложное решение.
А понять, что ты умеешь выбирать инструмент под условия задачи, а не писать сложный код "на всякий случай".

💡 Вывод
Сильный кандидат сначала ищет самое простое корректное решение.
И только потом усложняет его, если этого требуют ограничения.

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

📈 From O(n²) to O(n): Проверка на дубликаты

📌 Задача
Определить, есть ли в списке повторяющиеся элементы.

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

def has_duplicates(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Сложность: O(n²)

✅ Оптимизированное решение

def has_duplicates(nums):
    seen = set()

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

Сложность: O(n)

💥 Что изменилось?
Вместо сравнения каждого элемента со всеми остальными мы запоминаем уже встреченные значения в set.
Проверка наличия в множестве выполняется за O(1).

⚡️ Вывод
Если задача сводится к вопросу:

«Встречался ли этот элемент раньше?»

Первым делом подумай о set. Это один из самых частых способов превратить O(n²) в O(n).

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

🧰 Code Cleanup: «Убери дублирование условия»

❌ Плохой код

def get_discount(user):
    if user.is_premium and user.age >= 18:
        return 20
    elif user.is_premium and user.age < 18:
        return 10
    else:
        return 0



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

def get_discount(user):
    if not user.is_premium:
        return 0

    return 20 if user.age >= 18 else 10



💥 Что изменилось?
В исходном коде user.is_premium проверяется дважды.
Сначала разбираемся с исключением:
if not user.is_premium:
return 0
После этого можно спокойно работать только с премиум-пользователем.

⚡ Правило
Если одно условие повторяется в нескольких ветках — попробуй вынести его раньше и сделать ранний return.
Меньше вложенности → меньше кода → проще читать

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

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

📌 Задача
Найти, есть ли в двух списках хотя бы один общий элемент.

a = [10, 20, 30, 40]
b = [5, 30, 70, 90]

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

def has_common(a, b):
    for x in a:
        for y in b:
            if x == y:
                return True
    return False

Сложность: O(n × m)
Каждый элемент a сравнивается со всеми элементами b.

✅ Оптимизированное решение

def has_common(a, b):
    values = set(b)

    return any(x in values for x in a)

Сложность: O(n + m)

💡 Главный инсайт

Мы не ускорили вложенный цикл.
Мы вообще от него избавились.

Вместо:

«Сравни этот элемент со всеми»

делаем:

«Проверь, встречался ли он в

set

».

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

🧠 Interview Thinking

📌 Задача

Есть список:

nums = [3, 1, 4, 1, 5, 9]

Найти второй по величине уникальный элемент.

Ответ:

5

👶 Как думает junior

Сразу сортирует:

def second_max(nums):
    return sorted(set(nums))[-2]

Работает

Но сильный кандидат сначала спросит:

«Можно ли использовать дополнительную память?»

Если нельзя — это решение уже не подходит.

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

Проходит список один раз и хранит только два значения:

def second_max(nums):
    first = second = float("-inf")

    for num in nums:
        if num > first:
            second = first
            first = num
        elif first > num > second:
            second = num

    return second

Сложность: O(n) по времени и O(1) по памяти

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