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

Задача

Дан массив. Вернуть новый массив, где элемент i = произведение всех остальных элементов исходного.

nums = [1, 2, 3, 4]
→ [24, 12, 8, 6]
   │   │   │  └─ 1*2*3
   │   │   └──── 1*2*4
   │   └──────── 1*3*4
   └──────────── 2*3*4

Ограничение: нельзя использовать деление (например, общее произведение / nums[i]). И желательно — O(n) время, O(1) дополнительной памяти.

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

def product_except_self(nums):
    result = []
    for i in range(len(nums)):
        product = 1
        for j in range(len(nums)):
            if i != j:
                product *= nums[j]
        result.append(product)
    return result

Два вложенных цикла. Для каждого элемента считаем заново. Медленно.

Почему «через деление» — плохая идея

total = math.prod(nums)
return [total // n for n in nums]   # ❌

Проблема: если в массиве есть 0 — деление на ноль. И даже без нулей в задаче явно сказано «без деления» — это часть условия.

Идея — два прохода: префиксы и суффиксы
В каждой точке i нужны:
произведение всего слева от i
произведение всего справа от i
Перемножим — получим «всё, кроме i».

Первый проход — слева направо, копим произведение всех левее:

nums    = [1, 2, 3, 4]
left    = [1, 1, 2, 6]
           │  │  │  └─ 1*2*3
           │  │  └──── 1*2
           │  └──────── 1
           └────────── ничего слева

Второй проход — справа налево, домножаем на произведение всех правее:

nums          = [1,  2,  3, 4]
после left    = [1,  1,  2, 6]
после right   = [24, 12, 8, 6]
                 │   │   │  └─ 6 * 1 (ничего справа)
                 │   │   └──── 2 * 4
                 │   └──────── 1 * (3*4)
                 └──────────── 1 * (2*3*4)
def product_except_self(nums):
    n = len(nums)
    result = [1] * n

    # left pass
    left = 1
    for i in range(n):
        result[i] = left
        left *= nums[i]

    # right pass
    right = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right
        right *= nums[i]

    return result

O(n) время. И O(1) доп. памяти — массив result не считается, он сам ответ.

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

🧠 Interview Thinking

Задача
Строка — палиндром (читается одинаково слева и справа), если игнорировать регистр и все небуквенные символы.

"A man, a plan, a canal: Panama"  → True
"race a car"                       → False
" "                                → True

Как думает junior — O(n) время, O(n) память
«Очищу строку, потом переверну и сравню»:

def is_palindrome(s):
    cleaned = "".join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

Работает. Короткое, читаемое решение — на собесе его примут.
Но если интервьюер скажет «сделай без доп. строки» — нужен другой подход.

Как думает сильный кандидат — два указателя, O(1) памяти
Идея: два указателя — один с начала, второй с конца. Идут навстречу. Пропускаем небуквенные символы. Если буквы (в нижнем регистре) не совпали — не палиндром.

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

🎭 Red Flag

Открываешь чужой код и видишь:

# Увеличиваем счётчик на 1
counter += 1

# Проходим по списку пользователей
for user in users:
    # Если пользователь активен
    if user.is_active:
        # Отправляем письмо
        send_email(user)

Выглядит «документированно». На деле — это шум, который мешает читать.
Почему это red flag
Эти комментарии не дают никакой информации сверх кода. Любой, кто видит counter += 1, и так знает, что счётчик увеличивается. Комментарий повторяет код словами.

Хуже того:
1. Комментарии устаревают. Логика меняется — комментарий забывают обновить. И вот ты читаешь:

# Возвращаем True, если возраст >= 18
def is_adult(age):
    return age >= 21    # ❗️ изменили, комментарий не тронули

Доверие к комментариям падает. А плохой комментарий хуже отсутствующего — он вводит в заблуждение.

2. Они говорят «что», вместо «почему». Хороший комментарий объясняет причину, которую не видно из кода. Плохой — пересказывает синтаксис.

Как надо
Комментарий должен отвечать на вопрос, который код не объясняет:

# Плохо — пересказ кода
# Сортируем массив
nums.sort()

# Хорошо — объяснение причины
# Сортируем, потому что бинарный поиск ниже требует упорядоченности
nums.sort()
# Плохо
# Если retry_count больше 3, выходим
if retry_count > 3:
    break

# Хорошо
# Лимит ретраев такой же, как у внешнего API — больше нет смысла
if retry_count > 3:
    break

Хороший комментарий объясняет:
почему так сделано (а не «как»)
что важно знать при изменении этого кода
что было попробовано и почему не подошло
связь с внешним миром: тикеты, баги, ограничения API

Альтернатива комментариям — имена
Часто комментарий — это симптом плохого именования:

# было: непонятный код + объяснение
# x — количество дней до дедлайна
x = (deadline - today).days
if x < 7:
    notify(user)

# стало: код объясняет себя
days_until_deadline = (deadline - today).days
if days_until_deadline < 7:
    notify(user)

Хорошее имя переменной заменяет комментарий. Хорошее имя функции — тем более.

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

🧰 Code Cleanup

Плохой код

if status == "pending" or status == "processing" or status == "queued":
    show_loader()

if user_role == "admin" or user_role == "owner" or user_role == "superuser":
    grant_access()

Работает. Но переменная повторяется в каждом сравнении, оператор == — тоже. Глаза устают.

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

if status in {"pending", "processing", "queued"}:
    show_loader()

if user_role in {"admin", "owner", "superuser"}:
    grant_access()

То же самое, но переменная написана один раз. И сразу видно: проверяем принадлежность к набору.

Почему именно {...} (set), а не [...] или (...)
in работает для всех трёх. Но:
set — проверка за O(1)
tuple / list — проверка за O(n)

На двух-трёх элементах разницы не видно. На десяти и более — set ощутимо быстрее.

# нормально на маленьких наборах
if role in ("admin", "owner"):
    ...

# обязательно set при больших проверках
ALLOWED_ROLES = {"admin", "owner", "superuser", "auditor", "billing", ...}
if role in ALLOWED_ROLES:
    ...

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

🧠 Interview Thinking

Задача
Дан отсортированный массив (могут быть отрицательные). Вернуть массив квадратов элементов, тоже отсортированный.

nums = [-4, -1, 0, 3, 10]
→ [0, 1, 9, 16, 100]

Как думает junior — O(n log n)
«Возведу в квадрат, потом отсортирую»:

def sorted_squares(nums):
    return sorted(n * n for n in nums)

Работает. Просто. На собесе примут.
Но мы выбрасываем то, что массив уже отсортирован. Снова платим за сортировку «с нуля».

Как думает сильный кандидат — O(n)
Ключевой инсайт: самые большие квадраты — на краях. Минус сильно отрицательное число даёт большой квадрат, плюс сильно положительное — тоже.
Значит, кандидаты на «самый большой квадрат» — это left и right массива. Два указателя с краёв навстречу.
На каждом шаге сравниваем |nums[left]| и |nums[right]|, берём больший в квадрат и кладём в конец результата:

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1                          # пишем с конца

    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] ** 2
            left += 1
        else:
            result[pos] = nums[right] ** 2
            right -= 1
        pos -= 1

    return result

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

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

⏱️ Big O Breakdown

def reverse_via_insert(nums):
    result = []
    for n in nums:
        result.insert(0, n)
    return result


nums длины n.

Какая сложность?
A) O(n)
B) O(n log n)
C) O(n²)
D) Amortized O(n)

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

Разбор
Цикл крутится n раз — это O(n).
Но list.insert(0, x) — это O(n) для каждого вызова. Когда вставляешь в начало, все остальные элементы сдвигаются на одну позицию вправо. Чем длиннее список, тем больше сдвигов.

шаг 1:  сдвиг 0 элементов
шаг 2:  сдвиг 1 элемента
шаг 3:  сдвиг 2 элементов
...
шаг n:  сдвиг (n-1) элементов

Суммарно: 0 + 1 + 2 + ... + (n-1) ≈ n²/2 операций.
Снаружи код выглядит «один цикл, одна операция». А внутри прячется квадрат.

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

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

Задача
Дан список слов. Сгруппировать анаграммы вместе (слова из одних и тех же букв).

["eat", "tea", "tan", "ate", "nat", "bat"]

→ [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Наивное решение — O(n² · k)
Для каждого слова сравниваем со всеми остальными:

def group_anagrams(words):
    groups = []
    used = [False] * len(words)
    for i, w in enumerate(words):
        if used[i]:
            continue
        group = [w]
        for j in range(i + 1, len(words)):
            if not used[j] and sorted(w) == sorted(words[j]):
                group.append(words[j])
                used[j] = True
        groups.append(group)
    return groups

Где n — число слов, k — средняя длина слова. O(n² · k log k) — каждое сравнение через sorted стоит k log k.

Идея — общий ключ для анаграмм
Главный инсайт: у анаграмм есть одинаковая «нормальная форма».
Например — отсортированная строка букв:

"eat" → "aet"
"tea" → "aet"
"ate" → "aet"
"tan" → "ant"

Если использовать эту форму как ключ словаря, группировка становится одним проходом:

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))
        groups[key].append(w)
    return list(groups.values())

O(n · k log k) время — один проход, в каждой итерации сортировка слова.

Можно ещё лучше — O(n · k)
Заменяем сортировку на подсчёт частот букв. Кортеж из 26 чисел — это однозначная подпись анаграммы:

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        count = [0] * 26
        for ch in w:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(w)
    return list(groups.values())

Время — O(n · k). Сортировки нет, только подсчёт.

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

❌ Rookie Mistakes

Пишешь «безобидную» функцию, которая добавляет элемент:

def add_item(items, item):
    items.append(item)
    return items

my_list = [1, 2, 3]
new_list = add_item(my_list, 4)

print(my_list)   # [1, 2, 3, 4]   ❗️
print(new_list)  # [1, 2, 3, 4]

Функция выглядит как «вернуть новый список». А на деле она изменила оригинал.

Что произошло
В Python аргументы передаются по ссылке на объект. items внутри функции — это тот же самый список, что my_list снаружи. append мутирует его.
return items возвращает ту же ссылку. Поэтому new_list и my_list указывают на один объект.

my_list  ──┐
            ├──▶️ [1, 2, 3, 4]
new_list ──┘

Почему это коварно
Функция выглядит чистой — принимает аргументы, возвращает результат. Снаружи не видно, что она меняет вход.

И через полгода в коде:

items = [...]
result = process(items)        # мы не знали, что он мутирует items
items_for_other_use = items    # ❗️ items уже не тот, что был

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

Как правильно
Вариант 1 — не мутировать, создавать новое:

def add_item(items, item):
    return items + [item]      # ✅ новый список


+ создаёт новый список, оригинал не трогает.

Вариант 2 — явно копировать, если внутри нужны изменения:

def add_item(items, item):
    result = items.copy()
    result.append(item)
    return result

Вариант 3 — если изменение намеренно, выразить это в имени:

def append_in_place(items, item):    # имя говорит "меняю на месте"
    items.append(item)
    # ничего не возвращаем — это сигнал, что метод мутирующий

Так делают встроенные методы: list.sort() мутирует и возвращает None, а sorted() возвращает новый. Это конвенция.

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

🧠 Interview Thinking

Задача
Дан массив prices, где prices[i] — цена акции в день i. Купить можно один раз, продать — позже. Максимизируй прибыль. Если заработать нельзя — верни 0.
Как думает junior
«Переберу все пары: покупка i, продажа j > i.»

def max_profit(prices):
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            best = max(best, prices[j] - prices[i])
    return best

Работает. Но это O(n²) — на 10⁵ цен собес ляжет по таймауту.
Как думает сильный кандидат
Инсайт: я не ищу две точки одновременно.
Иду слева направо и на каждом дне задаю один вопрос:

«Если продаю сегодня — какая была лучшая цена покупки до этого?»

А это просто минимум среди предыдущих цен. Держу его в одной переменной.

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for price in prices:
        min_price = min(min_price, price)
        best = max(best, price - min_price)
    return best

O(n) время, O(1) память.

prices:   [7, 1, 5, 3, 6, 4]
min:       7  1  1  1  1  1
profit:    0  0  4  2  5  3   → best = 5

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

🔍 Under the Hood

Многие слышали «__slots__ экономит память». Но почти никто не может объяснить — почему и за счёт чего.

Как объект хранит атрибуты по умолчанию
У обычного экземпляра атрибуты лежат в словаре __dict__:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

p = Point(1, 2)
p.__dict__   # {'x': 1, 'y': 2}

Словарь гибкий — можно дописать p.z = 3 на лету. Но за гибкость платишь: dict держит хеш-таблицу с запасом под рост. На один маленький объект — сотни лишних байт.

Что меняет __slots__

class Point:
    __slots__ = ("x", "y")
    def __init__(self, x, y):
        self.x = x
        self.y = y

Теперь у экземпляра нет __dict__. Python заранее знает точный список атрибутов и раскладывает их по фиксированным ячейкам — как поля в C-структуре, а не как записи в словаре.

без slots:   p ──► __dict__ {'x':…, 'y':…}   (хеш-таблица с запасом)
со slots:    p ──► [ x ][ y ]                 (две ячейки впритык)

Разница на миллионах объектов — десятки процентов памяти. Плюс доступ к атрибуту чуть быстрее: не поиск по хешу, а смещение.

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

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

Задача
Дан массив целых nums и число k. Посчитай, сколько непрерывных подмассивов имеют сумму, равную k.
Пример: nums = [1, 2, 3], k = 3 → ответ 2 (это [1, 2] и [3]).

Наивное решение
Перебрать все пары «начало–конец» и просуммировать:

def subarray_sum(nums, k):
    count = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total == k:
                count += 1
    return count

Работает. Но это O(n²) — на больших массивах медленно.

Проблема
Мы заново складываем числа для каждого старта. Сумма куска [i..j] пересчитывается миллион раз, хотя её можно получить из накопленной суммы.

Оптимизированное решение
Идём один раз и копим префиксную сумму prefix (сумма всего слева).
Сумма куска [i..j] = prefix[j] − prefix[i−1].
Мы хотим, чтобы она равнялась k:

prefix[j] − prefix[i−1] = k
        →  prefix[i−1] = prefix[j] − k

То есть на каждом шаге вопрос один: «сколько раз раньше я уже встречал префикс, равный prefix − k?» Храним счётчик префиксов в словаре.

from collections import defaultdict

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = defaultdict(int)
    seen[0] = 1            # пустой префикс — для кусков с начала
    for num in nums:
        prefix += num
        count += seen[prefix - k]   # сколько начал дают сумму k
        seen[prefix] += 1
    return count

O(n) время, O(n) память.

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

⚖️ This vs That: copy() vs deepcopy()

Оба «копируют». Но между ними — целый класс багов, которые всплывают спустя недели.

Что делает copy() (поверхностная)
Создаёт новый внешний объект, но вложенные объекты не копирует — кладёт те же ссылки.

import copy

a = [[1, 2], [3, 4]]
b = copy.copy(a)

b[0].append(99)
print(a)   # [[1, 2, 99], [3, 4]]   ← задели оригинал!


b — новый список, но b[0] и a[0] — один и тот же внутренний список.

a ──► [ • , • ]
        │   │
        ▼   ▼
       [1,2] [3,4]
        ▲   ▲
        │   │
b ──► [ • , • ]      ← разные внешние, общие внутренние

Что делает deepcopy() (глубокая)
Рекурсивно копирует всё вложенное. Получаешь полностью независимый объект.

b = copy.deepcopy(a)
b[0].append(99)
print(a)   # [[1, 2], [3, 4]]   ← оригинал цел
a ──► [ • , • ] ──► [1,2] [3,4]
b ──► [ • , • ] ──► [1,2] [3,4]   ← всё своё, копии до самого дна

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

copy()

дублирует только верхний уровень.


deepcopy()

спускается до самого дна.

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

⏱️ Big O Breakdown

def dedup(items):
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

Убираем дубликаты, сохраняя порядок. n — длина items.

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

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

Разбор
Глаз цепляется за один цикл for и думает «O(n)». Но настоящая работа спрятана в x not in result.
in по списку — это линейный поиск. Python проходит элементы один за другим, пока не найдёт совпадение:

x not in result  →  до n сравнений

И это сравнение делается на каждой из n итераций:

итерация 1:  поиск среди 0 элементов
итерация 2:  поиск среди 1
итерация 3:  поиск среди 2
...
итерация n:  поиск среди n-1

всего: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2  →  O(n²)

Один видимый цикл, но in прячет второй внутри себя.

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

❌ Rookie Mistakes

counts = {"a": 0, "b": 3, "c": 0, "d": 5}

for key in counts:
    if counts[key] == 0:
        del counts[key]

Хотим выкинуть нулевые значения. Логика очевидна. А Python падает:

RuntimeError: dictionary changed size during iteration

Почему это ошибка
for key in counts не делает копию ключей. Он держит живой итератор по самому словарю. Как только ты удаляешь элемент — размер меняется, итератор обнаруживает это и аварийно останавливается.

читаем "a" → del "a" → размер изменился → 💥

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

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

🧰 Code Cleanup

Плохой код

groups = {}
for user in users:
    if user.city not in groups:
        groups[user.city] = []
    groups[user.city].append(user.name)

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

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

from collections import defaultdict

groups = defaultdict(list)
for user in users:
    groups[user.city].append(user.name)


defaultdict(list) сам создаёт пустой список при первом обращении к новому ключу. Проверка if ... not in исчезает — её делает сама структура.

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

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

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

Варианты:
A) [0, 1, 2]
B) [2, 2, 2]
C) [3, 3, 3]
D) [0, 0, 0]

Правильный ответ: B — [2, 2, 2]

Классика, на которой спотыкаются почти все.

Разбор
Кажется, что каждая лямбда «запоминает» своё i. На самом деле — нет.
Лямбда не сохраняет значение i. Она сохраняет ссылку на переменную i и смотрит на неё только в момент вызова, а не в момент создания.

создаём лямбды:   i крутится 0 → 1 → 2
                  все три лямбды ссылаются на одну и ту же i

вызываем f():     цикл давно закончился, i == 2
                  все три читают i  →  2, 2, 2

Это называется late binding: имя внутри замыкания разрешается поздно — при вызове.
К моменту f() цикл отработал полностью, и i навсегда застряла на последнем значении 2.

Как починить — «заморозить» значение
Передать i как аргумент со значением по умолчанию (оно вычисляется сразу, в момент создания функции):

funcs = [lambda i=i: i for i in range(3)]
print([f() for f in funcs])   # [0, 1, 2]

Теперь каждая лямбда несёт свою копию.

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

🧠 Interview Thinking

Задача
В массиве каждое число встречается дважды, кроме одного — оно встречается один раз. Найди его.
Пример: [4, 1, 2, 1, 2] → 4.

Как думает junior
«Посчитаю, сколько раз встречается каждое число, и верну то, у которого счётчик 1.»

from collections import Counter

def single_number(nums):
    counts = Counter(nums)
    for num, c in counts.items():
        if c == 1:
            return num

Корректно. O(n) время, но O(n) память — храним весь словарь.
На собесе после этого почти всегда летит вопрос: «А можешь без дополнительной памяти?»

Как думает сильный кандидат
Инсайт: тут просится XOR (^).
У XOR два свойства, которые решают задачу целиком:

x ^ x = 0      число, ксоренное само с собой, обнуляется
x ^ 0 = x      ксор с нулём ничего не меняет

А ещё XOR коммутативен — порядок не важен. Значит, если проксорить все числа подряд, каждая пара схлопнется в 0, и останется только одиночка:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4
from functools import reduce
from operator import xor

def single_number(nums):
    return reduce(xor, nums)

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

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

🎭 Red Flag

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

def get_config(path):
    try:
        with open(path) as f:
            return json.load(f)
    except Exception:
        pass
    return {}

Выглядит «надёжно»: что бы ни случилось — функция не упадёт, вернёт пустой конфиг. Программа продолжит работать.
Именно в этом и проблема.

Что не так
except Exception ловит всё подряд, а pass молча проглатывает. Ты теряешь информацию о том, что вообще пошло не так:

файла нет           → молчим, отдаём {}
битый JSON          → молчим, отдаём {}
опечатка в коде      → молчим, отдаём {}   ← а вот это уже баг!
нет прав на чтение   → молчим, отдаём {}

Все эти разные беды слиплись в один тихий «всё нормально». Приложение поедет на пустом конфиге, а настоящую причину ты будешь искать часами — потому что в логах пусто.
Хуже того: except Exception способна поймать KeyError/AttributeError от твоей же опечатки внутри try — и баг превратится в невидимку.

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

def get_config(path):
    try:
        with open(path) as f:
            return json.load(f)
    except FileNotFoundError:
        logging.warning("Конфиг %s не найден, беру дефолт", path)
        return {}
    except json.JSONDecodeError as e:
        logging.error("Конфиг %s битый: %s", path, e)
        raise          # это уже серьёзно — не глотаем

Теперь видно: чего ты ожидал (файла может не быть — ок) и что должно громко падать (битый JSON — это ошибка деплоя, а не норма).

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

⏱️ Big O Breakdown

def running_medians(stream):
    seen = []
    result = []
    for x in stream:
        seen.append(x)
        s = sorted(seen)
        result.append(s[len(s) // 2])
    return result

Для каждого нового числа считаем медиану по всему, что пришло. n — длина потока.

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

Правильный ответ: D — O(n² log n)
Почти все говорят C, забывая про логарифм от сортировки.

Разбор
Считаем по слоям.
Цикл крутится n раз. На каждой итерации внутри прячется sorted(seen):

итерация i:  сортируем список длины i  →  O(i · log i)

Суммируем по всем итерациям:

i=1:  1·log1
i=2:  2·log2
...
i=n:  n·log n

каждое слагаемое ≤ n·log n, а слагаемых n штук
→  всего ≤ n · (n log n)  =  O(n² log n)

Две ловушки сразу:

1) sorted внутри цикла   → лишний множитель n
2) сама сортировка       → лишний множитель log n

C (O(n²)) получился бы, будь внутри линейная операция (sum, max). Но сортировка дороже — отсюда log n сверху.

Где это легко прозевать
sorted(seen) — короткая строка, читается как «ну, отсортировали». Но она пересортировывает весь накопленный список заново на каждом шаге, хотя добавился всего один элемент.

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

⚖️ This vs That: is vs ==

Путают постоянно. А разница — фундаментальная, и на ней ловят на собесах.

Что делает ==
Сравнивает значения: «равны ли эти объекты по содержимому». Вызывает метод __eq__.

a = [1, 2, 3]
b = [1, 2, 3]
a == b      # True — содержимое одинаковое

Что делает is
Сравнивает идентичность: «это один и тот же объект в памяти». Сравнивает id(), никаких методов не зовёт.

a is b      # False — два разных списка, просто с одинаковым содержимым
a ──► [1, 2, 3]   id = 0xAAA
b ──► [1, 2, 3]   id = 0xBBB

a == b  →  сравнивает содержимое  →  True
a is b  →  сравнивает адреса      →  False

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

==

спрашивает «равны ли они?»,


is

— «это вообще один и тот же объект?».

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

📈 From O(n·m) to O(n+m)

Задача
Даны два отсортированных массива. Слей их в один отсортированный.
Пример: [1, 3, 5] и [2, 4, 6] → [1, 2, 3, 4, 5, 6].

Наивное решение
«Соединю и отсортирую — делов-то»

def merge(a, b):
    return sorted(a + b)

Работает, коротко. Но мы выбросили главное — то, что массивы уже отсортированы. sorted об этом не знает и сортирует с нуля: O((n+m)·log(n+m)).

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

Оптимизированное решение
Два указателя. Идём по обоим массивам одновременно, на каждом шаге берём меньший из текущих элементов.

def merge(a, b):
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    # один из массивов кончился — добиваем хвост второго
    result.extend(a[i:])
    result.extend(b[j:])
    return result

Каждый элемент трогаем ровно один раз → O(n+m) время.

Объяснение
Трассировка a = [1, 3, 5], b = [2, 4, 6]:

a: [1, 3, 5]     b: [2, 4, 6]
   i               j

1 ≤ 2  → берём 1, i→      result: [1]
3 > 2  → берём 2, j→      result: [1, 2]
3 ≤ 4  → берём 3, i→      result: [1, 2, 3]
5 > 4  → берём 4, j→      result: [1, 2, 3, 4]
5 ≤ 6  → берём 5, i→      result: [1, 2, 3, 4, 5]
a кончился → добиваем хвост b: [6]
                          result: [1, 2, 3, 4, 5, 6]

Указатели только движутся вперёд и никогда не откатываются — отсюда линейность.

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