⏱️ Big O Breakdown

Посмотри на код:

def example(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i, j, k)

❓ Какая сложность?

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

✅ Правильный ответ: C) O(n³)

🧠 Разбор

Первый цикл:

n

Второй цикл:

n

Третий цикл:

n

Общее количество операций:

n × n × n = n³

📌 Итог

Сложность алгоритма:

O(n³)

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

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

Задача: найти максимальную сумму подмассива.
(классическая задача, которую любят на собеседованиях)

Например:

nums = [-2,1,-3,4,-1,2,1,-5,4]

Ответ:

6

Потому что лучший подмассив:

[4, -1, 2, 1]

❌ Наивное решение — O(n²)

def max_subarray(nums):
    max_sum = float('-inf')

    for i in range(len(nums)):
        current = 0
        for j in range(i, len(nums)):
            current += nums[j]
            max_sum = max(max_sum, current)

    return max_sum

Что происходит:

🔷выбираем начало подмассива

🔷перебираем все возможные продолжения

🔷Два цикла —> O(n²).

✅ Оптимизация — O(n)
Алгоритм Кадане.

def max_subarray(nums):
    current = max_sum = nums[0]

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

    return max_sum

🧠 Идея

Если текущая сумма становится хуже, чем просто новый элемент — начинаем новый подмассив.

То есть на каждом шаге решаем:

🔷продолжать текущий массив
🔷или начать новый

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

В Django есть 3 типа наследования моделей

Abstract Base Class

🔹 Базовая модель не создаёт таблицу
🔹 Поля наследуются в дочерние модели

Multi-table inheritance

🔹 Для каждой модели создаётся отдельная таблица
🔹 Между ними связь OneToOne

Proxy model

🔹 Не создаёт новую таблицу
🔹 Меняет поведение (например, менеджеры, методы)

Итог

🔹 Abstract — переиспользование полей без таблицы
🔹 Multi-table — расширение с отдельной таблицей
🔹 Proxy — изменение поведения без изменения структуры

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

🧰 Code Cleanup — выпуск 31
Тема: лишний range(len(...))

Очень частая конструкция у новичков:

❌ Плохо:

for i in range(len(nums)):
    print(nums[i])

Работает? Да.
Но это не самый читаемый вариант.

✅ Code Cleanup:

for num in nums:
    print(num)

🧠 Почему так лучше

🔹 не нужен индекс, если ты его не используешь
🔹 код короче и чище
🔹 сразу понятно, что мы итерируемся по элементам

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

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

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

Ответ: [2, 2, 2]

Lambda не захватывает значение i в момент создания. Она захватывает переменную i из замыкания.

К моменту вызова f() цикл уже завершился, и i == 2. Все три функции смотрят на одну и ту же переменную.

# Фикс через default-аргумент:

funcs = []

for i in range(3):
    funcs.append(lambda x=i: x)

print([f() for f in funcs])  # [0, 1, 2]

Default-аргумент вычисляется сразу при создании функции — поэтому каждый раз фиксируется текущее значение i.

Замыкание в Python хранит ссылку на переменную из enclosing scope, а не её копию. Это нужно чувствовать на уровне рефлексов.

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

📈 FROM O(...) TO O(...)
Поиск дубликатов: от O(n²) до 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²) время / O(1) память

Два вложенных цикла. На 10 000 элементов — 50 миллионов сравнений.

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

def has_duplicates(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

⚡️ O(n) время / O(n) память

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

🧩 Code Cleanup

Декораторы: не пиши один и тот же код дважды

Часто вижу такое:

def get_user(user_id):
    print(f"Вызов get_user с {user_id}")
    result = db.query(user_id)
    print(f"get_user выполнился за ...")
    return result

def get_orders(user_id):
    print(f"Вызов get_orders с {user_id}")
    result = db.query_orders(user_id)
    print(f"get_orders выполнился за ...")
    return result

Логирование копируется в каждую функцию. Если нужно что-то поменять — правишь везде.

После:

import functools
import time

def log(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        print(f"Вызов {func.__name__} с {args} {kwargs}")
        start = time.perf_counter()
        result = func(*args, **kwargs)
        print(f"{func.__name__} выполнился за {time.perf_counter() - start:.4f}с")
        return result
    return wrapper

@log
def get_user(user_id):
    return db.query(user_id)

@log
def get_orders(user_id):
    return db.query_orders(user_id)

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

⏱️ Big O Breakdown

`sorted()` vs `list.sort()`: в чём разница по памяти

Оба сортируют. Оба используют Timsort. Какова сложность каждого?

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

result = sorted(nums)
nums.sort()

Варианты:
А) Оба O(n log n) время, O(1) память
Б) sorted — O(n log n) / O(n), list.sort() — O(n log n) / O(1)
В) Оба O(n log n) время, O(n) память
Г) sorted — O(n), list.sort() — O(n log n)

Ответ: Б

Алгоритм один и тот же — Timsort, O(n log n) в среднем и худшем случае. Разница в памяти.

list.sort() сортирует список на месте. Дополнительная память — O(1), исходный список меняется.

sorted() создаёт новый список. Дополнительная память — O(n), исходный остаётся нетронутым.

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

result = sorted(nums)
print(nums)    # [3, 1, 4, 1, 5] — не изменился
print(result)  # [1, 1, 3, 4, 5] — новый объект

nums.sort()
print(nums)    # [1, 1, 3, 4, 5] — изменился на месте

Ловушка, которую все допускают:

def process(data):
    data.sort()  # мутирует оригинал
    ...

my_list = [3, 1, 2]
process(my_list)
print(my_list)  # [1, 2, 3] — сюрприз

Передал список в функцию, а он изменился снаружи. Если это не задумано — баг.

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

list.sort() — когда исходный порядок не нужен и важна память. sorted() — когда нужно сохранить оригинал или сортируешь не список (tuple, generator, любой iterable).

Одинаковая нотация O(n log n) не означает одинаковое поведение. Разница в мутабельности и памяти — это детали, которые в продакшене стоят дорого.

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

❌ Rookie Mistakes

Не используй except Exception как мусорное ведро

Один из самых частых антипаттернов в реальных проектах:

def get_user(user_id):
    try:
        user = db.query(user_id)
        return user.name
    except Exception:
        return None

Выглядит безопасно. На деле — скрывает любую ошибку молча.

Что может пойти не так:

def get_user(user_id):
    try:
        user = db.query(user_id)
        return user.naem  # опечатка — AttributeError
    except Exception:
        return None       # проглотили, вернули None
                          # баг найдёшь через неделю

AttributeError, TypeError, KeyError, потеря соединения с БД — всё уходит в тишину. Функция возвращает None, код продолжает работу, а баг всплывает в совершенно другом месте.

Правильно — ловить конкретные исключения:

def get_user(user_id):
    try:
        user = db.query(user_id)
        return user.name
    except UserNotFoundError:
        return None
    except DatabaseConnectionError as e:
        logger.error(f"DB недоступна: {e}")
        raise

Каждое исключение обрабатывается осознанно. raise пробрасывает ошибку выше, если обработать её здесь невозможно.

Когда except Exception всё же уместен:

# На верхнем уровне — как последний рубеж
try:
    run_app()
except Exception as e:
    logger.critical(f"Необработанная ошибка: {e}")
    raise  # всё равно пробрасываем

Только на самом верху, только с логированием, только с raise.

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

⏱️ Big O Breakdown

Конкатенация строк в цикле. Где прячется O(n²)

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

def build_string(words):
    result = ""
    for word in words:
        result += word
    return result

Варианты:
А) O(n)
Б) O(n log n)
В) O(n²)
Г) O(1)

Ответ: В) O(n²)

Строки в Python иммутабельны. Каждый += не дописывает слово в конец — он создаёт новую строку, копируя всё, что было до.

Шаг 1: копируем 1 символ
Шаг 2: копируем 2 символа
Шаг 3: копируем 3 символа
...
Шаг n: копируем n символов

Итого: 1 + 2 + 3 + ... + n = O(n²) по количеству копируемых символов.

На 10 словах — незаметно. На 100 000 — катастрофа.

Правильно:

def build_string(words):
    return "".join(words)

str.join() вычисляет итоговый размер заранее, выделяет память один раз и заполняет её. Сложность — O(n).

Ловушка на собесе:

# Это тоже O(n²) — не обманывайся форматированием
result = ""
for word in words:
    result = result + word + ", "

И ещё одна:

# А вот это уже O(n) — список мутабельный
parts = []
for word in words:
    parts.append(word)
result = "".join(parts)

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

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

Схема
A
/ \
B C
\ /
D

🔹 D наследуется от B и C
🔹 B и C наследуются от A

В чём проблема

🔹 Неочевидно, какой метод из A будет вызван
🔹 Возможен двойной вызов конструктора
🔹 Возникает неоднозначность порядка вызовов

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

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

Поиск всех простых до N: от O(n√n) до O(n log log n)

Очевидное решение — проверять каждое число отдельно:

def primes_up_to(n):
    return [i for i in range(2, n + 1) if is_prime(i)]

O(√n) на каждое число. Суммарно — O(n√n). На миллионе чисел медленно.

Решето Эратосфена:

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    return [i for i, v in enumerate(is_prime) if v]

O(n log log n) — практически линейная.

Идея: не проверяем делители, а вычёркиваем кратные. Каждое составное число вычёркивается ровно один раз. Начинаем с i*i — всё меньшее уже вычеркнуто раньше.

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

🧩 Code Cleanup

Не проверяй тип через type() — используй isinstance()

Часто вижу такое:

def process(value):
    if type(value) == int:
        return value * 2
    if type(value) == str:
        return value.upper()

Выглядит логично. Но это ловушка.

После:

def process(value):
    if isinstance(value, int):
        return value * 2
    if isinstance(value, str):
        return value.upper()

В чём разница:

type() проверяет точный тип — не учитывает наследование. isinstance() учитывает.

class MyInt(int):
    pass

x = MyInt(5)

type(x) == int      # False — сюрприз
isinstance(x, int)  # True

С type() подкласс не пройдёт проверку. Это ломает полиморфизм и нарушает принцип подстановки Лисков.

Ещё плюс — isinstance() принимает кортеж типов:

isinstance(value, (int, float))  # вместо двух отдельных проверок

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

⏱️ Big O Breakdown

Поиск элемента в list vs set. Казалось бы, одно и то же

Какова сложность этих двух операций?

nums_list = list(range(1_000_000))
nums_set = set(range(1_000_000))

999_999 in nums_list
999_999 in nums_set

Варианты:
А) Оба O(1)
Б) Оба O(n)
В) list — O(n), set — O(1)
Г) list — O(1), set — O(n)

Ответ: В) list — O(n), set — O(1)

`list` хранит элементы последовательно. Проверка `in` — линейный перебор от первого до последнего. В худшем случае — n сравнений.

`set` — хеш-таблица. Python вычисляет `hash(999_999)`, находит нужный bucket и проверяет один элемент. Почти всегда — одна операция.

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

🧠 Interview Thinking

Найди два числа в массиве, дающих целевую сумму

Классика. Есть в каждом втором собесе.

# Дано:
nums = [2, 7, 11, 15]
target = 9

# Вернуть индексы двух чисел, сумма которых == target
# Ответ: [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)

Как думает junior:

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²). Работает — но интервьюер сразу спросит: «Можешь быстрее?»

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

Не ищу пары — ищу дополнение.

Для каждого числа x нужно найти target - x. Если хранить уже просмотренные числа в словаре — поиск O(1).

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i

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


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

Не просто правильный код. А ход мыслей:

1. Назвал наивное решение и его сложность
2. Сам предложил оптимизацию — не ждал подсказки
3. Объяснил trade-off: платим памятью, выигрываем время
4. Проверил edge cases: пустой массив, одно число, дубликаты

# Edge case с дубликатами:
nums = [3, 3], target = 6
# seen = {3: 0} → complement = 3 → найден на индексе 0
# Вернём [0, 1] — корректно

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

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

Скользящее окно: от O(n²) до O(n)

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

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

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

def max_sum(nums, k):
    max_s = 0
    for i in range(len(nums) - k + 1):
        s = sum(nums[i:i+k])
        max_s = max(max_s, s)
    return max_s

sum() внутри цикла — пересчитываем окно целиком на каждом шаге. O(n·k).


Скользящее окно:

def max_sum(nums, k):
    window = sum(nums[:k])
    max_s = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        max_s = max(max_s, window)
    return max_s

O(n) — один проход.

Идея: не пересчитываем окно заново. Добавляем новый элемент справа, убираем старый слева. Одно сложение и одно вычитание вместо k операций.

# [2, 1, 5] → сумма 8
# сдвиг: +1 -2 → [1, 5, 1] → сумма 7
# сдвиг: +3 -1 → [5, 1, 3] → сумма 9  ← максимум
# сдвиг: +2 -5 → [1, 3, 2] → сумма 6

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

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

🧩 Code Cleanup

Не пиши if len(lst) == 0 — Python умеет лучше

Типичный код от новичка:

if len(items) == 0:
    return

if len(items) > 0:
    process(items)

if len(result) != 0:
    return result

После:

if not items:
    return

if items:
    process(items)

if result:
    return result

Короче, читается как английский, работает для любого контейнера.

Почему это работает:

В Python пустые list, dict, set, str, tuple — все являются falsy. Непустые — truthy. Это не магия, а протокол __bool__ / __len__.

bool([])   # False
bool([1])  # True
bool({})   # False
bool("")   # False
bool("x")  # True

Ловушка — не путай с None:

items = []

if items is not None:  # True — список существует, просто пустой
    ...

if items:              # False — список пустой
    ...

Если функция может вернуть None или пустой список — это разные случаи. Проверяй осознанно.

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

⏱️ Big O Breakdown

dict.get() vs dict[]. Где прячется исключение

Какова сложность этих двух операций?

d = {"a": 1, "b": 2}

x = d["c"]
y = d.get("c", 0)

Варианты:
А) Оба O(1)
Б) d["c"] — O(n), d.get() — O(1)
В) Оба O(n)
Г) d.get() — O(n), d["c"] — O(1)

Ответ: А) Оба O(1)

По сложности — одинаковы. Оба обращаются к хеш-таблице. Разница не в скорости, а в поведении.

d["c"] бросает KeyError если ключа нет. d.get("c", 0) возвращает дефолтное значение.

Где это реально важно:

# Подсчёт частоты — rookie вариант
counts = {}
for word in words:
    if word not in counts:
        counts[word] = 0
    counts[word] += 1

# Чище через get()
for word in words:
    counts[word] = counts.get(word, 0) + 1

# Ещё лучше — defaultdict
from collections import defaultdict
counts = defaultdict(int)
for word in words:
    counts[word] += 1

Все три варианта — O(n). Но читаемость и лаконичность разные.

Ловушка:

d.get("key")  # вернёт None если ключа нет
d.get("key", [])  # осторожно — [] создаётся каждый раз заново

Если дефолт — мутабельный объект и нужно его модифицировать, используй defaultdict — он создаёт дефолт один раз per key.

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

RESTful — API, реализующее принципы REST.

Основные идеи

🔹 Ресурсы вместо действий
/users/1 — ресурс

🔹 Использование HTTP-методов по назначению
GET, POST, PUT/PATCH, DELETE

🔹 Stateless — сервер не хранит состояние клиента

🔹 Единый и предсказуемый интерфейс

Итог: RESTful — это API, где операции выполняются над ресурсами через стандартные HTTP-механизмы.

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