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

t = ([1, 2], [3, 4])
t[0] += [5]

Варианты ответа:
A) t становится ([1, 2, 5], [3, 4]), ошибок нет
B) TypeError, t не меняется
C) TypeError, но t[0] всё равно становится [1, 2, 5]
D) SyntaxError — так писать нельзя

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

Разбор
t[0] += [5] — это не «магия», а синтаксический сахар для:

t[0] = t[0].__iadd__([5])

Первая часть, t[0].__iadd__([5]), отрабатывает штатно: список — мутируемый объект, __iadd__ меняет его на месте и возвращает ту же ссылку. На этом этапе t[0] уже физически стал [1, 2, 5].
Проблема — во второй части. Python пытается выполнить t[0] = ..., а t — кортеж, и __setitem__ у него просто не существует. Отсюда TypeError: 'tuple' object does not support item assignment.
Мутация уже случилась, откат назад никто не делает. Получаем на первый взгляд абсурдную ситуацию: код падает с ошибкой, но результат мутации остаётся.

Вывод
⚡️ += на изменяемом объекте внутри неизменяемой структуры — это два разных действия под одной строкой: in-place мутация и попытка присваивания. Первое может пройти успешно, второе — упасть. На собеседовании это отличный способ проверить, понимает ли кандидат разницу между __iadd__ и обычным __add__, а не просто заучил, что кортежи «неизменяемые».

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

🧰 Code Cleanup
Ручная мемоизация через словарь-аргумент

❌ Плохой код

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

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

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

💥 Краткое объяснение
memo={} — mutable default argument, тот самый классический баг-магнит: словарь создаётся один раз при определении функции и живёт между всеми вызовами. Работает это здесь случайно, а не потому что так задумано — стоит кому-то вызвать fib(5, {}) явно, и кэш перестанет работать без ошибки, просто молча.
lru_cache решает ту же задачу правильно: кэш живёт в самом декораторе, изолирован от сигнатуры функции и не тянется в аргументы, где ему не место. Плюс lru_cache умеет ограничивать размер кэша (maxsize) и даёт .cache_info() для отладки — попробуй получить это от самодельного словаря без лишнего кода.
Есть нюанс: lru_cache требует, чтобы аргументы были хешируемыми. Если функция принимает списки или словари — сначала понадобится обёртка или functools.cache не подойдёт вовсе, и это стоит держать в голове.

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

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

Задача
Дан список чисел и target. Нужно найти индексы двух элементов, сумма которых равна target. Гарантируется, что решение ровно одно.

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

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(1) по памяти.

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

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(n) по памяти.

💡 Что изменилось
Наивное решение на каждом шаге спрашивает «а есть ли где-то ещё число, дополняющее меня до target?» — и каждый раз отвечает на этот вопрос заново, перебором. Отсюда квадрат: n элементов × n элементов проверки.
Ключевая мысль оптимизации — не искать ответ, а помнить его. Вместо того чтобы на шаге i заново сканировать весь массив в поисках target - nums[i], мы один раз проходим по массиву и складываем уже увиденные числа в словарь. Тогда вопрос «встречалось ли нужное дополнение раньше?» превращается из линейного поиска в O(1) обращение к hash-таблице.
Это общий паттерн: если задача сводится к вопросу «видел ли я это (или что-то связанное с этим) раньше», почти всегда можно заменить вложенный цикл на один проход с dict или set. Цена — дополнительная память, но на собеседовании это почти всегда приемлемый trade-off, и его стоит проговорить вслух.

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

❌ Rookie Mistakes

Сортировка, которая возвращает None

❌ Код с ошибкой

def get_top_scores(scores):
    result = scores.sort(reverse=True)
    return result[:3]

🤔 Что ожидает новичок
Что sort() отсортирует список и вернёт его — как будто это просто ещё один способ вызвать sorted(). Логика понятная: метод называется «сортировка», значит должен отдать отсортированные данные.

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

TypeError: 'NoneType' object is not subscriptable


scores.sort(reverse=True) действительно сортирует список — но на месте, мутируя сам scores. А возвращает при этом None. В result попадает не список, а None, и result[:3] падает.

🧠 Почему
Это осознанное архитектурное решение Python, а не недосмотр. Методы, которые мутируют объект in-place (list.sort(), list.append(), list.reverse(), dict.update()), по конвенции возвращают None — это сигнал «я меняю существующий объект, а не создаю новый». Если бы sort() заодно и возвращал список, легко было бы перепутать: непонятно, работаешь ты с оригиналом или с копией.
Отсюда правило: функция либо мутирует и возвращает None, либо ничего не мутирует и возвращает новый объект. Смешивать эти два поведения в Python считается плохим тоном, и стандартная библиотека этому правилу следует последовательно.

✅ Исправление

def get_top_scores(scores):
    return sorted(scores, reverse=True)[:3]


sorted() — функция, а не метод списка. Она не трогает исходный scores и возвращает новый отсортированный список, который сразу можно использовать дальше.

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

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

📌 Задача

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

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

def is_anagram(s1, s2):
    if len(s1) != len(s2):
        return False

    for char in s1:
        if s1.count(char) != s2.count(char):
            return False

    return True

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

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

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

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

💡 Что изменилось?
Главная проблема — count().
Каждый его вызов проходит по всей строке. Когда он вызывается внутри цикла, сложность становится квадратичной.
Counter подсчитывает частоту символов за один проход, после чего остаётся лишь сравнить два словаря

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

🧠 Interview Thinking

📌 Задача

Найти максимальную сумму двух элементов массива

nums = [8, 3, 10, 5, 7]

👶 Как думает junior

«Нужно отсортировать массив.»

def max_pair_sum(nums):
    nums.sort()
    return nums[-1] + nums[-2]

Работает за O(n log n).

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

«Мне не нужен полностью отсортированный массив. Мне нужны только два максимальных элемента.»

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

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

    return first + second

Работает за O(n)

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

📈 От O(n log n) до O(n log k)

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

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

from collections import Counter

def top_k_frequent(words: list[str], k: int) -> list[str]:
    counts = Counter(words)
    ranked = sorted(counts.items(), key=lambda x: x[1], reverse=True)
    return [word for word, _ in ranked[:k]]

Сложность: O(n log n) — сортируем вообще все уникальные слова, хотя нужны только 5.

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

import heapq
from collections import Counter

def top_k_frequent(words: list[str], k: int) -> list[str]:
    counts = Counter(words)
    return [word for word, _ in heapq.nlargest(k, counts.items(), key=lambda x: x[1])]

Сложность: O(n log k) — куча размером k вместо полной сортировки.

💡 Что изменилось
Разница в том, что мы спрашиваем: «мне нужны все элементы отсортированными или только первые k?». sorted() — это решение первой задачи, а heap заточен именно под вторую.
heapq.nlargest внутри поддерживает кучу размером k: новый элемент либо выбрасывается сразу, либо вытесняет минимум из кучи. Если k мало по сравнению с n (а на практике почти всегда так), выигрыш ощутимый — сортировка миллиона элементов ради top-5 просто не нужна.
На больших данных (n = 10⁶, k = 5) наивное решение делает ~20 млн операций сравнения, куча — около 6.6 млн.

⚡️ Вывод
Как только видишь в задаче "top-K" — это сигнал think heap, а не sort. Спроси себя: нужен ли полный порядок или только первые k элементов. Если k << n, куча выигрывает почти всегда.

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

🧰 Group by без боли: defaultdict вместо ручных проверок

Классический код, который встречается почти в каждом втором проекте — группировка списка объектов по ключу.

❌ Плохой код

def group_orders_by_user(orders: list[dict]) -> dict[str, list[dict]]:
    grouped = {}
    for order in orders:
        user_id = order["user_id"]
        if user_id not in grouped:
            grouped[user_id] = []
        grouped[user_id].append(order)
    return grouped

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

from collections import defaultdict

def group_orders_by_user(orders: list[dict]) -> dict[str, list[dict]]:
    grouped = defaultdict(list)
    for order in orders:
        grouped[order["user_id"]].append(order)
    return dict(grouped)

💥 Краткое объяснение
Проблема первого варианта не в том, что он не работает, а в том, что он тратит логику на несуществующую задачу: «а вдруг ключа ещё нет». defaultdict берёт эту проверку на себя — при первом обращении к отсутствующему ключу он молча создаёт значение по умолчанию (в нашем случае пустой список) и продолжает работу.
Важный нюанс: defaultdict — это не просто синтаксический сахар, это отдельный тип со своим поведением при доступе через []. Если в конце функции ты возвращаешь grouped наружу как есть, у вызывающего кода могут появиться сюрпризы — любое обращение по несуществующему ключу тихо создаст новую пустую запись вместо KeyError. Поэтому в примере выше на выходе стоит dict(grouped) — это обрезает "magic"-поведение и отдаёт обычный dict.

⚡️ Одно правило
Используй defaultdict внутри функции для накопления данных, но на границе (return, экспорт наружу) всегда приводи к обычному dict — иначе поведение по умолчанию просочится туда, где его никто не ждёт.

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

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

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

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

Варианты ответа:
A) [0, 1, 2]
B) [2, 2, 2]
C) [0, 0, 0]
D) RuntimeError

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

Разбор
Интуитивно кажется, что каждая лямбда «запоминает» своё значение i в момент создания. Но это не так — лямбда не копирует значение, она захватывает саму переменную i по ссылке на её область видимости.
Все три лямбды в списке funcs смотрят на одну и ту же ячейку памяти — переменную i из окружающей функции (замыкание, closure). Цикл for не создаёт новую переменную на каждой итерации, он просто переиспользует одну и ту же i и меняет её значение. К моменту, когда мы реально вызываем f() в списковом включении, цикл уже завершён, и i равна последнему значению — 2.
Это называется late binding — тело функции обращается к переменной по имени в момент вызова, а не в момент определения.
Как исправить, если нужно зафиксировать значение на каждой итерации:

funcs = []
for i in range(3):
    funcs.append(lambda i=i: i)  # значение по умолчанию фиксируется сразу

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

Аргумент по умолчанию вычисляется один раз, в момент определения лямбды — поэтому такой трюк «замораживает» текущее значение i.

Вывод
Замыкания в Python захватывают переменные, а не их значения. Это всплывает везде, где создаются функции внутри циклов — от лямбд до обработчиков событий в GUI и async-калбэков. Если интервьюер спрашивает «что выведет этот код» с циклом и лямбдой — это почти всегда проверка именно на понимание late binding.

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

📈 От O(n²) до O(n)

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

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

def has_pair_with_sum(nums: list[int], target: int) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

Сложность: O(n²) — для каждого элемента перебираем все последующие.

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

def has_pair_with_sum(nums: list[int], target: int) -> bool:
    seen = set()
    for num in nums:
        if target - num in seen:
            return True
        seen.add(num)
    return False

Сложность: O(n) — один проход, поиск в множестве.

💡 Что изменилось
Ключевая идея — развернуть вопрос. Вместо «есть ли пара, дающая в сумме target» спрашиваем на каждом шаге: «я уже видел число, которое в паре с текущим даст target?». Это target - num.
Проверка in set работает в среднем за O(1) благодаря хеш-таблице под капотом, а не за O(n), как поиск в списке. Именно поэтому переход с list на set меняет асимптотику всей задачи, а не просто ускоряет константу.
Обрати внимание на порядок действий: сначала проверяем target - num in seen, потом добавляем num. Если поменять местами, для случая target == 2 * num алгоритм ошибочно сочтёт число парой самому себе.

⚡️ Вывод
Если в задаче фигурирует «найти пару/подмножество с определённой суммой» — это почти всегда сигнал заменить вложенный цикл на set или dict. Ищи не «как перебрать все пары», а «что нужно было увидеть раньше, чтобы текущий элемент завершил пару».

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

Ребят, запустил Telegram-канал с вакансиями для Python-разработчиков 🐍

Сейчас канал только начинает расти, поэтому хочу собрать первую аудиторию и постепенно привлечь больше работодателей.

Если вы Python-разработчик, подписывайтесь, чтобы не пропустить новые вакансии.

А если вы HR или занимаетесь наймом Python-разработчиков, просто возьмите канал на заметку. Возможно, скоро он вам пригодится 👀

t.me/python_work1

🧰 Читаемые условия: all()/any() вместо ручных флагов

Проверка «выполняется ли условие для всех/хотя бы одного элемента» — то место, где Python-код часто выдаёт бэкграунд разработчика.

❌ Плохой код

def all_users_verified(users: list[dict]) -> bool:
    is_all_verified = True
    for user in users:
        if not user["is_verified"]:
            is_all_verified = False
            break
    return is_all_verified

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

def all_users_verified(users: list[dict]) -> bool:
    return all(user["is_verified"] for user in users)

💥 Краткое объяснение
Первый вариант — это ручная реализация того, что уже есть в стандартной библиотеке, причём реализация не бесплатная: заводится промежуточный флаг, состояние которого нужно отслеживать, плюс явный break. Всё это — шум, который отвлекает от самой сути проверки.
all() принимает любой итерируемый объект и возвращает True, только если каждый элемент истинный. Важный нюанс: генератор (user["is_verified"] for user in users) вычисляется лениво — как только all() натыкается на первый False, он немедленно останавливается и не проходит по остальным элементам. То есть по производительности это тот же short-circuit, что и break в ручном варианте, только без явного управления состоянием.
Та же логика работает в обратную сторону: any() возвращает True, если истинен хотя бы один элемент, и тоже останавливается на первом совпадении.

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

🧠 Interview Thinking: найти первый неповторяющийся символ

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

find_first_unique("swiss")  # "w"

👶 Как думает junior
Для каждого символа проверить, сколько раз он встречается в строке — и как только нашли символ с count == 1, вернуть его.

def find_first_unique(s: str) -> str | None:
    for char in s:
        if s.count(char) == 1:
            return char
    return None

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

🧠 Как думает сильный кандидат
Сначала разделить задачу на две части: «посчитать частоту каждого символа» и «найти первый по порядку с частотой 1». Первую часть можно сделать за один проход, вторую — тоже за один, итого O(n) вместо O(n²).

from collections import Counter

def find_first_unique(s: str) -> str | None:
    counts = Counter(s)
    for char in s:
        if counts[char] == 1:
            return char
    return None

Здесь два прохода по строке — O(2n), что асимптотически всё равно O(n). Но важно не просто написать Counter, а объяснить, зачем нужен именно второй проход по s, а не по counts: Counter в Python 3.7+ сохраняет порядок вставки, но нам нужен порядок именно исходной строки, а не порядок первого появления в словаре — хотя на практике они совпадают, полагаться на это как на гарантию не стоит без проверки документации под конкретную версию.

🎯 Что хочет интервьюер
Не код с Counter сам по себе — это можно найти в любом решении на LeetCode. Интервьюер хочет услышать, что кандидат сам заметил скрытую стоимость s.count() внутри цикла, назвал её вслух и предложил trade-off: чуть больше памяти (хеш-таблица на все уникальные символы) в обмен на линейное время вместо квадратичного.
Хороший вопрос, который стоит задать в ответ: «а какого размера ожидается строка на входе» — если это заведомо короткие строки (пароли, коды), O(n²) может быть абсолютно приемлемым, и оверинжиниринг с Counter не всегда плюс.

💡 Вывод
Разница между junior и сильным кандидатом здесь не в знании Counter, а в привычке проверять код на скрытые вложенные проходы — count(), in list, index() внутри цикла почти всегда прячут лишнюю степень сложности.

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

❌ Rookie Mistakes

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

board = matrix.copy()
board[0][0] = 1

print(matrix[0])

🤔 Что ожидает новичок
board = matrix.copy() создаёт независимую копию — значит, изменение board никак не должно затронуть matrix.
Ожидаемый вывод:

[0, 0, 0]

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

[1, 0, 0]

Мы поменяли board, а изменился и matrix, хотя вроде бы сделали копию.

🧠 Почему
.copy() (как и срез matrix[:], и list(matrix)) делает shallow copy — поверхностную копию. Это значит, что копируется только внешний список, а вот его элементы копируются не по значению, а по ссылке.
matrix — это список списков. Внешний .copy() создаёт новый внешний контейнер, но каждый элемент внутри — это всё та же ссылка на тот же вложенный список, что и в оригинале. board[0] и matrix[0] — это буквально один и тот же объект в памяти, просто до него можно добраться двумя путями.
Проверить это легко:

print(board[0] is matrix[0])  # True
print(board is matrix)        # False

Внешние контейнеры — разные, внутренние — общие.

✅ Исправление
Для настоящей независимой копии вложенной структуры нужен deep copy:

import copy

board = copy.deepcopy(matrix)
board[0][0] = 1

print(matrix[0])  # [0, 0, 0] — не изменился

Для простого случая с числами внутри можно обойтись и без импорта copy, пересобрав вложенные списки вручную:

board = [row.copy() for row in matrix]

⚡️ Вывод
.copy() копирует только один уровень вложенности. Если внутри структуры есть изменяемые объекты (списки, словари) — они останутся общими между оригиналом и копией. Для многомерных структур default should be copy.deepcopy(), а не .copy().

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

📈 От O(n²) до O(n)

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

has_common(nums1=[1, 2, 3], nums2=[4, 5, 3])  # True

❌ Наивное решение
Для каждого элемента первого списка проверяем, есть ли он во втором.

def has_common(nums1: list[int], nums2: list[int]) -> bool:
    for a in nums1:
        for b in nums2:
            if a == b:
                return True
    return False

Сложность: O(n·m) — вложенный цикл, где для каждого элемента первого списка перебирается весь второй.

✅ Оптимизированное решение
Превращаем один из списков в множество и проверяем принадлежность.

def has_common(nums1: list[int], nums2: list[int]) -> bool:
    return not set(nums1).isdisjoint(nums2)

Сложность: O(n + m) — построение множества линейно, проверка через isdisjoint тоже линейна.

💡 Что изменилось
Здесь смена структуры данных меняет саму природу операции «проверить принадлежность». В списке она стоит O(n), потому что интерпретатор вынужден пройти по элементам один за другим. В множестве та же проверка — O(1) в среднем, потому что под капотом хеш-таблица сразу вычисляет, куда должен попасть элемент, без перебора.
Многие вместо isdisjoint пишут set(nums1) & set(nums2) и проверяют результат на пустоту — это тоже правильно по сложности, но isdisjoint быстрее на практике, потому что может остановиться на первом же совпадении и не обязан строить пересечение целиком, если второй аргумент — любой итерируемый объект, а не только множество.

⚡️ Вывод
Как только видишь «есть ли пересечение / общий элемент между двумя коллекциями» — это сигнал заменить вложенный цикл на set. Отдельно стоит запомнить isdisjoint — он часто выразительнее и быстрее, чем ручная проверка пересечения через &.

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

🧰 Code Cleanup: словарь вместо цепочки if/elif

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

❌ Плохой код

def handle_event(event_type: str, payload: dict) -> str:
    if event_type == "created":
        return f"Created: {payload['id']}"
    elif event_type == "updated":
        return f"Updated: {payload['id']}"
    elif event_type == "deleted":
        return f"Deleted: {payload['id']}"
    elif event_type == "archived":
        return f"Archived: {payload['id']}"
    else:
        return f"Unknown event: {event_type}"

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

HANDLERS = {
    "created": lambda p: f"Created: {p['id']}",
    "updated": lambda p: f"Updated: {p['id']}",
    "deleted": lambda p: f"Deleted: {p['id']}",
    "archived": lambda p: f"Archived: {p['id']}",
}

def handle_event(event_type: str, payload: dict) -> str:
    handler = HANDLERS.get(event_type)
    if handler is None:
        return f"Unknown event: {event_type}"
    return handler(payload)

💥 Краткое объяснение
Проблема цепочки if/elif не в производительности — на 4-5 условиях разницы почти нет. Проблема в том, что она плохо масштабируется: каждый новый тип события — это ещё одна ветка, вставленная куда-то в середину растущего блока, и с этим неудобно работать при code review, легко случайно сломать порядок проверок.
Словарь-диспетчер превращает набор веток в данные. Добавление нового типа события — это добавление одной строки в HANDLERS, а не правка ветвящейся логики. Поиск по ключу в словаре — O(1), так что при росте количества обработчиков (а не количества вызовов) производительность не деградирует, в отличие от if/elif, где в худшем случае приходится пройти все условия по очереди.
Отдельный плюс — HANDLERS можно тестировать и модифицировать независимо от функции handle_event, например регистрировать обработчики динамически из разных модулей.

⚡️ Одно правило
Если цепочка if/elif проверяет равенство одной и той же переменной разным константам — это структура "ключ → действие", и её почти всегда стоит превратить в словарь.

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

📈 От O(n·k) до O(n)

Задача: дан список чисел и число k, нужно найти максимальную сумму среди всех подряд идущих подмассивов длины k.

max_subarray_sum([2, 1, 5, 1, 3, 2], k=3)  # 9 (5+1+3)

❌ Наивное решение
Для каждой стартовой позиции суммируем k элементов заново.

def max_subarray_sum(nums: list[int], k: int) -> int:
    best = float("-inf")
    for i in range(len(nums) - k + 1):
        window_sum = sum(nums[i:i + k])
        best = max(best, window_sum)
    return best

Сложность: O(n·k) — для каждого из ~n стартовых окон заново пересчитываем сумму k элементов.

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

def max_subarray_sum(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best

Сложность: O(n) — сумма поддерживается инкрементально, каждый элемент обрабатывается один раз.

💡 Что изменилось
Ключевая идея — не пересчитывать то, что уже посчитано. Между соседними окнами [i, i+k) и [i+1, i+k+1) разница ровно в двух элементах: один уходит слева, другой добавляется справа. Наивное решение это игнорирует и каждый раз суммирует k элементов с нуля, хотя k-1 из них уже входили в предыдущую сумму.
Это классический sliding window — паттерн, который стоит узнавать сразу, как только видишь "подмассив/подстрока фиксированной или переменной длины" в условии задачи. Здесь окно фиксированного размера, поэтому обновление тривиальное: +nums[i] - nums[i-k]. Для окна переменного размера логика чуть сложнее (нужны два указателя, которые двигаются независимо), но идея та же — переиспользовать уже посчитанное состояние вместо пересчёта.

⚡️ Вывод
Если в задаче фигурирует "подряд идущие элементы" и надо посчитать что-то (сумму, среднее, количество уникальных) для каждого окна — думай sliding window, а не пересчёт с нуля на каждой позиции. Вопрос себе: что меняется между соседними окнами, и можно ли обновить результат инкрементально?

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

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

d = {1: 'a', True: 'b', 1.0: 'c'}

print(d)

Варианты ответа:
A) {1: 'a', True: 'b', 1.0: 'c'}
B) {1: 'c'}
C) {1: 'c', True: 'b'}
D) KeyError

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

Разбор
Ключи в словаре сравниваются не по типу, а по __hash__ и __eq__.
bool — подкласс int, поэтому True == 1, и hash(True) == hash(1). У float та же история: 1.0 == 1, и hash(1.0) == hash(1).
Для Python это три записи с одинаковым ключом. Каждая следующая просто перезаписывает значение по уже существующему хешу:

d = {}
d[1] = 'a'      # новый ключ
d[True] = 'b'   # ключ уже есть → перезаписываем значение
d[1.0] = 'c'    # ключ уже есть → перезаписываем значение

Важный нюанс: значение перезаписывается, а вот объект ключа — нет. CPython хранит тот ключ, который был вставлен первым. Поэтому в итоговом словаре ключ — это int(1), а не True и не 1.0, хотя последним «выигрывает» именно их значение.

Вывод
Если используешь int, bool и float как ключи словаря или элементы множества — они не так изолированы, как кажется. 1, True и 1.0 для хеш-таблицы это один и тот же ключ. На собеседовании это отличный способ проверить, понимает ли кандидат, что равенство и хеш решают, а не тип объекта.

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

🧠 Interview Thinking

Задача

Дан список интервалов [[1, 3], [2, 6], [8, 10], [15, 18]]. Нужно объединить все пересекающиеся интервалы.

👶 Как думает junior

Первая мысль — сравнить каждый интервал с каждым и сливать на лету.

def merge(intervals):
    result = intervals[:]
    merged = True
    while merged:
        merged = False
        for i in range(len(result)):
            for j in range(i + 1, len(result)):
                a, b = result[i], result[j]
                if a[0] <= b[1] and b[0] <= a[1]:
                    result[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    result.pop(j)
                    merged = True
                    break
            if merged:
                break
    return result

Работает. Но это O(n²) в среднем, а в худшем — и того хуже: мутация списка внутри вложенных циклов + перезапуск после каждого слияния.

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

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

def merge(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = result[-1][1]
        if start <= last_end:
            result[-1][1] = max(last_end, end)
        else:
            result.append([start, end])

    return result

O(n log n) за счёт сортировки, дальше — линейный проход без вложенных циклов и без мутации списка на лету.

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

Не код сам по себе. Интервьюер проверяет:

- заметил ли кандидат, что сортировка убирает необходимость сравнивать всё со всем;
- понимает ли, почему после сортировки достаточно смотреть только на соседа;
- задаёт ли уточняющие вопросы: интервалы закрытые или открытые? [1, 3] и [3, 5] — это пересечение или нет? может ли список быть пустым?
- готов ли явно назвать trade-off: сортировка стоит O(n log n), но избавляет от квадратичной сложности и лишней мутации.

💡 Вывод

Разница между junior и сильным кандидатом здесь не в синтаксисе, а в одном наблюдении: сортировка — это не «дополнительная работа», а способ превратить задачу «сравнить всё со всем» в задачу «сравнить с соседом». Это наблюдение стоит проговаривать вслух — интервьюер должен услышать ход мысли, а не увидеть готовый код.

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

📈 From O(...) to O(...)

Задача

Найти длину самой длинной подстроки без повторяющихся символов. Например, для "abcabcbb" ответ — 3 (`"abc"`).

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

Проверяем каждую подстроку на уникальность символов.

def longest_unique(s):
    n = len(s)
    best = 0
    for i in range(n):
        for j in range(i, n):
            window = s[i:j + 1]
            if len(set(window)) == len(window):
                best = max(best, len(window))
    return best

Сложность: O(n³) — O(n²) подстрок, и ещё O(n) уходит на set(window) для проверки каждой.

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

Скользящее окно + хеш-таблица, которая хранит последнюю позицию каждого символа.

def longest_unique(s):
    last_seen = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        best = max(best, right - left + 1)

    return best

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

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

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

Идея оптимизации: не пересчитывать, а поддерживать состояние. last_seen хранит, где в последний раз встретился каждый символ. Как только текущий символ повторяется внутри текущего окна, левая граница сразу прыгает за место его прошлого появления — без перебора символов между left и повтором.

Ключевой момент — right никогда не уменьшается, left тоже двигается только вперёд. Значит, суммарно оба указателя пройдут по строке не больше 2n раз, а не n².

⚡ Вывод

Как только видишь задачу вида «найти лучшее окно/подстроку/подмассив с условием» — первый вопрос должен быть не «как перебрать все варианты», а «что можно инкрементально поддерживать при сдвиге границы окна». В 90% случаев это словарь или множество с позициями/счётчиками, и он превращает перебор в один проход.

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