⏱️ Big O Breakdown

Конкатенация строк в цикле. Где прячется O(n²)

Код выглядит невинно. Какова его сложность?

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

Варианты:
А) O(n)
Б) O(n log n)
В) O(n²)
Г) O(1)

Ответ: В) O(n²)

Строки в Python иммутабельны. Каждый += не дописывает слово в конец — он создаёт новую строку, копируя всё, что было до.

Шаг 1: копируем 1 символ
Шаг 2: копируем 2 символа
Шаг 3: копируем 3 символа
...
Шаг n: копируем n символов

Итого: 1 + 2 + 3 + ... + n = O(n²) по количеству копируемых символов.

На 10 словах — незаметно. На 100 000 — катастрофа.

Правильно:

def build_string(words):
    return "".join(words)

str.join() вычисляет итоговый размер заранее, выделяет память один раз и заполняет её. Сложность — O(n).

Ловушка на собесе:

# Это тоже O(n²) — не обманывайся форматированием
result = ""
for word in words:
    result = result + word + ", "

И ещё одна:

# А вот это уже O(n) — список мутабельный
parts = []
for word in words:
    parts.append(word)
result = "".join(parts)

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

Diamond problem — проблема множественного наследования, когда класс получает один и тот же базовый класс по двум путям.

Схема
A
/ \
B C
\ /
D

🔹 D наследуется от B и C
🔹 B и C наследуются от A

В чём проблема

🔹 Неочевидно, какой метод из A будет вызван
🔹 Возможен двойной вызов конструктора
🔹 Возникает неоднозначность порядка вызовов

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

📈 FROM O(...) TO O(...)

Поиск всех простых до N: от O(n√n) до O(n log log n)

Очевидное решение — проверять каждое число отдельно:

def primes_up_to(n):
    return [i for i in range(2, n + 1) if is_prime(i)]

O(√n) на каждое число. Суммарно — O(n√n). На миллионе чисел медленно.

Решето Эратосфена:

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    return [i for i, v in enumerate(is_prime) if v]

O(n log log n) — практически линейная.

Идея: не проверяем делители, а вычёркиваем кратные. Каждое составное число вычёркивается ровно один раз. Начинаем с i*i — всё меньшее уже вычеркнуто раньше.

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

🧩 Code Cleanup

Не проверяй тип через type() — используй isinstance()

Часто вижу такое:

def process(value):
    if type(value) == int:
        return value * 2
    if type(value) == str:
        return value.upper()

Выглядит логично. Но это ловушка.

После:

def process(value):
    if isinstance(value, int):
        return value * 2
    if isinstance(value, str):
        return value.upper()

В чём разница:

type() проверяет точный тип — не учитывает наследование. isinstance() учитывает.

class MyInt(int):
    pass

x = MyInt(5)

type(x) == int      # False — сюрприз
isinstance(x, int)  # True

С type() подкласс не пройдёт проверку. Это ломает полиморфизм и нарушает принцип подстановки Лисков.

Ещё плюс — isinstance() принимает кортеж типов:

isinstance(value, (int, float))  # вместо двух отдельных проверок

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

⏱️ Big O Breakdown

Поиск элемента в list vs set. Казалось бы, одно и то же

Какова сложность этих двух операций?

nums_list = list(range(1_000_000))
nums_set = set(range(1_000_000))

999_999 in nums_list
999_999 in nums_set

Варианты:
А) Оба O(1)
Б) Оба O(n)
В) list — O(n), set — O(1)
Г) list — O(1), set — O(n)

Ответ: В) list — O(n), set — O(1)

`list` хранит элементы последовательно. Проверка `in` — линейный перебор от первого до последнего. В худшем случае — n сравнений.

`set` — хеш-таблица. Python вычисляет `hash(999_999)`, находит нужный bucket и проверяет один элемент. Почти всегда — одна операция.

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

🧠 Interview Thinking

Найди два числа в массиве, дающих целевую сумму

Классика. Есть в каждом втором собесе.

# Дано:
nums = [2, 7, 11, 15]
target = 9

# Вернуть индексы двух чисел, сумма которых == target
# Ответ: [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)

Как думает junior:

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²). Работает — но интервьюер сразу спросит: «Можешь быстрее?»

Как думает strong middle:

Не ищу пары — ищу дополнение.

Для каждого числа x нужно найти target - x. Если хранить уже просмотренные числа в словаре — поиск O(1).

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i

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


Что хочет услышать интервьюер:

Не просто правильный код. А ход мыслей:

1. Назвал наивное решение и его сложность
2. Сам предложил оптимизацию — не ждал подсказки
3. Объяснил trade-off: платим памятью, выигрываем время
4. Проверил edge cases: пустой массив, одно число, дубликаты

# Edge case с дубликатами:
nums = [3, 3], target = 6
# seen = {3: 0} → complement = 3 → найден на индексе 0
# Вернём [0, 1] — корректно

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

📈 FROM O(...) TO O(...)

Скользящее окно: от O(n²) до O(n)

Задача: найти максимальную сумму подмассива длиной k.

nums = [2, 1, 5, 1, 3, 2]
k = 3
# Ответ: 9 (подмассив [5, 1, 3])

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

def max_sum(nums, k):
    max_s = 0
    for i in range(len(nums) - k + 1):
        s = sum(nums[i:i+k])
        max_s = max(max_s, s)
    return max_s

sum() внутри цикла — пересчитываем окно целиком на каждом шаге. O(n·k).


Скользящее окно:

def max_sum(nums, k):
    window = sum(nums[:k])
    max_s = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        max_s = max(max_s, window)
    return max_s

O(n) — один проход.

Идея: не пересчитываем окно заново. Добавляем новый элемент справа, убираем старый слева. Одно сложение и одно вычитание вместо k операций.

# [2, 1, 5] → сумма 8
# сдвиг: +1 -2 → [1, 5, 1] → сумма 7
# сдвиг: +3 -1 → [5, 1, 3] → сумма 9  ← максимум
# сдвиг: +2 -5 → [1, 3, 2] → сумма 6

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

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

🧩 Code Cleanup

Не пиши if len(lst) == 0 — Python умеет лучше

Типичный код от новичка:

if len(items) == 0:
    return

if len(items) > 0:
    process(items)

if len(result) != 0:
    return result

После:

if not items:
    return

if items:
    process(items)

if result:
    return result

Короче, читается как английский, работает для любого контейнера.

Почему это работает:

В Python пустые list, dict, set, str, tuple — все являются falsy. Непустые — truthy. Это не магия, а протокол __bool__ / __len__.

bool([])   # False
bool([1])  # True
bool({})   # False
bool("")   # False
bool("x")  # True

Ловушка — не путай с None:

items = []

if items is not None:  # True — список существует, просто пустой
    ...

if items:              # False — список пустой
    ...

Если функция может вернуть None или пустой список — это разные случаи. Проверяй осознанно.

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

⏱️ Big O Breakdown

dict.get() vs dict[]. Где прячется исключение

Какова сложность этих двух операций?

d = {"a": 1, "b": 2}

x = d["c"]
y = d.get("c", 0)

Варианты:
А) Оба O(1)
Б) d["c"] — O(n), d.get() — O(1)
В) Оба O(n)
Г) d.get() — O(n), d["c"] — O(1)

Ответ: А) Оба O(1)

По сложности — одинаковы. Оба обращаются к хеш-таблице. Разница не в скорости, а в поведении.

d["c"] бросает KeyError если ключа нет. d.get("c", 0) возвращает дефолтное значение.

Где это реально важно:

# Подсчёт частоты — rookie вариант
counts = {}
for word in words:
    if word not in counts:
        counts[word] = 0
    counts[word] += 1

# Чище через get()
for word in words:
    counts[word] = counts.get(word, 0) + 1

# Ещё лучше — defaultdict
from collections import defaultdict
counts = defaultdict(int)
for word in words:
    counts[word] += 1

Все три варианта — O(n). Но читаемость и лаконичность разные.

Ловушка:

d.get("key")  # вернёт None если ключа нет
d.get("key", [])  # осторожно — [] создаётся каждый раз заново

Если дефолт — мутабельный объект и нужно его модифицировать, используй defaultdict — он создаёт дефолт один раз per key.

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

RESTful — API, реализующее принципы REST.

Основные идеи

🔹 Ресурсы вместо действий
/users/1 — ресурс

🔹 Использование HTTP-методов по назначению
GET, POST, PUT/PATCH, DELETE

🔹 Stateless — сервер не хранит состояние клиента

🔹 Единый и предсказуемый интерфейс

Итог: RESTful — это API, где операции выполняются над ресурсами через стандартные HTTP-механизмы.

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

📈 FROM O(...) TO O(...)

Разворот связного списка: от рекурсии к итерации

Задача: развернуть односвязный список.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

# 1 -> 2 -> 3 -> 4 -> None
# Нужно: 4 -> 3 -> 2 -> 1 -> None

Рекурсивное решение:

def reverse(head):
    if not head or not head.next:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

O(n) время — но O(n) память из-за стека вызовов. На списке из 100 000 элементов — RecursionError.

Итеративное решение:

def reverse(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

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

Как работает:

None <- 1    2 -> 3 -> 4
  prev curr next
       ↓
None <- 1 <- 2    3 -> 4
         prev curr next

На каждом шаге переворачиваем одну стрелку. Сохраняем next_node до того, как потеряем ссылку.

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

🧩 Code Cleanup

Не используй range(len()) там, где не нужен индекс

Классика junior-кода:

names = ["alice", "bob", "charlie"]

for i in range(len(names)):
    print(names[i])

После:

for name in names:
    print(name)

Прямо, читаемо, питонично. Никаких лишних индексов.

Когда нужен и элемент, и индекс — enumerate():

# Плохо
for i in range(len(names)):
    print(i, names[i])

# Хорошо
for i, name in enumerate(names):
    print(i, name)

Когда нужно идти по двум спискам одновременно — zip():

# Плохо
for i in range(len(names)):
    print(names[i], scores[i])

# Хорошо
for name, score in zip(names, scores):
    print(name, score)

Когда range(len()) всё же уместен:

# Нужно модифицировать список по индексу
for i in range(len(nums)):
    nums[i] *= 2

Здесь индекс нужен для записи — оправдано.

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

⏱️ Big O Breakdown

list.insert(0, x) vs collections.deque. Скрытый O(n) в начале списка

Какова сложность этих двух операций?

lst = [1, 2, 3, 4, 5]
lst.insert(0, 0)

from collections import deque
dq = deque([1, 2, 3, 4, 5])
dq.appendleft(0)

Варианты:
А) Оба O(1)
Б) Оба O(n)
В) insert(0, x) — O(n), appendleft() — O(1)
Г) insert(0, x) — O(1), appendleft() — O(n)

Ответ: В) insert(0, x) — O(n), appendleft() — O(1)

list в Python — это динамический массив. Вставка в начало сдвигает все элементы вправо на одну позицию. n элементов — n операций.

deque — двусвязный список. Добавление в начало — просто новая ссылка. Всегда O(1).

На практике:

deque быстр по краям, медленен в середине. list — наоборот.

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

Объект первого класса — это сущность, с которой можно работать как с данными.

Признаки

🔹 можно присваивать переменной
🔹 можно передавать в функцию как аргумент
🔹 можно возвращать из функции
🔹 можно хранить в структурах данных

Пример

def greet():
    return "hi"

f = greet
print(f())  # hi

🔹 функция ведёт себя как обычный объект

Итог: объект первого класса — это объект, который можно свободно передавать и использовать как значение

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

🧠 Interview Thinking

Найди максимальную прибыль от покупки и продажи акции

Ещё одна классика. Встречается часто на собесе на middle.

# Дано: цены акции по дням
prices = [7, 1, 5, 3, 6, 4]

# Купить один раз, продать один раз.
# Вернуть максимальную прибыль.
# Ответ: 5 (купить за 1, продать за 6)

Как думает junior:

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

O(n²) время, O(1) память. Работает — но медленно.

Как думает strong middle:

Не нужно перебирать пары. Нужно отслеживать минимальную цену покупки и максимальную прибыль на каждом шаге.

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

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

Логика: на каждый день спрашиваем — если бы продал сегодня, какая прибыль? Максимум из всех таких ответов — и есть результат.

# prices = [7, 1, 5, 3, 6, 4]
# min:      7  1  1  1  1  1
# profit:   0  0  4  2  5  3  <- максимум = 5

Что хочет услышать интервьюер:

1. Наивное решение назвал сам — не ждал подсказки
2. Объяснил почему O(n²) плохо на больших данных
3. Додумался до одного прохода через отслеживание минимума
4. Проверил edge cases

# Edge cases:
prices = [7, 6, 4, 3, 1]  # цены только падают → прибыль 0
prices = [1]               # один день → прибыль 0

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

📈 FROM O(...) TO O(...)

Анаграммы: от сортировки до счётчика

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

# "listen" и "silent" — анаграммы
# "hello" и "world" — нет

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

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

Коротко, но sorted() — O(n log n). На длинных строках медленно.

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

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        count[c] = count.get(c, 0) - 1
        if count[c] < 0:
            return False
    return True

O(n) время, O(1) память — алфавит фиксирован, максимум 26 ключей.

Или через Counter:

from collections import Counter

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

Тоже O(n) — но читается в одну строку.

Ранний выход: проверка len(s) != len(t) отсекает очевидные случаи до любых вычислений. Всегда добавляй такие проверки первыми.

Логика счётчика: увеличиваем за первую строку, уменьшаем за вторую. Если любой счётчик уходит в минус — символ встречается чаще во второй строке. Не анаграмма.

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

🧩 Code Cleanup

dataclasses — перестань писать __init__ руками

Типичный класс-контейнер:

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}, age={self.age}, email={self.email})"

    def __eq__(self, other):
        return (self.name, self.age, self.email) == (other.name, other.age, other.email)

Много кода. Весь — шаблонный.

После:

from dataclasses import dataclass

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

__init__, __repr__, __eq__ — генерируются автоматически.

Дополнительные возможности:

@dataclass(frozen=True)  # иммутабельный, можно использовать как ключ словаря
class Point:
    x: float
    y: float

@dataclass(order=True)  # добавляет __lt__, __gt__ — можно сортировать
class Product:
    price: float
    name: str

Дефолтные значения:

from dataclasses import dataclass, field

@dataclass
class Config:
    host: str = "localhost"
    port: int = 8080
    tags: list = field(default_factory=list)  # мутабельный дефолт — через field()

field(default_factory=list) — потому что мутабельный дефолт напрямую это та самая ловушка с разделяемым объектом.

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

📈 FROM O(...) TO O(...)

Числа Фибоначчи: от O(2ⁿ) до O(n)

Задача: найти n-е число Фибоначчи.

# fib(0) = 0, fib(1) = 1
# fib(n) = fib(n-1) + fib(n-2)

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

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

Выглядит элегантно. Но fib(40) считается секунды, fib(50) — минуты.

Сложность — O(2ⁿ). Каждый вызов порождает два новых. Одни и те же значения пересчитываются тысячи раз.

Мемоизация — O(n) время, O(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)

Один декоратор — каждое значение считается ровно один раз.

Итеративно — O(n) время, O(1) память:

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

Никакой рекурсии, никакого кеша. Два числа — и вперёд.

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

🧠 Interview Thinking

Валидация скобок. Задача на стек

Простая на вид задача, которая проверяет понимание структур данных.

# Дано: строка из скобок
# Вернуть True если все скобки закрыты правильно

"([]{})"  # True
"([)]"    # False
"((("     # False

Как думает junior:

Считает открывающие и закрывающие скобки:

def is_valid(s):
    return s.count("(") == s.count(")")

Не работает для "([)]" — количество совпадает, порядок нет.

Как думает strong middle:

Нужен стек. Открывающую скобку кладём, закрывающую — проверяем пару с вершиной.

def is_valid(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}

    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return not stack

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

Разбор на примере "([)]":

( → stack: ["("]
[ → stack: ["(", "["]
) → ожидаем "(" на вершине, там "[" → False

Что хочет услышать интервьюер:

1. Сразу назвал стек — не пытался считать символы
2. Объяснил почему счётчик не работает
3. Не забыл return not stack — стек должен быть пуст в конце
4. Проверил edge cases

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

❌ Rookie Mistakes

is вместо == — тихий баг который сложно поймать

Очень частая ошибка у тех, кто переходит с других языков:

a = input()  # вводим "hello"

if a is "hello":  # выглядит логично
    print("совпадает")

Иногда работает. Иногда нет. Зависит от реализации интерпретатора.

В чём разница:

== — сравнивает значения. is — сравнивает идентичность объектов, то есть ссылки на один и тот же объект в памяти.

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

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

Почему иногда работает с числами и строками:

Python кеширует маленькие целые числа (-5 до 256) и некоторые строки — это называется интернирование. Поэтому is для них случайно возвращает True.

a = 256
b = 256
a is b  # True — оба ссылаются на один кешированный объект

a = 257
b = 257
a is b  # False — уже не кешируется

Полагаться на это нельзя — поведение зависит от реализации CPython.

Когда is уместен:

# Только для сравнения с None, True, False
if value is None:
    ...

if result is True:
    ...

Это канонический способ — None всегда один объект в памяти.

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

⏱️ Big O Breakdown

Два указателя: O(n²) становится O(n)

Задача: найти в отсортированном массиве пару чисел с заданной суммой. Какова сложность каждого подхода?

nums = [1, 3, 5, 7, 9, 11]
target = 12

# Вариант 1
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return [i, j]

# Вариант 2
left, right = 0, len(nums) - 1
while left < right:
    s = nums[left] + nums[right]
    if s == target:
        return [left, right]
    elif s < target:
        left += 1
    else:
        right -= 1

Варианты:
А) Оба O(n)
Б) Оба O(n²)
В) Вариант 1 — O(n²), Вариант 2 — O(n)
Г) Вариант 1 — O(n), Вариант 2 — O(n²)

Ответ: В) Вариант 1 — O(n²), Вариант 2 — O(n)

Два вложенных цикла — O(n²). Два указателя — один проход от краёв к центру — O(n).

Почему работает:

Массив отсортирован. Сумма меньше target — двигаем левый указатель вправо, увеличиваем сумму. Сумма больше — двигаем правый влево, уменьшаем. Каждый шаг отсекает невозможные пары.

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