⚖️ This vs That

Оба сравнивают. Разница ловится в одной фразе.
== — равенство значений

«Эти два объекта одинаковые по содержанию?»

[1, 2, 3] == [1, 2, 3]   # True
"abc" == "abc"           # True

is — идентичность объектов

«Это один и тот же объект в памяти?»

a = [1, 2, 3]
b = [1, 2, 3]
c = a

a == b   # True   — содержимое одинаковое
a is b   # False  — разные объекты в памяти
a is c   # True   — одна и та же ссылка

== смотрит что внутри. is смотрит где живёт.

Где это путают
Самая частая ошибка — сравнение с числами и строками:

x = 1000
y = 1000
x is y   # False (или True — зависит от реализации!)

CPython кэширует маленькие числа (от -5 до 256) и короткие строки. Поэтому:

a = 100; b = 100
a is b   # True   — оба указывают на кэшированный объект

a = 1000; b = 1000
a is b   # False  — разные объекты

Никогда не используй is для сравнения значений. Поведение зависит от внутренней оптимизации интерпретатора. Сегодня работает — завтра нет.

Когда is — единственно правильный выбор
Для синглтонов Python: None, True, False.

if x is None:        # ✅ правильно
if x == None:        # ❌ работает, но не идиоматично

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

🧠 Interview Thinking

Задача
Дан массив длины n. Найти элемент, который встречается более n/2 раз. Гарантируется, что он есть.

nums = [3, 2, 3, 3, 1, 3, 3]   (n = 7, нужен элемент > 3 раз)
→ 3

Как думает junior — O(n) время, O(n) память
Через Counter:

from collections import Counter

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

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

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

Идея: идём по массиву и ведём «счётчик силы» одного кандидата. Если встречаем его же — +1. Другой — -1. Если счётчик ушёл в ноль — меняем кандидата.

def majority(nums):
    candidate = None
    count = 0
    for n in nums:
        if count == 0:
            candidate = n
        count += 1 if n == candidate else -1
    return candidate

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

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

🧰 Code Cleanup

Плохой код

msg = "User %s has %d points" % (name, score)
msg = "User {} has {} points".format(name, score)
msg = "User {name} has {score} points".format(name=name, score=score)

Все три работают. Но это наследие из старого Python, когда f-strings ещё не было.

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

msg = f"User {name} has {score} points"

Короче. Значения прямо на своих местах — не нужно держать в голове, какой {} соответствует какому аргументу.

Что ещё умеют f-strings

Выражения прямо внутри:

f"Discount: {price * 0.9:.2f}"
f"Items: {len(cart)}"
f"Greeting: {'Hi' if user else 'Hello'}"

Форматирование — после двоеточия:

f"{value:.2f}"      # 2 знака после запятой → "3.14"
f"{n:>10}"          # выравнивание вправо в 10 символов
f"{n:,}"            # разделители тысяч → "1,000,000"
f"{n:08b}"          # двоичное с ведущими нулями → "00001010"

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

⏱️ Big O Breakdown

nums = [1, 2, 3, ..., 1_000_000]
n = len(nums)

Какая сложность len()?
A) O(1)
B) O(n)
C) O(log n)
D) Зависит от типа объекта


Правильный ответ: D — зависит от типа
Для большинства встроенных типов — O(1). Но не для всего.

Разбор
В Python len() зовёт метод __len__ объекта. Если он реализован как прямое чтение поля — это O(1).

Так устроены:

list, tuple, str, bytes, dict, set, frozenset, range

У каждого из них внутри уже хранится длина. len() просто её возвращает — за константное время.

len([1] * 1_000_000)   # O(1) — мгновенно
len("a" * 1_000_000)   # O(1) — мгновенно

Но есть исключения — генераторы

gen = (x for x in range(1000))
len(gen)   # ❌ TypeError: object of type 'generator' has no len()

У генератора нет длины, потому что элементы ещё не сгенерированы. len() не работает в принципе.
Если очень нужно — конвертируй в список (len(list(gen))), но это O(n) и съест всю память.

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

🧠 Interview Thinking

Задача
Лестница из n ступеней. За один шаг можно подняться на 1 или 2 ступени. Сколько различных способов добраться до вершины?

n = 4
→ 5

Способы: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2

Как думает junior — рекурсия в лоб, O(2ⁿ)
«До n-й ступени можно прийти либо с (n-1), либо с (n-2). Значит:»

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

Работает. И это те же самые числа Фибоначчи.
Сложность — O(2ⁿ). На n = 40 уже секунды, на n = 50 — минуты.

Как думает сильный кандидат
Замечает: формула f(n) = f(n-1) + f(n-2) — это Фибоначчи. И сразу понимает, что подзадачи повторяются.
Дальше — два пути:

Мемоизация (top-down):

from functools import lru_cache

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

Каждое значение считается один раз. O(n) время, O(n) память.

Итеративно (bottom-up):

def climb(n):
    a, b = 1, 2
    for _ in range(n - 1):
        a, b = b, a + b
    return a

O(n) время, O(1) память. Лучший вариант.

Главный инсайт
Когда в рекурсии видишь разветвление с повторяющимися подзадачами — это сигнал к динамическому программированию.

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

🧰 Code Cleanup

Плохой код

if age >= 18 and age <= 65:
    ...

if 0 < score and score < 100:
    ...

if start <= x and x < end:
    ...

Работает. Но age пишется дважды, операторы дублируются, читается тяжелее, чем мог бы.

Чистый вариант — цепочка сравнений

if 18 <= age <= 65:
    ...

if 0 < score < 100:
    ...

if start <= x < end:
    ...

Питон позволяет сцеплять операторы сравнения. Это эквивалентно a < b and b < c, но переменная b упоминается один раз.
Читается как математика: «18 ≤ age ≤ 65». Так же и думаешь.

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

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

Задача
Дан массив и число k. Вернуть k-й по величине элемент.

nums = [3, 2, 1, 5, 6, 4], k = 2
→ 5

Наивное решение — O(n log n)
Отсортировать и взять нужный элемент:
python

def kth_largest(nums, k):
    return sorted(nums)[-k]

Работает. Но мы делаем больше работы, чем нужно: сортируем весь массив, хотя нам интересен только один элемент.

Лучше — куча размера k, O(n log k)
Идея: пройти по массиву и держать топ-k самых больших элементов в min-heap. Размер кучи всё время = k.
Когда приходит новый элемент:
если он больше минимального в куче → меняем его местами
иначе пропускаем

На выходе вершина min-heap — это k-й наибольший.
python

import heapq

def kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for n in nums[k:]:
        if n > heap[0]:
            heapq.heapreplace(heap, n)
    return heap[0]

O(n log k) — каждая операция с кучей размера k стоит log k, а не log n.
Если k маленький (k=10) на массиве в миллион — это огромная разница против полной сортировки.

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

🧠 Interview Thinking

Задача
Дан массив. Переместить все нули в конец, сохранив порядок остальных элементов. Менять массив на месте (без создания нового).

nums = [0, 1, 0, 3, 12]
→ [1, 3, 12, 0, 0]

Как думает junior — отдельный массив, O(n) памяти
«Соберу не-нули, потом добью нулями»:

def move_zeroes(nums):
    non_zeros = [n for n in nums if n != 0]
    zeros = [0] * (len(nums) - len(non_zeros))
    nums[:] = non_zeros + zeros

Работает. O(n) по времени, но и O(n) по памяти.
И если интервьюер скажет «сделай на месте, без доп. массивов» — junior зависает.

Как думает сильный кандидат — два указателя, O(1) памяти
Идея: один указатель идёт по массиву и читает элементы. Второй отмечает позицию, куда записать следующий не-ноль.
Когда встретили не-ноль — записываем его на позицию write и двигаем write вправо. Нули просто пропускаем.
В конце все «непрочитанные хвосты» заполняем нулями.

def move_zeroes(nums):
    write = 0
    for n in nums:
        if n != 0:
            nums[write] = n
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0

Один проход + добивка нулей. O(n) время, O(1) память.

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

❌ Rookie Mistakes

Хочешь сделать копию списка перед изменениями:

original = [1, 2, 3]
copy = original

copy.append(4)
print(original)   # [1, 2, 3, 4]   ❗️❗️❗️

Почему изменился original, если меняли copy?

Что произошло
copy = original не создаёт новый список. Это просто новое имя для того же объекта в памяти.

original ──┐
           ├──▶️ [1, 2, 3]
copy     ──┘

copy.append(4) мутирует один список, на который смотрят обе переменные.
В Python присваивание объектов никогда не копирует. Оно создаёт ссылку.

Как правильно
Создать новый список с теми же элементами:

copy = original[:]           # срез — самый короткий способ
copy = list(original)        # явная конструкция
copy = original.copy()       # читаемый метод

Все три варианта дают новый объект. Теперь изменения в copy не затронут original.

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

⏱️ Big O Breakdown

def find_user_by_name(users, name):
    for user_id, user_name in users.items():
        if user_name == name:
            return user_id
    return None

users — словарь {id: name} на n элементов. Какая сложность?

A) O(1) — это же словарь
B) O(log n)
C) O(n)
D) O(n²)


Правильный ответ: C — O(n)
Разбор
Главный обман — слово «словарь». Все знают, что доступ по ключу — O(1). И часто переносят это на любые операции со словарём.
Но O(1) работает только по ключу. Хеш-таблица знает, где лежит users[42], потому что хеширует ключ 42 и идёт в нужный bucket.
Когда мы ищем по значению, словарь нам не помогает. Приходится перебирать все пары — это O(n), как и обычный список.

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

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

Задача
Дан массив целых чисел и число k. Найти количество непрерывных подмассивов с суммой ровно k.

nums = [1, 1, 1], k = 2
→ 2     ([1,1] с индексов 0-1 и 1-2)

nums = [1, 2, 3], k = 3
→ 2     ([1,2] и [3])

Наивное решение — O(n²)
Перебираем все пары (start, end) и считаем сумму:

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

Работает. На массиве в миллион — таймаут.

Идея — префиксные суммы + хеш-таблица
prefix[i] = сумма первых i элементов. Тогда сумма на отрезке [l, r] = prefix[r+1] - prefix[l].

Если эта сумма равна k, значит:

prefix[r+1] - prefix[l] = k
prefix[l] = prefix[r+1] - k

То есть: для текущей префиксной суммы s мы ищем, сколько раз раньше встречалась сумма s - k. Каждое такое совпадение — это отдельный подмассив, оканчивающийся в текущей позиции.

Идём один раз, копим префиксы в словарь:

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}                   # пустой префикс встречался 1 раз
    for n in nums:
        prefix += n
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

O(n) время, O(n) память.
Что значит seen = {0: 1} в начале
Это «нулевой префикс» — сумма пустого начала. Нужно, чтобы корректно считать подмассивы, начинающиеся с индекса 0.
Пример: nums = [3], k = 3. На первом шаге prefix = 3, ищем seen[3 - 3] = seen[0] = 1. Нашли 1 подмассив. ✅

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

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

Задача
Дана строка. Найти длину самой длинной непрерывной подстроки, в которой все символы разные.

"abcabcbb"  → 3   ("abc")
"bbbbb"     → 1   ("b")
"pwwkew"    → 3   ("wke")

Наивное решение — O(n²)
Для каждой стартовой позиции расширяем подстроку, пока не встретим повтор:

def longest_unique(s):
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
        best = max(best, len(seen))
    return best

Работает. Но мы много раз перепроверяем одни и те же символы. Каждый новый старт начинает с нуля.

Идея — sliding window
Держим окно [left, right] и расширяем его вправо. Если новый символ уже в окне — двигаем left вперёд, пока он не уйдёт.

def longest_unique(s):
    seen = {}                    # символ → последний индекс
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1  # перепрыгиваем за повтор
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

O(n) время. Окно проходит слева направо ровно один раз — left и right никогда не идут назад.

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

🧠 Interview Thinking

Задача
Дан массив из n+1 целых чисел, каждое — в диапазоне [1, n]. Один элемент точно повторяется (один или несколько раз). Найти его.

nums = [1, 3, 4, 2, 2]   → 2
nums = [3, 1, 3, 4, 2]   → 3

Как думает junior — O(n) время, O(n) память
Через множество:

def find_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return n
        seen.add(n)

Работает. O(n) время, O(n) память.
Если интервьюер скажет «без дополнительной памяти и не меняй массив» — junior зависает.

Как думает чуть выше — отсортировать

def find_duplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            return nums[i]

O(n log n), без доп. памяти. Но массив изменён — а это часто запрещено условием.

Как думает сильный кандидат — алгоритм Флойда (поиск цикла)
Главный инсайт: рассматриваем массив как связный список, где nums[i] — это указатель на следующий узел.

nums = [1, 3, 4, 2, 2]
индекс: 0  1  2  3  4

0 → nums[0]=1 → nums[1]=3 → nums[3]=2 → nums[2]=4 → nums[4]=2 → ...
                                          ↑                       ↓
                                          └───────── повтор ──────┘

Раз есть дубликат — есть два индекса, указывающих на одно значение. Это значит, в «графе» есть цикл. А дубликат — это вход в цикл.

Дальше классика: алгоритм Флойда «черепаха и заяц».

def find_duplicate(nums):
    slow = fast = nums[0]

    # Шаг 1: встречаемся внутри цикла
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Шаг 2: ищем начало цикла
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

O(n) время, O(1) память. Массив не модифицируется.

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

Попробуйте ответить без запуска, что выведет код, разбор будет через 2 часа

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

Правильный ответ: [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

Разбор
На первый взгляд кажется, что мы создали матрицу 3×3 и поменяли элемент в углу.
На самом деле — нет.
[0] * 3 создаёт один список [0, 0, 0]. А [[0] * 3] * 3 не создаёт три разных списка. Он создаёт три ссылки на один и тот же внутренний список.

Когда мы пишем matrix[0][0] = 1, мы меняем тот единственный список, на который смотрят все три «строки».

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

⏱️ Big O Breakdown

def mystery(n):
    if n <= 1:
        return n
    return mystery(n // 2) + mystery(n // 2)

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

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

Разбор
Глаз видит n // 2 и сразу хочет сказать «логарифм!». Классическая ловушка.
O(log n) появляется, когда мы делим задачу пополам и идём только в одну половину (как бинарный поиск). Здесь мы делим пополам — но рекурсивно вызываемся дважды.

Дерево вызовов:

                mystery(n)
              /            \
       mystery(n/2)      mystery(n/2)
        /        \         /        \
    n/4         n/4      n/4        n/4
   /   \       /  \     /   \      /   \
  ...

На каждом уровне общая работа удваивается. Уровней — log n. Узлов в дереве — 2^(log n) = n.
Итого — O(n).

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

🧰 Code Cleanup

Плохой код

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

    def __repr__(self):
        return f"User(name={self.name!r}, age={self.age}, email={self.email!r})"

    def __eq__(self, other):
        if not isinstance(other, User):
            return NotImplemented
        return (self.name, self.age, self.email) == (other.name, other.age, other.email)

15 строк, чтобы просто хранить три поля. Каждое имя повторяется 3-4 раза. Опечатка в одном месте — баг.

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

from dataclasses import dataclass

@dataclass
class User:
    name: str
    age: int
    email: str

Три строки. Python сам сгенерирует:
__init__ с правильными аргументами
__repr__ с красивым выводом
__eq__ со сравнением по полям

Что это даёт

u1 = User("Anna", 30, "anna@example.com")
u2 = User("Anna", 30, "anna@example.com")

print(u1)        # User(name='Anna', age=30, email='anna@example.com')
u1 == u2         # True

Всё работает «из коробки»

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

❌ Rookie Mistakes

result = 0.1 + 0.2
if result == 0.3:
    print("ок")
else:
    print("WTF?!")

Вывод: WTF?!

Что происходит
В Python (и почти везде) числа с плавающей точкой хранятся в двоичном виде. И некоторые десятичные дроби не имеют точного представления в двоичной системе — как 1/3 не записывается точно в десятичной.

print(0.1 + 0.2)
# 0.30000000000000004

Эта микроскопическая разница — не баг Python. Это стандарт IEEE 754, и так работает везде: в JavaScript, в C, в калькуляторах.

Где это коварно

balance -= 0.1
balance -= 0.1
balance -= 0.1
# теперь balance не "0.7", а 0.7000000000000001

Накапливается. На финансовых данных или физических расчётах — катастрофа.

if total == 100.0:   # сравнение с round-числом
    ...              # может никогда не сработать

Как правильно
Сравнение с допуском:

import math
if math.isclose(0.1 + 0.2, 0.3):
    print("ок")


math.isclose сравнивает с относительным или абсолютным допуском. Параметры по умолчанию подходят для большинства случаев.

Или вручную:

if abs(a - b) < 1e-9:
    ...

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

⏱️ Big O Breakdown

def top_after_each_insert(nums):
    sorted_list = []
    result = []
    for n in nums:
        sorted_list.append(n)
        sorted_list = sorted(sorted_list)   
        result.append(sorted_list[-1])
    return result

nums длины n.

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

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

Разбор
Внешний цикл — n шагов.
Внутри на каждом шаге вызывается sorted(sorted_list). Размер списка к шагу i — это i. Сложность сортировки — O(i log i).
Считаем суммарную работу:

шаг 1:  1 × log 1
шаг 2:  2 × log 2
шаг 3:  3 × log 3
...
шаг n:  n × log n

Это O(n² log n) — на каждом шаге пересортируем всё с нуля.

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