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

def f():
    print(x)
    x = 10

x = 5
f()

Варианты:
A) 5
B) 10
C) None
D) UnboundLocalError

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

Снаружи x = 5 существует. А функция всё равно падает. Почему?

Разбор

Python определяет, локальная переменная или глобальная, не во время выполнения, а заранее — на этапе компиляции функции.
Правило: если внутри функции переменной где-то присваивают значение — она считается локальной на всю функцию целиком. С первой строки до последней.

def f():
    print(x)    # ← пытаемся прочитать x
    x = 10      # ← из-за этой строки x ЛОКАЛЬНА во всей f

Из-за x = 10 ниже Python ещё при компиляции решает: «x здесь локальная». Глобальная x = 5 для функции больше не видна — её заслонила локальная.
А на строке print(x) локальной x ещё не присвоили значение:

f() вызвана
   ↓
x объявлена локальной (из-за присваивания ниже)
   ↓
print(x) → читаем локальную x, которой ещё нет → 💥 UnboundLocalError

Ключевой момент: дело не в порядке строк сверху вниз. Даже если print(x) идёт первым — наличие присваивания где угодно в функции делает переменную локальной везде.

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

🧰 Code Cleanup

Плохой код

def get_handler(command):
    if command == "start":
        return start_game()
    elif command == "pause":
        return pause_game()
    elif command == "resume":
        return resume_game()
    elif command == "stop":
        return stop_game()
    else:
        return unknown_command()

Работает. Но это «лестница»: каждая новая команда — ещё два elif. И вся структура — однотипная: сравнили строку → вызвали функцию.

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

HANDLERS = {
    "start": start_game,
    "pause": pause_game,
    "resume": resume_game,
    "stop": stop_game,
}

def get_handler(command):
    handler = HANDLERS.get(command, unknown_command)
    return handler()

Соответствие «команда → функция» стало данными, а не кодом. Добавить команду — одна строка в словарь, а не новая ветка.

Объяснение
Длинный if/elif, который сравнивает одну и ту же переменную с разными значениями — это замаскированная таблица соответствий. А таблицу естественнее хранить в словаре.

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

🧠 Interview Thinking

Задача
Даны две строки. Определи, являются ли они анаграммами — то есть состоят из одних и тех же символов в одинаковом количестве.
Пример: "listen" и "silent" → True; "rat" и "car" → False.

Как думает junior
«Анаграммы — это одинаковый набор букв. Отсортирую обе строки и сравню.»

def is_anagram(s, t):
    return sorted(s) == sorted(t)

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

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

from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)

O(n) время. Counter строит словарь {буква: количество}, а == сравнивает их целиком.

Хочешь показать, что понимаешь, что под капотом, — можно и руками одним словарём:

def is_anagram(s, t):
    if len(s) != len(t):     # разной длины — точно не анаграммы
        return False
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in t:
        if ch not in counts:
            return False
        counts[ch] -= 1
        if counts[ch] == 0:
            del counts[ch]
    return not counts        # пусто → всё сошлось

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

🎭 Red Flag

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

def process(value):
    if type(value) == list:
        return [v * 2 for v in value]
    if type(value) == dict:
        return {k: v * 2 for k, v in value.items()}
    raise TypeError("неподдерживаемый тип")

Работает на обычных списках и словарях. Но проверка типа через type(x) == — хрупкая, и однажды она тихо тебя подведёт.

Что не так
type(x) == list проверяет, что тип — ровно list, и ничего больше. Наследников он не признаёт.

from collections import OrderedDict

d = OrderedDict(a=1, b=2)
type(d) == dict        # False !  — а ведь это словарь по сути
isinstance(d, dict)    # True


OrderedDict, defaultdict, Counter — все наследуют dict и ведут себя как словари. Но type(x) == dict их отвергнет, и твоя функция упадёт на совершенно валидных данных.
Это нарушает подстановку Лисков: подкласс должен работать везде, где работает базовый. type() == ломает этот принцип на ровном месте.

Как надо
isinstance проверяет «является ли x этим типом или его наследником» — то есть то, что обычно и нужно:

def process(value):
    if isinstance(value, list):
        return [v * 2 for v in value]
    if isinstance(value, dict):     # ловит и OrderedDict, и defaultdict
        return {k: v * 2 for k, v in value.items()}
    raise TypeError("неподдерживаемый тип")

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

⏱️ Big O Breakdown

def join_words(words):
    result = ""
    for word in words:
        result += word + " "
    return result

Склеиваем слова в одну строку. n — число слов (для простоты считаем их сопоставимой длины).

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

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

Один цикл, простое += — а под капотом квадрат.

Разбор
Главная ловушка: строки в Python неизменяемы. result += word не дописывает в существующую строку — он создаёт новую, копируя в неё всё старое содержимое плюс новый кусок.

result += word  →  на самом деле:  result = result + word
                                   (новая строка, копия всего)

А копирование строки длины k стоит O(k). На каждой итерации result всё длиннее:

итерация 1:  копируем строку длины ~1
итерация 2:  копируем длины ~2
итерация 3:  копируем длины ~3
...
итерация n:  копируем длины ~n

всего: 1 + 2 + 3 + ... + n  =  O(n²)

Строка переписывается заново снова и снова. Каждый символ из начала копируется десятки тысяч раз.

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

💾 Memory Footprint: чтение файла целиком vs построчно

def count_errors(path):
    lines = open(path).readlines()
    return sum(1 for line in lines if "ERROR" in line)

Считаем строки со словом ERROR в лог-файле. n — число строк в файле.

Какая сложность по ПАМЯТИ?
A) O(1)
B) O(log n)
C) O(n)
D) Зависит от числа ошибок

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

По времени тут честный O(n).

А вот по памяти — ловушка, которую почти не замечают.

Разбор
readlines() читает весь файл сразу и возвращает список всех строк:

readlines()  →  ["строка1\n", "строка2\n", ..., "строкаN\n"]
                 весь файл целиком лежит в памяти

Это список из n строк → O(n) памяти. На лог-файле в 10 ГБ программа просто упадёт с MemoryError, хотя нам нужно-то всего одно число — счётчик.
Ключевое наблюдение: нам не нужны все строки одновременно. Мы смотрим на каждую по разу и забываем. Зачем держать их все в памяти?

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

def count_errors(path):
    with open(path) as f:
        return sum(1 for line in f if "ERROR" in line)
readlines():  [строка1][строка2]...[строкаN]   ← всё в памяти, O(n)
итерация по f: строка → обработали → забыли    ← одна за раз, O(1)

В памяти в любой момент — одна строка.

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

💾 Memory Footprint: генератор vs списковое включение

nums = range(1_000_000)

a = [x * x for x in nums]
b = (x * x for x in nums)

print(sum(a))
print(sum(b))

Обе строки «создают квадраты». sum от обеих даст одинаковый результат. Но память они едят по-разному.

Сколько памяти держит b (в круглых скобках)?
A) O(n), как и a
B) O(1)
C) O(log n)
D) Ошибка — генератор нельзя суммировать


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

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

Разбор

a = [x * x for x in nums]    # список: считает и хранит ВСЕ значения сразу
b = (x * x for x in nums)    # генератор: не считает ничего, пока не спросят


a — списковое включение. Оно сразу вычисляет миллион квадратов и складывает их в список. Это O(n) памяти — все элементы лежат одновременно.
b — генераторное выражение. Оно не вычисляет ничего наперёд. Это рецепт: «при запросе выдай следующий квадрат». Значения рождаются по одному во время итерации и тут же выбрасываются.

a:  [0, 1, 4, 9, ..., n²]      ← весь миллион в памяти, O(n)
b:  → 0 → 1 → 4 → ...          ← по одному, O(1)
        (в памяти всегда один элемент)


sum(b) идёт по генератору: берёт квадрат, прибавляет к сумме, забывает, берёт следующий. В памяти в каждый момент — одно число.

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

🧠 Interview Thinking

Задача
Дан массив чисел. Определи, есть ли в нём хотя бы один повторяющийся элемент.
Пример: [1, 2, 3, 1] → True; [1, 2, 3, 4] → False.

Как думает junior
«Для каждого элемента проверю, встречается ли он дальше. Сравню все пары.»

def contains_duplicate(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²) — два вложенных цикла. На большом массиве собес ляжет.

Как думает сильный кандидат
Инсайт: вопрос «видел ли я это число раньше?» — это вопрос про принадлежность множеству. А in по set — это O(1).
Иду по массиву один раз, складываю увиденное в set. Если новый элемент уже там — нашли дубликат.

def contains_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

O(n) время, O(n) память. И ранний выход — на первом же повторе.

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

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

a = [1, 2, 3]
b = a
a = a + [4]
print(b)

c = [1, 2, 3]
d = c
c += [4]
print(d)

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

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

Один и тот же b = a, почти одинаковые операции — а результат разный. Вот где зарыто.

Разбор

Разница между a = a + [4] и a += [4] — фундаментальная, хоть и выглядят синонимами.
Первый случай: a = a + [4]
a + [4] создаёт новый список. Затем имя a переставляется на него. А b как смотрело на старый список — так и смотрит.

до:   a ──► [1, 2, 3] ◄── b

a + [4] создаёт НОВЫЙ список [1,2,3,4]
a переставляется на него:

      a ──► [1, 2, 3, 4]
      b ──► [1, 2, 3]        ← b на старом, не тронут

Второй случай: c += [4]
Для списка += — это extend на месте. Он не создаёт новый объект, а мутирует существующий. А d указывает на тот же самый объект → видит изменение.

до:   c ──► [1, 2, 3] ◄── d

c += [4] меняет ТОТ ЖЕ список на месте:

      c ──► [1, 2, 3, 4]
      d ──────┘            ← d на том же объекте, видит [1,2,3,4]

Суть:

a = a + [4]   →  новый объект, переставляем имя   →  чужие ссылки целы
c += [4]      →  мутируем старый объект на месте   →  чужие ссылки видят изменение

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

⚖️ This vs That: staticmethod vs classmethod

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

Что делает classmethod
Получает первым аргументом сам класс (cls). Через него имеет доступ к классу: другим методам, атрибутам, и — главное — может создавать экземпляры.

class User:
    def __init__(self, name):
        self.name = name

    @classmethod
    def from_string(cls, data):
        name = data.strip().title()
        return cls(name)        # создаём экземпляр через cls
User.from_string("  аня ")    # User(name="Аня")

Что делает staticmethod
Не получает ничего автоматически — ни self, ни cls. Это просто функция, которая лежит внутри класса для группировки. О классе она ничего не знает.

class User:
    @staticmethod
    def is_valid_name(name):
        return name.isalpha() and len(name) >= 2
User.is_valid_name("Аня")    # True

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

знает про свой класс (

cls

) и может им пользоваться.

staticmethod

не знает ни про класс, ни про экземпляр — это просто функция в неймспейсе класса.

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

❌ Rookie Mistakes

def check_status(code):
    if code is 200:
        return "OK"
    return "ошибка"

print(check_status(200))     # "OK"  — вроде работает
print(check_status(1000))    # ???

Со 200 всё хорошо. А теперь то же самое с большим числом:

x = 1000
y = 1000
print(x is y)     # False  ?!

Два раза 1000 — а is говорит «разные». Хотя == сказал бы True. Почему?

Почему это ошибка
is проверяет не равенство значений, а идентичность — «это один и тот же объект в памяти». А Python кэширует только маленькие целые числа: от −5 до 256. Они существуют в единственном экземпляре, поэтому is для них «случайно» работает:

256 is 256    → True    (256 кэширован, объект один)
257 is 257    → False   (создаются два разных объекта)

То же со строками — короткие интернируются, длинные нет:

"hi" is "hi"              # часто True  (интернирована)
"hello world!" is "hello world!"   # может быть False

Самое коварное: код проходит тесты на маленьких значениях и падает в проде на больших. Баг, который невозможно объяснить, глядя только на логику.

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

🧰 Code Cleanup: «Не ищи значение дважды»

❌ Плохой код

users = {
    1: "Alice",
    2: "Bob",
    3: "Charlie",
}

for user_id in users.keys():
    print(users[user_id])

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

for name in users.values():
    print(name)

Или, если нужен и ключ, и значение:

for user_id, name in users.items():
    print(user_id, name)

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

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

❌ Rookie Mistakes: sort() vs sorted()

Многие используют их как взаимозаменяемые.
Именно здесь часто появляются неожиданные баги.

❌ Ошибка

nums = [3, 1, 2]

result = nums.sort()

print(result)
print(nums)

🤔 Ожидание

[1, 2, 3]
[1, 2, 3]

💥 Реальность

None
[1, 2, 3]

🧠 Почему так?

Метод sort() сортирует список на месте и ничего не возвращает.

Поэтому:

result = nums.sort()

в result окажется None.

✅ Правильно

Если нужно изменить исходный список:

nums.sort()

Если нужен новый отсортированный список:

result = sorted(nums)

⚡️ Вывод

Запомни простое правило:
sort() — изменяет существующий список.
sorted() — создаёт новый.

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

🔍 Under the Hood: почему append — это O(1), хотя список растёт

list.append(x) мы делаем не задумываясь. Но список — это массив фиксированного размера в памяти. Как он «дорастает» до нужной длины, не переписываясь каждый раз?

И почему это всё-таки O(1)?

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

1) выделить новый блок побольше
2) скопировать в него все старые элементы   ← это O(n)!
3) дописать новый

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

Трюк: список выделяет память с запасом
Когда места не хватает, Python выделяет не «+1 ячейку», а сразу заметно больше — примерно в 1.125 раза (растёт по мере надобности). Освободившиеся слоты стоят пустыми и ждут будущих append.

len=4, ёмкость=4  →  [1][2][3][4]              полный
append(5):
   выделяем ёмкость 8, копируем, дописываем
len=5, ёмкость=8  →  [1][2][3][4][5][_][_][_]  есть запас!

append(6), append(7), append(8):  ложатся в готовые слоты — БЕЗ копирования

То есть дорогое копирование происходит редко — только когда запас кончился. Между такими моментами куча дешёвых append за O(1).

Почему это «амортизированный O(1)»
Разложим стоимость на всю серию из n добавлений:

дешёвые append (в готовый слот):  O(1)   — большинство
редкие append (с копированием):   O(n)   — но всё реже и реже

Ключ: чем больше список, тем реже случается копирование (ёмкость растёт мультипликативно). Если сложить стоимость всех n операций и поделить на n, редкие дорогие копирования «размазываются» и дают в среднем O(1) на операцию.

суммарно n добавлений  →  O(n)
на одну операцию       →  O(n) / n = O(1) амортизированно

«Амортизированный» — значит «в среднем по серии», а не «всегда». Отдельный append иногда может быть O(n) (в момент расширения), но серия в целом — линейна.

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

🧰 Code Cleanup: индексы в range(len(...)) → enumerate / zip

Плохой код

for i in range(len(names)):
    print(f"{i + 1}. {names[i]}")

И где-то рядом — параллельный обход двух списков по индексу:

for i in range(len(names)):
    print(f"{names[i]} — {scores[i]}")

Работает. Но range(len(...)) — это почти всегда признак, что ты пишешь на Python как на C: крутишь индекс, чтобы потом лезть по нему в список. Индекс тут — лишний посредник.

Чистый вариант
Когда нужен и элемент, и его номер — enumerate:

for i, name in enumerate(names, start=1):
    print(f"{i}. {name}")

Когда идёшь по двум спискам параллельно — zip:

for name, score in zip(names, scores):
    print(f"{name} — {score}")

Объяснение
enumerate отдаёт пары (индекс, элемент) — не надо ни range, ни len, ни names[i]. А start=1 убирает вечное i + 1 для человекочитаемой нумерации.
zip берёт по одному элементу из каждого списка и отдаёт кортежем. Обход двух коллекций «в ногу» становится очевидным — и распаковка name, score сразу показывает, что с чем в паре.
Что меняется по сути:

range(len(x)):  крутим ЧИСЛА, потом лезем x[i]  → индекс как посредник
enumerate/zip:  крутим сами ЭЛЕМЕНТЫ            → работаем с данными напрямую

Пропадает целый класс ошибок: выход за границу, names[i] при рассинхроне длин, опечатка i вместо j. И читается как обычный текст: «для каждого имени и его счёта…».

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

📈 From O(n) to O(1)

Задача
Дано положительное число n. Определи, является ли оно степенью двойки (1, 2, 4, 8, 16, …).

Наивное решение
«Буду делить на 2, пока делится. Если в конце осталась единица — это степень двойки.»

def is_power_of_two(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Корректно. Но это цикл: для n мы делаем примерно log₂(n) итераций — O(log n).

Проблема
Мы работаем с числом как с десятичным и крутим цикл. А в этой задаче есть красивая структура, которую видно только в двоичном виде.

Оптимизированное решение
Посмотри, как степени двойки выглядят в битах:

1   →  0001
2   →  0010
4   →  0100
8   →  1000

Закономерность: у степени двойки ровно один бит равен 1. Всё.
Теперь трюк. Вычтем единицу:

   8  →  1000
   7  →  0111
        ------
n & (n-1):
1000
0111
& ----
0000   →  ноль!

Вычитание единицы «переворачивает» единственную единицу в нули справа от неё. Поэтому n и n-1 не имеют общих единичных битов — их & даёт 0. И это верно только для степеней двойки.

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

O(1) — одна битовая операция, без цикла.

Объяснение
Проверим на не-степени, скажем 6:

   6  →  110    (два единичных бита)
   5  →  101
        -----
   &  →  100    ≠ 0   →  НЕ степень двойки ✅


n & (n-1) — это классический приём «снять самый младший единичный бит». Если после снятия единственного бита осталось 0, значит бит был один → степень двойки.
Условие n > 0 обязательно: для n = 0 формула тоже дала бы 0, но ноль степенью двойки не является.

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

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

print(True + True + True)
print(True == 1)
print(["a", "b", "c"][False])
print(sum([True, False, True, True]))

Что выведет каждая строка?

Ответы:

3
True
"a"
3

Если хоть одна строка удивила — читай дальше, тут прячется важное про устройство Python.

Разбор

Ключевой факт: в Python bool — это подкласс `int`. Не «похож на число», а буквально является числом.

isinstance(True, int)    # True
True == 1                # True
False == 0               # True

Внутри True — это 1, False — это 0. Полноценные целые, просто с красивыми именами и печатью.

Разберём по строкам:

True + True + True   →  1 + 1 + 1        →  3
True == 1            →  1 == 1           →  True
lst[False]           →  lst[0]           →  "a"   (False как индекс = 0!)
sum([T, F, T, T])    →  1 + 0 + 1 + 1    →  3

Третья строка — самая коварная: False спокойно работает как индекс 0, а True — как 1. lst[True] вернул бы "b".

Где это реально полезно

sum булевых значений — это идиома «посчитать, сколько раз условие истинно»:

# сколько чисел больше 10?
count = sum(x > 10 for x in nums)

# сколько строк непустые?
count = sum(bool(s) for s in strings)

Каждое True добавляет 1, каждое False — 0. Коротко и читаемо, без ручного счётчика в цикле.

Где это подводит

bool — подкласс int, поэтому type() == их путает при неаккуратной проверке, а как ключи словаря True и 1 — один и тот же ключ:

d = {1: "один", True: "правда"}
print(d)          # {1: 'правда'}  — True перезаписал 1 !
print(len(d))     # 1

True и 1 равны и дают одинаковый хеш → для словаря это один ключ.

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

🎭 Red Flag: raise без from — потеря исходной ошибки

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

def load_user(user_id):
    try:
        data = cache[user_id]
    except KeyError:
        raise UserNotFoundError(f"Юзер {user_id} не найден")

Выглядит аккуратно: поймали низкоуровневый KeyError, бросили осмысленный доменный UserNotFoundError. Но так ты прячешь улики — и однажды это выйдет боком.

Что не так

Когда исключение возникает внутри блока except, Python по умолчанию цепляет его к исходному. Но в трейсбеке это выглядит запутанно:

KeyError: 42

During handling of the above exception, another exception occurred:

UserNotFoundError: Юзер 42 не найден

Формулировка «During handling of the above exception» намекает, что новая ошибка выскочила случайно, во время обработки — как будто в твоём обработчике баг. А ты-то преобразовал ошибку намеренно. Смысл связи потерян.

Хуже, когда исходную ошибку глушат совсем:

except KeyError:
    raise UserNotFoundError(...)  # а если тут не KeyError, а TypeError?

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

Как надо

Явно свяжи новое исключение с исходным через raise ... from:

def load_user(user_id):
    try:
        data = cache[user_id]
    except KeyError as e:
        raise UserNotFoundError(f"Юзер {user_id} не найден") from e

Теперь трейсбек говорит правду о причинно-следственной связи:

KeyError: 42

The above exception was the direct cause of the following exception:

UserNotFoundError: Юзер 42 не найден

«The direct cause» — ты явно сказал: «этот UserNotFoundError вызван вот этим `KeyError`». Отладка сохраняет всю цепочку.

Когда исходную ошибку стоит подавить

Иногда низкоуровневая причина — шум, и её нужно осознанно скрыть (например, деталь реализации, которую не должен видеть вызывающий). Для этого есть from None:

except KeyError:
    raise UserNotFoundError(f"Юзер {user_id} не найден") from None

Это тоже явное решение — «я намеренно обрываю цепочку», в отличие от случайной потери контекста при голом raise.

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

🧠 Interview Thinking: Two Sum

Классика, с которой начинается почти любой собес. И именно на ней видно, отличает ли кандидат «перебор» от «правильной структуры данных».

Задача

Дан массив чисел и target. Найди индексы двух элементов, дающих в сумме target.
Пример: nums = [2, 7, 11, 15], target = 9 → [0, 1] (2 + 7 = 9).

Как думает junior
«Переберу все пары, проверю каждую сумму.»

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²). На собесе сразу: «А быстрее?»

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

Инсайт-переворот: я ищу не «две подходящие пары», а для каждого числа — одно конкретное дополнение.
Если сейчас у меня x, то мне нужен ровно target − x. Вопрос сужается до: «встречал ли я уже target − x?» А «встречал ли уже» — это O(1) через словарь.
Иду один раз, по пути запоминаю каждое число и его индекс. Для нового x сначала проверяю, не лежит ли уже его дополнение:

def two_sum(nums, target):
    seen = {}                       # число → его индекс
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i

O(n) время, O(n) память. Один проход.

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

💾 Memory Footprint

def has_pair_summing(nums, target):
    for i in range(len(nums)):
        rest = nums[i + 1:]          # «остаток» массива
        for x in rest:
            if nums[i] + x == target:
                return True
    return False

Ищем пару с нужной суммой.

Какая сложность по ПАМЯТИ?

A) O(1)
B) O(n)
C) O(n²)
D) O(log n)

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

Мало кто замечает: срез — это не «взгляд на кусок массива», а новый список.

Разбор
nums[i+1:] выглядит как «просто хвост массива». Но срез списка в Python всегда создаёт копию — выделяет новый список и копирует туда элементы.

nums[i+1:]  →  новый список из (n - i - 1) элементов
               (не ссылка на кусок оригинала — КОПИЯ)

А делаем мы этот срез на каждой итерации внешнего цикла:

i=0:  копия длины n-1
i=1:  копия длины n-2
i=2:  копия длины n-3
...

суммарно скопировано: (n-1)+(n-2)+...+1  =  O(n²) элементов

Да, старые копии собирает garbage collector, но пиковая работа с памятью и лишние аллокации никуда не деваются — на каждом шаге мы создаём и выбрасываем целый список. Это бьёт и по памяти, и по скорости (само копирование — тоже O(n) на итерацию).

Как починить — O(1) лишней памяти
Нам не нужна копия хвоста. Нужен лишь индекс, с которого начинать внутренний цикл:

def has_pair_summing(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):   # индекс вместо среза
            if nums[i] + nums[j] == target:
                return True
    return False
nums[i+1:]:        копия хвоста каждый раз  →  O(n²) памяти
range(i+1, len):   просто числа-индексы     →  O(1) памяти

Никаких копий — ходим по оригиналу по индексам.

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

⚖️ This vs That: sorted() vs list.sort()

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

Что делает list.sort()
Сортирует список на месте, меняя оригинал. И возвращает None.

nums = [3, 1, 2]
nums.sort()
print(nums)    # [1, 2, 3]  — сам список изменился

Что делает sorted()
Не трогает оригинал. Создаёт и возвращает новый отсортированный список.

nums = [3, 1, 2]
result = sorted(nums)
print(result)    # [1, 2, 3]
print(nums)      # [3, 1, 2]  — оригинал цел

Главное отличие в одной фразе
.sort()

меняет список и возвращает

None

.

sorted()

не трогает оригинал и возвращает новый список.

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