В множество (set) можно помещать только hashable (хешируемые) объекты.

Требования

🔹 объект имеет __hash__()
🔹 объект неизменяемый (immutable)
🔹 корректно реализует __eq__()

Можно

🔹 int, float, str, bool
🔹 tuple (если внутри тоже hashable)
🔹 frozenset

Нельзя

🔹 list
🔹 dict
🔹 set

(они изменяемые → нет стабильного хеша)

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

🧰 Code Cleanup

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

❌ Плохой код

def get_active_users(users):
    result = []

    for user in users:
        if "is_active" in user:
            if user["is_active"]:
                result.append(user["name"])

    return result

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

def get_active_users(users):
    return [user["name"] for user in users if user.get("is_active")]

💥 Объяснение

В первом варианте происходит лишнее:

👉 Ты сначала проверяешь наличие ключа
👉 Потом сразу используешь его же

Это дублирование логики.

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

🧠 Interview Thinking

Классическая задача.
Но валятся здесь не из-за кода — а из-за мышления.

📌 Задача

Дана строка:

s = "leetcode"

Нужно вернуть индекс первого уникального символа.
Если нет — вернуть -1.

👶 Как думает junior

def first_unique(s):
    for i in range(len(s)):
        if s.count(s[i]) == 1:
            return i
    return -1

На первый взгляд — логично.

👉 Проверяем каждый символ
👉 Если встречается 1 раз — возвращаем индекс

💥 Проблема

Метод count() — это O(n)

А он вызывается внутри цикла.

👉 Итог: O(n²)

На маленьких строках — ок
На больших — просадка


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

from collections import Counter

def first_unique(s):
    freq = Counter(s)

    for i, char in enumerate(s):
        if freq[char] == 1:
            return i

    return -1

🚀 Что изменилось

👉 Сначала считаем частоты → O(n)
👉 Потом один проход → O(n)

Итого: O(n)

⚠️ Но дело не только в оптимизации

Сильный кандидат:

🔷 сразу проговаривает сложность
🔷 замечает повторные операции
🔷ищет способ вынести их из цикла


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

Не просто решение.

А чтобы ты сказал:

«Здесь есть повторный подсчёт.
Я могу вынести его в отдельную структуру»

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

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

Задача простая.
Но именно здесь многие застревают в brute force.

📌 Задача

Дан массив чисел и число target.

Нужно найти два индекса, сумма элементов по которым равна target.

nums = [2, 7, 11, 15]
target = 9

Ответ: [0, 1]


❌ Наивное решение (brute force)

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

На маленьких массивах — нормально
На больших — боль

🧠 Ключевой вопрос

На первый взгляд кажется:
«Ну а как иначе? Надо же проверить все пары»

Но…

👉 А если мы будем помнить, что уже видели?

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

def two_sum(nums, target):
    seen = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

🚀 Что произошло

Мы заменили:

👉 «перебирать все пары»
на
👉 «проверять, встречали ли нужное значение раньше»


📉 Сложность

Один проход по массиву → O(n)
Поиск в словаре → O(1)

Итого: O(n)

⚠️ Где часто ошибаются

❌ Сначала добавляют в seen, потом проверяют
→ ловят кейс, где элемент используется дважды

Правильно:

👉 сначала проверка
👉 потом добавление

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

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

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

✅ Правильный ответ:
[1, 2, 3, 4]
[1, 2, 3, 4]

💥 Разбор

На первый взгляд кажется:

data += [4] создаёт новый список

Но это не так.

🧠 Что происходит на самом деле

Для списков:

data += [4]

👉 это мутация (аналог extend)
👉 объект изменяется на месте

А data и lst — это одна и та же ссылка.

⚠️ Где ловушка

Многие думают:

+= всегда создаёт новый объект

Но в Python:

для list → мутация
для tuple, str → новый объект

Один и тот же оператор — разное поведение.

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

🧰 Code Cleanup

На первый взгляд — нормальный код.
Но в нём скрытая неэффективность и шум.

❌ Плохой код

def group_by_type(items):
    result = {}

    for item in items:
        if item["type"] not in result:
            result[item["type"]] = []

        result[item["type"]].append(item)

    return result

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

from collections import defaultdict

def group_by_type(items):
    result = defaultdict(list)

    for item in items:
        result[item["type"]].append(item)

    return result

💥 Объяснение

В первом варианте:

👉 дважды обращаешься к item["type"]
👉 руками обрабатываешь инициализацию

Код работает, но перегружен лишними действиями.

🧠 Что здесь неочевидно

Многие думают:

«Ну это же стандартный паттерн»

На самом деле:

ты берёшь на себя работу, которую уже решил Python

⚠️ Где часто ошибаются

Пишут так «по привычке»:

if key not in dict:
    dict[key] = []

Хотя это почти всегда можно упростить.

⚡️ Маленькое правило

👉 Если собираешь значения в группы → смотри в сторону defaultdict
👉 Убирай повторные обращения к одним и тем же данным

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

⏱️ 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