❌ Rookie Mistakes: except ловит не то, что кажется

try:
    config = load_config()
    value = config["timeout"]
    result = process(value)
except KeyError:
    print("В конфиге нет ключа timeout")
    result = default_result()

Логика ясная: если в конфиге нет timeout — берём дефолт. Но однажды process внутри себя тоже кинет KeyError — по совсем другой причине. И этот блок его проглотит, напечатав неверное сообщение.

Почему это ошибка
except KeyError ловит любой KeyError, возникший где угодно в блоке try — не только тот, что ты имел в виду.

try:
    config = load_config()
    value = config["timeout"]      # ← ждём KeyError отсюда
    result = process(value)        # ← а он прилетит ОТСЮДА
except KeyError:                   # ловит оба, не различая
    ...

Если process внутри обратится к несуществующему ключу словаря — вылетит KeyError, но не про timeout. А обработчик уверенно скажет «нет ключа timeout» и подсунет дефолт. Настоящий баг в process замаскирован, сообщение врёт, отладка превращается в ад.

Суть ошибки: try обнимает слишком много кода. Чем больше строк под ним, тем выше шанс, что тип исключения совпадёт случайно, не по той причине.

Исправленный вариант
Оборачивай в try ровно ту строку, чьё исключение ты ждёшь:

config = load_config()

try:
    value = config["timeout"]      # только эта строка
except KeyError:
    print("В конфиге нет ключа timeout")
    value = 30

result = process(value)            # его ошибки НЕ ловятся здесь

Теперь KeyError из process полетит наверх — как и должен, с честным трейсбеком.

А для «достать значение с дефолтом» вообще не нужен try:

value = config.get("timeout", 30)   # ключа нет → 30, без исключений
result = process(value)

Общее правило узкого try

широкий try:   try { A; B; C } except E   ← E от A, B или C — не различить
узкий try:     try { B } except E          ← точно знаем: это про B

Держи под try минимум строк — только те, где ожидаешь конкретную ошибку. Всё остальное выноси наружу.

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

⚖️ This vs That: list vs tuple

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

Что делает list
Изменяемая последовательность. Можно добавлять, удалять, менять элементы:

items = [1, 2, 3]
items.append(4)
items[0] = 99      # ок

Что делает tuple
Неизменяемая последовательность. После создания — только чтение:

point = (1, 2, 3)
point[0] = 99      # TypeError: 'tuple' object does not support item assignment

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

— изменяемый,

tuple

— нет. Но следствия из этого важнее самого факта.

Следствие 1: хешируемость
Кортеж можно использовать как ключ словаря и элемент множества. Список — нельзя:

cache = {(1, 2): "результат"}     # ок
cache = {[1, 2]: "результат"}     # TypeError: unhashable type: 'list'

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

Это главная практическая причина брать кортеж — координаты, составные ключи, пары в set.

Следствие 2: смысл, а не только форма
Есть негласная семантическая конвенция:

list   →  однородная коллекция ПЕРЕМЕННОЙ длины
          [user1, user2, user3] — «много одинакового»

tuple  →  фиксированная структура, где важна ПОЗИЦИЯ
          (x, y) — координата; (name, age, city) — запись

Поэтому функции возвращают кортежи: return name, age — это одна структура из разных по смыслу полей, а не «список из двух штук».

Следствие 3: память и скорость
Кортеж знает свой размер навсегда — ему не нужен запас под рост:

list:  выделяет память С ЗАПАСОМ под будущие append
tuple: ровно под n элементов

Отсюда кортеж компактнее и чуть быстрее в создании/обходе. На миллионах мелких записей разница заметна.

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

📈 From O(n log n) to O(n)

Задача
Дан массив из n чисел. Верни k наибольших. Обычно k сильно меньше n (топ-10 из миллиона).

Наивное решение
«Отсортирую и возьму хвост.»

def top_k(nums, k):
    return sorted(nums, reverse=True)[:k]

Коротко и корректно. Но сложность — O(n log n): мы упорядочили весь массив, хотя нужны всего k элементов.

Проблема
Мы делаем гораздо больше работы, чем требует задача. Порядок остальных n − k элементов нас не интересует вообще — а мы за него заплатили.

Оптимизированное решение
Куча (heap) размера k. Держим min-heap ровно из k элементов — текущего топа. Новый элемент сравниваем с минимумом кучи: если он больше — минимум вылетает, новый заходит.

import heapq

def top_k(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)              # O(k)
    for x in nums[k:]:
        if x > heap[0]:              # heap[0] — минимум кучи, O(1)
            heapq.heapreplace(heap, x)   # выкинуть min, вставить x: O(log k)
    return heap

Сложность: O(n log k). Когда k мало и почти константа — это фактически O(n).
По памяти — O(k) вместо O(n) на копию для сортировки. Важно, если данные идут потоком и не влезают в память целиком.

Объяснение
Min-heap — структура, где минимум всегда на вершине и доступен за O(1). Это ровно то, что нужно: «самый слабый в топе» — кандидат на вылет.
Трассировка nums = [3, 1, 5, 12, 2, 11], k = 3:

куча из первых 3:  [1, 3, 5]        min = 1

x=12:  12 > 1  → выкидываем 1  → [3, 12, 5]    min = 3
x=2:   2 < 3   → пропускаем     → [3, 12, 5]
x=11:  11 > 3  → выкидываем 3  → [5, 12, 11]   min = 5

топ-3: [5, 12, 11]

Куча в любой момент содержит k лучших из просмотренного. Элементы меньше текущего минимума отбрасываются мгновенно, за одно сравнение.

В стандартной библиотеке это уже завёрнуто:

heapq.nlargest(k, nums)     # то же самое, готовое

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

🎭 Red Flag: изменение списка, по которому идёт цикл

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

def remove_inactive(users):
    for user in users:
        if not user.is_active:
            users.remove(user)      # удаляем прямо во время итерации


users = [alice, bob, carol, dave]   # bob и carol неактивны
remove_inactive(users)
print([u.name for u in users])      # ['alice', 'carol', 'dave']  ← carol выжила!

Код выглядит очевидно правильным. Но неактивный carol остался в списке. И — что коварно — никакой ошибки не было. Просто тихо неверный результат.

Что не так
Итератор списка ходит по индексам, а не по элементам «логически». Он помнит: «я на позиции i». Когда ты удаляешь элемент — все, что правее, сдвигаются влево, и следующий элемент проскакивает мимо.

users: [alice, bob, carol, dave]
         i=0    i=1    i=2    i=3

i=1: bob неактивен → remove(bob)
     список сдвинулся:
     [alice, carol, dave]
              ↑
     а итератор идёт на i=2 → это dave, НЕ carol
     carol пропущена!

Удалил элемент → сосед занял его место → итератор перешагнул через соседа. Каждое удаление «прячет» следующий элемент от проверки.
Со словарём и множеством такое хотя бы честно падает с RuntimeError. А список молчит и возвращает мусор — это опаснее всего: баг проходит тесты на «удобных» данных и стреляет в проде.

Как надо
Не мутируй то, что перебираешь. Построй новый список из того, что нужно оставить:

def remove_inactive(users):
    return [user for user in users if user.is_active]

Если по контракту надо изменить тот же объект (на него есть ссылки снаружи) — перезапиши его содержимое срезом:

def remove_inactive(users):
    users[:] = [user for user in users if user.is_active]   # мутируем на месте, но безопасно


users[:] = ... заменяет содержимое существующего списка — ссылки снаружи увидят изменение, но итерации по живому списку во время удаления нет.
Ещё вариант, если очень нужен цикл, — итерируйся по копии, а меняй оригинал:

for user in list(users):        # копия ключей/элементов
    if not user.is_active:
        users.remove(user)

Когда исходный подход не сломается
Практически никогда для удаления. Единственный безопасный способ менять список в цикле — идти с конца по индексам, тогда сдвиг не задевает ещё не пройденные позиции:

for i in range(len(users) - 1, -1, -1):
    if not users[i].is_active:
        del users[i]

Но это менее читаемо, чем comprehension. Comprehension почти всегда лучше.

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

⏱️ Big O Breakdown: рекурсивный Фибоначчи

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Классика из учебника. Выглядит элегантно. n — входное число.

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


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

Три строки кода, а под ними — экспоненциальный взрыв.

Разбор
Каждый вызов fib(n) порождает два новых вызова: fib(n-1) и fib(n-2). Те — ещё по два. Дерево вызовов удваивается на каждом уровне.

                fib(5)
              /        \
         fib(4)        fib(3)
challenged /    \       /    \
     fib(3)  fib(2)  fib(2) fib(1)
      /  \    /  \    /  \
    ...  ... ...  ... ... ...

Глубина дерева — примерно n, а на каждом уровне число вызовов удваивается → всего порядка 2ⁿ вызовов. Для fib(50) это больше триллиона вызовов. Программа зависнет.

Где именно взрыв

Смотри на дерево: fib(3) считается дважды, fib(2) — трижды. Мы решаем одни и те же подзадачи снова и снова, с нуля. Вот источник экспоненты — не сама рекурсия, а повторный пересчёт.

fib(2) вызывается: в fib(4) и в fib(3) и ещё... — многократно
каждый раз считается заново, хотя ответ один и тот же

Как починить — мемоизация
Запоминаем уже посчитанное. Каждое fib(k) считается один раз:

from functools import cache

@cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Теперь каждое из n значений вычисляется единожды → O(n) время.

без кэша:  каждая подзадача считается многократно  →  O(2ⁿ)
с кэшем:   каждая подзадача считается один раз      →  O(n)

Одна строка cache превращает триллион вызовов в n.
Или итеративно, двумя переменными — и O(1) памяти вместо стека рекурсии:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

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

❌ Rookie Mistakes: list *= n с вложенными списками

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

❌ Ошибка

matrix = [[0] * 3] * 3

matrix[0][1] = 1

print(matrix)

🤔 Ожидание

[
    [0, 1, 0],
    [0, 0, 0],
    [0, 0, 0]
]

💥 Реальность

[
    [0, 1, 0],
    [0, 1, 0],
    [0, 1, 0]
]

🧠 Почему так?

Оператор * не создаёт новые вложенные списки.
Он копирует ссылку на один и тот же объект.
В итоге все строки матрицы указывают на один список.

✅ Правильно

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

matrix[0][1] = 1

print(matrix)

⚡️ Вывод
Если создаёшь вложенные списки, не используй * для внешнего списка.
[[0] * n for _ in range(n)] — безопасный вариант, который должен войти в привычку.

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

🧰 Code Cleanup: «Не используй list(), если можно сразу создать список»

❌ Плохой код

result = list()

for i in range(10):
    result.append(i * i)

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

result = [i * i for i in range(10)]

💥 Объяснение
В первом варианте список создаётся пустым, а затем постепенно заполняется.
Во втором сразу видно, что именно должно получиться.

⚡️ Правило
Если задача — создать новый список, а не изменять существующий, используй list comprehension. Код становится компактнее и легче читается.

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

🧠 Interview Thinking: «Не оптимизируй то, что не является проблемой»

📌 Задача
Проверить, является ли строка палиндромом.

👶 Как думает junior
Сразу пишет решение с двумя указателями:

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

«Так эффективнее.»

🧠 Как думает сильный кандидат
Сначала оценивает задачу.
Если дополнительных требований нет, решение может быть намного проще:

def is_palindrome(s):
    return s == s[::-1]

А затем добавляет:

«Если бы интервьюер запретил дополнительную память, тогда я бы использовал два указателя.»

🎯 Что хочет интервьюер
Не увидеть самое сложное решение.
А понять, что ты умеешь выбирать инструмент под условия задачи, а не писать сложный код "на всякий случай".

💡 Вывод
Сильный кандидат сначала ищет самое простое корректное решение.
И только потом усложняет его, если этого требуют ограничения.

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

📈 From O(n²) to O(n): Проверка на дубликаты

📌 Задача
Определить, есть ли в списке повторяющиеся элементы.

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

def has_duplicates(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

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

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

def has_duplicates(nums):
    seen = set()

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

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

💥 Что изменилось?
Вместо сравнения каждого элемента со всеми остальными мы запоминаем уже встреченные значения в set.
Проверка наличия в множестве выполняется за O(1).

⚡️ Вывод
Если задача сводится к вопросу:

«Встречался ли этот элемент раньше?»

Первым делом подумай о set. Это один из самых частых способов превратить O(n²) в O(n).

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

🧰 Code Cleanup: «Убери дублирование условия»

❌ Плохой код

def get_discount(user):
    if user.is_premium and user.age >= 18:
        return 20
    elif user.is_premium and user.age < 18:
        return 10
    else:
        return 0



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

def get_discount(user):
    if not user.is_premium:
        return 0

    return 20 if user.age >= 18 else 10



💥 Что изменилось?
В исходном коде user.is_premium проверяется дважды.
Сначала разбираемся с исключением:
if not user.is_premium:
return 0
После этого можно спокойно работать только с премиум-пользователем.

⚡ Правило
Если одно условие повторяется в нескольких ветках — попробуй вынести его раньше и сделать ранний return.
Меньше вложенности → меньше кода → проще читать

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

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

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

a = [10, 20, 30, 40]
b = [5, 30, 70, 90]

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

def has_common(a, b):
    for x in a:
        for y in b:
            if x == y:
                return True
    return False

Сложность: O(n × m)
Каждый элемент a сравнивается со всеми элементами b.

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

def has_common(a, b):
    values = set(b)

    return any(x in values for x in a)

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

💡 Главный инсайт

Мы не ускорили вложенный цикл.
Мы вообще от него избавились.

Вместо:

«Сравни этот элемент со всеми»

делаем:

«Проверь, встречался ли он в

set

».

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

🧠 Interview Thinking

📌 Задача

Есть список:

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

Найти второй по величине уникальный элемент.

Ответ:

5

👶 Как думает junior

Сразу сортирует:

def second_max(nums):
    return sorted(set(nums))[-2]

Работает

Но сильный кандидат сначала спросит:

«Можно ли использовать дополнительную память?»

Если нельзя — это решение уже не подходит.

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

Проходит список один раз и хранит только два значения:

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

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

    return second

Сложность: O(n) по времени и O(1) по памяти

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

📈 From O(n²) to O(n): Подсчёт частоты элементов

📌 Задача
Найти элемент, который встречается чаще всего в списке.

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

def most_frequent(nums):
    max_count = 0
    result = None

    for num in nums:
        count = nums.count(num)

        if count > max_count:
            max_count = count
            result = num

    return result

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

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

from collections import Counter

def most_frequent(nums):
    return Counter(nums).most_common(1)[0][0]

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

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

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

🧠 Interview Thinking

📌 Задача

Проверить, содержит ли список дубликаты.

👶 Как думает junior

def has_duplicates(nums):
    return len(nums) != len(set(nums))

Работает. На этом объяснение заканчивается.

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

def has_duplicates(nums):
    seen = set()

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

И сразу объясняет:

«Я использую

set

, потому что проверка наличия элемента выполняется в среднем за

O(1)

. Кроме того, функция завершится сразу после нахождения первого дубликата, не проходя весь список.»

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

Не просто увидеть set.
Он хочет понять, почему ты выбрал именно его, а не список, словарь или сортировку

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

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

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