🎭 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

🧰 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