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

Задача
Дан отсортированный массив. Найти индекс числа target или вернуть -1, если его нет.

nums = [1, 3, 5, 7, 9, 11, 13, 15], target = 11
→ 5

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

def find(nums, target):
    for i, n in enumerate(nums):
        if n == target:
            return i
    return -1

Проходит весь массив. На миллионе элементов — миллион сравнений. Сортировка не используется.
Бинарный поиск — O(log n)

Идея: каждый шаг отбрасываем половину массива.

Смотрим на средний элемент:
равен target → нашли
target меньше → ищем в левой половине
target больше → ищем в правой половине

def find(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

O(log n) — потому что на каждом шаге размер задачи делится пополам.
Насколько это быстрее

n              линейный поиск     бинарный поиск
─────────────────────────────────────────────────
1 000          1 000              ~10
1 000 000      1 000 000          ~20
1 000 000 000  1 миллиард         ~30

На миллиарде элементов — 30 шагов вместо миллиарда.

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

🧠 Interview Thinking
Все знают FizzBuzz. Это не задача на алгоритмы. Это задача на то, как ты пишешь код.

Условие
Числа от 1 до n. Для каждого:
кратно 3 → "Fizz"
кратно 5 → "Buzz"
кратно и 3, и 5 → "FizzBuzz"
иначе → само число

Как пишет junior

for i in range(1, n + 1):
    if i % 3 == 0 and i % 5 == 0:
        print("FizzBuzz")
    elif i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    else:
        print(i)

Работает. Принято.

Но интервьюер уже видит проблемы:
условие i % 3 == 0 and i % 5 == 0 — это i % 15 == 0, но junior это не упростил
что будет, если завтра добавят i % 7 == 0 → "Bazz"? Получим лестницу из 8 веток.

Как пишет сильный кандидат
Сначала проговаривает структуру:

«Это не три независимых условия, а накопление строки. Для каждого числа я хочу собрать суффиксы: если делится на 3 — добавить Fizz, если на 5 — добавить Buzz. Если ничего не накопилось — вернуть само число.»

И пишет:

for i in range(1, n + 1):
    out = ""
    if i % 3 == 0:
        out += "Fizz"
    if i % 5 == 0:
        out += "Buzz"
    print(out or i)

Заметь:
никаких and — два независимых условия сами дают «FizzBuzz»
никакой проблемы порядка — Fizz всегда перед Buzz
никакого else — out or i элегантно подставляет число, если строка пустая

А если масштабировать?

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

«Если бы правил было больше, я бы вынес их в данные.»

RULES = [(3, "Fizz"), (5, "Buzz"), (7, "Bazz")]

for i in range(1, n + 1):
    out = "".join(word for div, word in RULES if i % div == 0)
    print(out or i)

Теперь добавить новое правило — это одна строка в списке, а не новая ветка в функции.

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

🧰 Code Cleanup

Плохой код

names = ["Anna", "Boris", "Carol"]
ages = [30, 25, 40]

for i in range(len(names)):
    print(f"{names[i]} — {ages[i]} лет")

Работает. Но связь между списками неявная. Чтобы понять код, нужно мысленно держать индекс i и индексировать оба списка вручную.

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

for name, age in zip(names, ages):
    print(f"{name} — {age} лет")

zip склеивает списки в пары: ("Anna", 30), ("Boris", 25), ("Carol", 40).
В цикле сразу распаковываем — и работаем с именованными переменными, а не с индексами.

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

🎭 Red Flag

def process(value):
    if type(value) == list:
        return sum(value)
    if type(value) == int:
        return value * 2

Работает. На простых случаях. Но это хрупкая проверка типа, и она ломается в самых неприятных местах.

Что не так
type(x) == X проверяет точное совпадение типа. Любой наследник провалит проверку:

class MyList(list):
    pass

m = MyList([1, 2, 3])

type(m) == list      # False ❗️
isinstance(m, list)  # True ✅


MyList — это список во всех смыслах. У него те же методы, то же поведение. Но type(m) == list его не пропускает.
Это нарушает принцип подстановки Лисков (LSP): код, который работает с базовым типом, должен работать с наследниками. type == этот принцип ломает.

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

⏱️ Big O Breakdown

def process(nums):
    for n in nums:
        print(n)

    for n in nums:
        print(n * 2)

nums длины n.

Какая сложность?

A) O(n)
B) O(2n)
C) O(n²)
D) Зависит от размера

Правильный ответ: A — O(n)
Разбор

Глаз видит два цикла и хочет сказать «O(n²)». Но n² появляется только тогда, когда циклы вложены — один внутри другого.
Здесь циклы последовательные: сначала отработал первый (n шагов), потом второй (ещё n шагов). Итого — 2n шагов.
В big-O константы отбрасываются: 2n — это O(n). Не O(2n), а именно O(n).

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

🧰 Code Cleanup

Плохой код

if is_active == True:
    do_something()

if items == []:
    return None

Работает. Но это двойная проверка там, где хватит одной.

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

if is_active:
    do_something()

if not items:
    return None

if сам приводит значение к булеву. Не нужно сравнивать с True или с пустым контейнером — питон уже понимает, что считать «истиной».

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

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

Задача
Даны два отсортированных массива. Слить их в один отсортированный.

a = [1, 4, 7, 10]
b = [2, 3, 8, 11]
→ [1, 2, 3, 4, 7, 8, 10, 11]

Наивное решение — O((n+m) log(n+m))

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

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

Сравнить через in? Ещё хуже — O(n·m)

result = []
for x in a:
    for y in b:
        if y < x and y not in result:
            result.append(y)
    result.append(x)

Вложенный цикл по парам — катастрофа.

Два указателя — O(n+m)
Идём по обоим массивам одновременно. На каждом шаге берём меньший элемент:

def merge(a, b):
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])   # докинуть остаток
    result.extend(b[j:])
    return result

Каждый элемент обоих массивов посещается ровно один раз. Итого — O(n+m) по времени.

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

⏱️ Big O Breakdown

def running_average(nums):
    result = []
    for i in range(1, len(nums) + 1):
        result.append(sum(nums[:i]) / i)
    return result

nums длины n.

Какая сложность?

A) O(n)
B) O(n log n)
C) O(n²)
D) O(n²) только в худшем случае

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

Разбор
Внешний цикл — n шагов. Это очевидно.
А вот внутри прячется коварство: sum(nums[:i]) на каждом шаге проходит по всем элементам до i. Это O(i) операций.

i=1:  sum по 1 элементу
i=2:  sum по 2 элементам
i=3:  sum по 3 элементам
...
i=n:  sum по n элементам

Сумма: 1 + 2 + 3 + ... + n ≈ n²/2. Итого — O(n²).

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

🧠 Interview Thinking

Задача
Дан массив цен акции по дням. Купить один раз, продать позже — максимизировать прибыль.

prices = [7, 1, 5, 3, 6, 4]
→ 5     (купить за 1 в день 1, продать за 6 в день 4)

Как думает junior — O(n²)
Перебирает все пары «день покупки / день продажи»:

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

Работает. На большом входе — таймаут.

Как думает сильный кандидат — O(n)
Главный вопрос: что мне нужно знать, чтобы посчитать прибыль в день i?
Только одно — самая низкая цена среди предыдущих дней. Если я её помню, то прибыль = prices[i] - min_so_far.
Значит, идём слева направо, на каждом шаге обновляем две вещи:
минимальную цену из увиденных
лучшую прибыль из увиденных

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for price in prices:
        min_price = min(min_price, price)       # самый дешёвый день до сих пор
        best = max(best, price - min_price)     # лучшая прибыль до сих пор
    return best

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

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

🧰 Code Cleanup

Плохой код

def calculate_price(items):
    total = sum(item.price for item in items)
    if total > 5000:
        total *= 0.9
    if len(items) > 10:
        total -= 200
    return total + total * 0.2

Откуда взялись 5000, 0.9, 10, 200, 0.2? Что они значат? Без знания бизнес-логики — никак не понять.
Это и есть магические числа: непонятные литералы прямо в коде.

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

DISCOUNT_THRESHOLD = 5000
DISCOUNT_RATE = 0.9
BULK_ITEM_THRESHOLD = 10
BULK_DISCOUNT = 200
VAT_RATE = 0.2

def calculate_price(items):
    total = sum(item.price for item in items)
    if total > DISCOUNT_THRESHOLD:
        total *= DISCOUNT_RATE
    if len(items) > BULK_ITEM_THRESHOLD:
        total -= BULK_DISCOUNT
    return total + total * VAT_RATE

Та же логика. Но теперь код читается как описание правил, а не как ребус.
Что мы получили
1. Самодокументируемость. total > DISCOUNT_THRESHOLD объясняет сам себя.
2. Изменения в одном месте. Если VAT поменяется с 20% на 21% — правишь одну строку, а не охотишься за 0.2 по всему файлу.

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

⚖️ 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