⏱️ Big O Breakdown

def process(matrix):
    result = []
    for row in matrix:
        for val in row:
            result.append(val)
    return result

matrix — это список из n элементов суммарно (например, 100 чисел, разбитых на строки разной длины).

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

A) O(n)
B) O(n²)
C) O(n · m)
D) Зависит от формы матрицы

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

Разбор

Глаз видит два вложенных цикла и автоматически кричит «O(n²)!». Это рефлекс, и он часто врёт.

Сложность считается не по количеству циклов, а по числу итераций относительно размера входа.

Здесь внутренний for val in row пробегает по элементам строки. А внешний — по строкам. В сумме мы касаемся каждого элемента ровно один раз.

Если всего элементов n — мы делаем n шагов. Это O(n).

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

📈 From O(n·k) to O(n)

Задача

Дан массив и число k. Для каждого окна длины k найти максимум.

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
→ [3, 3, 5, 5, 6, 7]

Наивное решение — O(n·k)

def max_sliding(nums, k):
    return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

Чисто, читаемо, проходит на маленьких данных.

Проблема: для каждого из n окон вызываем max(), который проходит по k элементам. Итого — O(n·k).

При n = 10⁶ и k = 10⁵ это уже 10¹¹ операций. Тесты упадут по таймауту.


Оптимизация — O(n) через deque

Идея: хранить в очереди индексы кандидатов на максимум. Поддерживать в ней убывающий порядок значений.

from collections import deque

def max_sliding(nums, k):
    dq = deque()  # индексы, значения по ним убывают
    result = []

    for i, n in enumerate(nums):
        # выбрасываем индексы, вышедшие за окно
        while dq and dq[0] <= i - k:
            dq.popleft()

        # выбрасываем всё, что меньше текущего — они никогда не станут максимумом
        while dq and nums[dq[-1]] < n:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Почему это O(n), а не O(n·k)?

На первый взгляд внутри for есть два while — кажется, что снова вложенность.

На самом деле каждый элемент попадает в очередь и выпадает из неё ровно один раз за всю работу алгоритма. Сумма всех итераций внутренних while — не больше 2n.

Это называется амортизированный анализ: смотрим не на худший шаг, а на суммарную работу.

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

Новая рубрика🔥🔥🔥:

⚖️ This vs That — «Это или то»
Сравнение похожих штук, между которыми все путаются

Мы стараемся для вас 💛

🔥 — если ждали новую рубрику

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

⚖️ This vs That: staticmethod vs classmethod

Оба — методы без self. Оба вызываются через класс. Разница ловится за 30 секунд, если понять одну вещь.

staticmethod — функция, которая просто живёт внутри класса

Не получает ни self, ни cls. Не знает ни про экземпляр, ни про класс. По сути — обычная функция, которую сложили в namespace класса для удобства.

class Temperature:

    @staticmethod

    def c_to_f(celsius):

        return celsius * 9/5 + 32

Temperature.c_to_f(100)  # 212

Если убрать staticmethod и вынести функцию наружу — ничего не сломается. Это и есть маркер.

classmethod — метод, который знает свой класс

Первым аргументом получает cls — сам класс. Это даёт две суперспособности:

1. Альтернативные конструкторы

class User:

    def __init__(self, name, age):

        self.name = name

        self.age = age

    @classmethod

    def from_dict(cls, data):

        return cls(data["name"], data["age"])

user = User.from_dict({"name": "Anna", "age": 30})

cls(...) вместо User(...) — важная деталь. Об этом ниже.

2. Корректная работа с наследованием

class Admin(User):

    pass

admin = Admin.from_dict({"name": "Bob", "age": 40})

print(type(admin))  # <class 'Admin'> ✅

Если бы внутри было return User(...) — Admin.from_dict(...) вернул бы User. Это классическая ошибка.

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

staticmethod — про группировку.

classmethod — про полиморфизм по классу.

Если методу не нужен ни self, ни cls — это staticmethod.

Если нужно создать объект *того же класса, что вызвал метод* — это classmethod.

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

🧰 Code Cleanup

Плохой код

def has_admin(users):
    found = False
    for user in users:
        if user.role == "admin":
            found = True
            break
    return found

Работает. Но это четыре строки там, где могла быть одна.

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

def has_admin(users):
    return any(user.role == "admin" for user in users)

Та же логика, тот же ранний выход (any ленивый — остановится на первом True), но без флага и break.

Зеркальный кейс — «все ли валидны»:

# было
all_valid = True
for item in items:
    if not item.is_valid():
        all_valid = False
        break

# стало
all_valid = all(item.is_valid() for item in items)

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

❌ Rookie Mistakes

Делаешь список функций — каждая должна возвращать своё число:

funcs = [lambda: i for i in range(3)]

print([f() for f in funcs])

Ожидаешь: [0, 1, 2]
Получаешь: [2, 2, 2]

Почему так

Лямбда не «запоминает» значение i в момент создания. Она запоминает саму переменную i. А переменная одна на всех.

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

Это называется late binding — переменные в замыкании резолвятся в момент вызова, а не определения.

Как правильно

Способ 1 — захватить значение через дефолтный аргумент:

funcs = [lambda i=i: i for i in range(3)]

Дефолты вычисляются в момент определения функции — i фиксируется.

Способ 2 — functools.partial:

from functools import partial
funcs = [partial(lambda x: x, i) for i in range(3)]

Вывод

Замыкания захватывают переменные, а не значения. Если в цикле создаёшь функции — всегда фиксируй переменную явно (x=x в аргументах или partial).

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

📈 From O(n) to O(1):

Задача

Дан массив. Приходят запросы вида «найди сумму элементов от индекса l до r включительно». Запросов много — тысячи или миллионы.

nums = [3, 1, 4, 1, 5, 9, 2, 6]
query(1, 4)  → 1 + 4 + 1 + 5 = 11
query(2, 6)  → 4 + 1 + 5 + 9 + 2 = 21

Наивное решение — O(n) на запрос

def query(nums, l, r):
    return sum(nums[l:r+1])

Один запрос — O(n). Тысяча запросов на массиве в миллион — 10⁹ операций. Сервер плачет.

Идея: один раз посчитать, дальше отвечать за O(1)

Префиксная сумма prefix[i] — это сумма всех элементов до индекса i.

nums   = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]

prefix[i] = сумма nums[0..i-1]. Длина — n + 1 (с нулём в начале для удобства).

Тогда сумма на отрезке [l, r] — это:

prefix[r+1] - prefix[l]

Из суммы «всё до r включительно» вычитаем «всё до l не включая». Остаётся ровно нужный отрезок.

Код

def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, n in enumerate(nums):
        prefix[i + 1] = prefix[i] + n
    return prefix

def query(prefix, l, r):
    return prefix[r + 1] - prefix[l]

Препроцессинг — O(n), один раз.
Каждый запрос — O(1).

На тысяче запросов вместо 10⁹ операций получаем n + 1000 — фактически линейное время.

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

🧠 Interview Thinking

Задача

Дана строка из скобок (), [], {}. Вернуть True, если они правильно сбалансированы.

"()[]{}"     → True
"([{}])"     → True
"(]"         → False
"([)]"       → False  ← коварный кейс
"((("        → False

Как думает junior

Сразу видит «надо считать скобки» и пишет:

def is_balanced(s):
    count = 0
    for ch in s:
        if ch in "([{":
            count += 1
        else:
            count -= 1
    return count == 0

Работает на "()()", ломается на "([)]" — там тоже баланс по числу, но порядок неправильный. Пройдёт по count == 0 и вернёт True. Бага.

Junior часто радуется, что счётчик сошёлся, и не замечает, что порядок закрытия имеет значение.

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

Сначала задаёт себе вопрос: «Что я вообще проверяю?»

Не баланс чисел. А то, что каждая закрывающая скобка совпадает с последней открытой того же типа.

Это «последняя открытая, первая закрытая» — классический LIFO. Значит — стек.

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

Логика:
- открывающую — кидаем в стек
- закрывающую — смотрим, что наверху стека: если не пара, или стек пуст → не сбалансировано
- в конце стек должен быть пуст (если остались незакрытые — тоже false)

Тонкие моменты, которые отличают сильного кандидата

Сильный сам проговаривает edge cases, не дожидаясь вопроса:

- пустая строка → True (стек пуст в конце ✅)
- только закрывающие ")))" → False (стек пуст)
- только открывающие "(((" → False (стек не пуст в конце)
- смешанные с другими символами? → уточняет у интервьюера: «А в строке могут быть буквы, или только скобки?»

Последнее — особенно ценно. Уточнение требований до кода — маркер инженерного мышления.

Что хочет интервьюер

Не код. Код — побочный продукт.

Интервьюер слушает, как ты приходишь к идее стека. Идеальный путь:

1. «Проверять баланс счётчиком — недостаточно, порядок важен»
2. «Мне нужно помнить, что было открыто последним»
3. «Структура „последний вошёл — первый вышел“ — это стек»
4. «В Python это просто list с append / pop»

Если ты пройдёшь этот путь вслух за 30 секунд — половина задачи решена ещё до первой строки кода.

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

🧰 Code Cleanup

Плохой код

def get_discount(user_type):
    if user_type == "regular":
        return 0
    elif user_type == "silver":
        return 5
    elif user_type == "gold":
        return 10
    elif user_type == "platinum":
        return 20
    else:
        return 0

Работает. Но каждый новый тип клиента — это +2 строки. И с каждым новым elif код всё дальше уезжает вправо.

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

DISCOUNTS = {
    "regular": 0,
    "silver": 5,
    "gold": 10,
    "platinum": 20,
}

def get_discount(user_type):
    return DISCOUNTS.get(user_type, 0)

Те же варианты, но:
- данные отделены от логики
- добавить новый тип = одна строка в словаре
- .get(..., 0) сам обрабатывает «дефолт», без else

А если нужно вызывать функции, а не возвращать значения?

Словарь умеет хранить и функции:

def handle_create(req): ...
def handle_update(req): ...
def handle_delete(req): ...

HANDLERS = {
    "create": handle_create,
    "update": handle_update,
    "delete": handle_delete,
}

def dispatch(action, req):
    handler = HANDLERS.get(action)
    if handler is None:
        raise ValueError(f"Unknown action: {action}")
    return handler(req)

Вместо if action == "create": handle_create(req) × N — одна строка диспетчеризации.

Когда `if/elif` всё-таки лучше

Не каждую цепочку нужно превращать в словарь. Оставляй if/elif, если:

- условия не равенство, а диапазоны или сложные проверки (age < 18, score >= 90)
- веток 2–3 — словарь будет оверкиллом
- логика веток разная по структуре (где-то return, где-то raise, где-то побочный эффект)

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

Новая рубрика🔥🔥🔥

🎭 Red Flag — «Антипаттерн»
Плохие практики, которые выглядят как нормальный код

Мы стараемся для вас и работаем улучшением контента 🎉

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

🎭 Red Flag

Знакомая картина:

def send_email(user, message, urgent=False, retry=False, log=False):
    ...

И в коде встречаешь такое:

send_email(user, msg, True, False, True)

Что здесь происходит — без подсказки IDE не разберёшь.

Почему это red flag

1. Невозможно читать на месте вызова.
Что значит True, False, True? Каждый раз нужно открывать сигнатуру функции.

2. Флаг почти всегда означает «функция делает две разные вещи».

def get_user(user_id, with_orders=False):
    user = db.query(...)
    if with_orders:
        user.orders = db.query(...)
    return user

Это не одна функция. Это две функции, склеенные булевым переключателем. Внутри неизбежно появляется if with_orders — ветвление логики на каждый вызов.

3. Флаги размножаются.
Сначала один. Потом with_addresses, with_payments, include_deleted. Через полгода у функции 6 булевых аргументов и матрица из 64 поведений, из которых протестированы 3.

Как надо

Способ 1 — разделить функцию на две.

def get_user(user_id): ...
def get_user_with_orders(user_id): ...

Каждая делает одну вещь. Имя сразу говорит, что получишь.

Способ 2 — keyword-only аргументы.

Если флаг всё-таки нужен, заставь вызывающего писать его по имени:

def send_email(user, message, *, urgent=False, retry=False):
    ...

send_email(user, msg, urgent=True, retry=False)  # ✅ читаемо
send_email(user, msg, True, False)               # ❌ TypeError

Звёздочка * запрещает позиционную передачу. Магия — на месте вызова всегда понятно, что значит каждое значение.

Способ 3 — Enum вместо булева.

Если флаг описывает не «да/нет», а выбор из вариантов — почти всегда это Enum, а не цепочка булевых:

# было
def render(template, html=False, json=False, xml=False): ...

# стало
class Format(Enum):
    HTML = "html"
    JSON = "json"
    XML = "xml"

def render(template, format: Format): ...

Невозможно случайно передать два формата сразу. Невозможно забыть выбрать формат. Расширяется без новых аргументов.

Когда булев флаг норм

Не каждый булев — зло. Флаг ок, если:

- он действительно бинарный по смыслу
- их немного (1, максимум 2)
- передаётся по имени: delete(path, force=True)

subprocess.run(..., check=True) — нормально. process_data(True, False, True, False) — катастрофа.

Правило

Каждый булев флаг в сигнатуре — это вопрос: *«а нельзя ли это разделить на две функции?»*

В половине случаев — можно. И код становится в разы понятнее.

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

⏱️ Big O Breakdown

def has_duplicates(items):
    seen = []
    for item in items:
        if item in seen:
            return True
        seen.append(item)
    return False

items — список длины n. Какая сложность?

A) O(n)
B) O(n log n)
C) O(n²)
D) O(n) в среднем

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

Разбор

Цикл идёт по n элементам — это O(n).

Внутри item in seen для списка — это линейный поиск. В худшем случае пробегает весь список, чтобы убедиться, что элемента нет. С ростом seen это 1 + 2 + 3 + ... + n ≈ n²/2 операций.

Итого — O(n²).

Глаз видит «один цикл», а на деле внутри in спрятан второй.

Маленькая правка — огромная разница

def has_duplicates(items):
    seen = set()           # ← вместо []
    for item in items:
        if item in seen:
            return True
        seen.add(item)     # ← вместо append
    return False

in для set — это O(1) в среднем (хеш-таблица).

Сложность падает с O(n²) до O(n).

На миллионе элементов — разница между «отработало за 0.1 сек» и «висит уже 10 минут».

Тонкий момент: почему «в среднем»?

set и dict устроены на хеш-таблицах. В среднем доступ — O(1). Но в худшем случае (катастрофические коллизии хешей) — O(n).

В реальной жизни этого почти не бывает — хеши в Python хорошо распределены, а словари автоматически расширяются. На собесе достаточно сказать: «O(1) amortized».

Вывод

Когда видишь x in collection — сразу спрашивай себя: что это за коллекция?

list / tuple   →  O(n)
set / dict     →  O(1) в среднем

Если коллекция используется только для проверки «есть ли элемент» — почти всегда нужен set, а не list. Это одна из самых дешёвых оптимизаций в Python: меняешь [] на set(), и код ускоряется на порядки.

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

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

Задача

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

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

Лучший подмассив: [4, -1, 2, 1]
Сумма:            6

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

Перебираем все возможные подмассивы и считаем сумму каждого:

def max_subarray(nums):
    best = nums[0]
    for i in range(len(nums)):
        current = 0
        for j in range(i, len(nums)):
            current += nums[j]
            best = max(best, current)
    return best

Два вложенных цикла → O(n²). На массиве в миллион элементов — 10¹² операций. Не вариант.

Идея Kadane'а — O(n)

Ключевой инсайт: в каждой точке нам нужно решить только один вопрос — продолжить текущий подмассив или начать новый с этого элемента?

Если сумма того, что мы накопили слева, отрицательная — она только утянет нас вниз. Лучше начать заново.

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

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

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

🧠 Interview Thinking

Задача

Дано целое n > 0. Вернуть True, если оно — степень двойки (1, 2, 4, 8, 16, ...).

Как думает junior

«Делим на 2, пока можем»:

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

Работает, O(log n). На собесе пройдёт. Но это «решение в лоб» — кандидат не задумался, есть ли что-то лучше.

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

Смотрит на двоичное представление:

1   = 0001
2   = 0010
4   = 0100
8   = 1000
16  = 10000

Степень двойки — это ровно один установленный бит. Все остальные числа имеют 2+ единицы.

Дальше — известный битовый трюк: n & (n - 1) сбрасывает самый правый установленный бит.

n     = 1000
n - 1 = 0111
n & (n-1) = 0000   ← если был один бит, всё стало нулём

Если n — степень двойки, после операции получится 0:

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

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

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

Какая сложность данного алгоритма?

words — список из n строк.

Разбор будет через 2 часа

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

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

Разбор

Строки в Python неизменяемые. result += word не «дописывает в конец» — это создание нового объекта строки, в который копируется и старое содержимое, и новое.
С каждой итерацией result всё длиннее, и каждое копирование становится дороже:

шаг 1: копируем 1 символ
шаг 2: копируем 2 символа
шаг 3: копируем 3 символа
...
шаг n: копируем n символов
Сумма: 1 + 2 + 3 + ... + n ≈ n²/2. Итого — O(n²).

Один цикл — а внутри незаметно вложен второй, в виде копирования.

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

🧰 Code Cleanup

Плохой код

def get_user_email(user):
    if user is not None:
        if user.is_active:
            if user.email:
                return user.email
            else:
                return None
        else:
            return None
    else:
        return None

Каждое условие — новый уровень вложенности. Логику нужно держать в голове до самого конца, чтобы понять, где что вернётся.

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

def get_user_email(user):
    if user is None:
        return None
    if not user.is_active:
        return None
    if not user.email:
        return None
    return user.email

То же самое, но плоско. Каждая проверка — отдельный пункт «не подходит → выходим». Основной путь функции виден сразу.

Это называется guard clauses — «охранные условия» в начале функции, которые отсекают всё лишнее.

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

1. Меньше отступов → меньше когнитивной нагрузки.
2. Основная логика в конце на нулевом уровне, а не закопана в три вложенности.
3. Легче добавить новую проверку — просто ещё один if в начале.
4. Легче читать сверху вниз: «не то — выход, не то — выход, всё ок — работаем».

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

🧠 Interview Thinking

Задача

Дан массив из n - 1 различных чисел в диапазоне от 1 до n. Одно число пропущено. Найти его.

nums = [3, 1, 5, 2]   (n = 5)
→ 4

Как думает junior

«Перебираю все числа от 1 до n и проверяю, какого нет»:

def find_missing(nums, n):
    for i in range(1, n + 1):
        if i not in nums:
            return i

Работает. Но i not in nums — это O(n), и мы делаем его n раз. Итого — O(n²).

На массиве в миллион чисел — таймаут.

Junior часто этим и ограничивается. Главный признак: он не проверил себя на сложность перед сдачей решения.

Как думает чуть более опытный кандидат

«Положу в set для быстрого поиска»:

def find_missing(nums, n):
    seen = set(nums)
    for i in range(1, n + 1):
        if i not in seen:
            return i

O(n) по времени, O(n) по памяти. Уже хорошо.

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

Замечает структуру задачи: числа — это арифметическая прогрессия.

Сумма всех чисел от 1 до n известна заранее: n * (n + 1) / 2.

Если из этой суммы вычесть сумму того, что есть в массиве — получится пропущенное число.

def find_missing(nums, n):
    return n * (n + 1) // 2 - sum(nums)

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

Альтернатива через XOR (если интервьюер давит)

Если массив большой и есть риск переполнения сумм (для других языков, не Python) — XOR:

def find_missing(nums, n):
    result = 0
    for i in range(1, n + 1):
        result ^= i
    for x in nums:
        result ^= x
    return result

a ^ a = 0, поэтому всё, что встретилось дважды (в обоих циклах), сократится. Останется только пропущенное число.

В Python переполнения нет — но знание этого трюка показывает, что ты видишь задачу шире языка.

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

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

Задача

Дан отсортированный массив и число target. Найти два числа, сумма которых равна target. Вернуть их индексы.

nums = [1, 3, 5, 8, 11, 14], target = 13
→ (1, 4)   # 3 + 11

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

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²).

И главное: мы не используем факт, что массив отсортирован. А это подсказка от интервьюера.

Идея двух указателей — O(n)

Заводим два индекса: один на начало, другой на конец. На каждом шаге смотрим сумму:

- сумма меньше target → нужно больше → двигаем левый вправо
- сумма больше target → нужно меньше → двигаем правый влево
- равна → нашли

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1
        else:
            right -= 1
    return None

Указатели идут навстречу — за один проход. O(n) по времени, O(1) по памяти.

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