Какая сложность данного алгоритма?

words — список из n строк.

Разбор будет через 2 часа

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

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

Разбор

Строки в Python неизменяемые. result += word не «дописывает в конец» — это создание нового объекта строки, в который копируется и старое содержимое, и новое.
С каждой итерацией result всё длиннее, и каждое копирование становится дороже:

шаг 1: копируем 1 символ
шаг 2: копируем 2 символа
шаг 3: копируем 3 символа
...
шаг n: копируем n символов
Сумма: 1 + 2 + 3 + ... + n ≈ n²/2. Итого — O(n²).

Один цикл — а внутри незаметно вложен второй, в виде копирования.

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

🧰 Code Cleanup

Плохой код

def get_user_email(user):
    if user is not None:
        if user.is_active:
            if user.email:
                return user.email
            else:
                return None
        else:
            return None
    else:
        return None

Каждое условие — новый уровень вложенности. Логику нужно держать в голове до самого конца, чтобы понять, где что вернётся.

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

def get_user_email(user):
    if user is None:
        return None
    if not user.is_active:
        return None
    if not user.email:
        return None
    return user.email

То же самое, но плоско. Каждая проверка — отдельный пункт «не подходит → выходим». Основной путь функции виден сразу.

Это называется guard clauses — «охранные условия» в начале функции, которые отсекают всё лишнее.

Почему так лучше

1. Меньше отступов → меньше когнитивной нагрузки.
2. Основная логика в конце на нулевом уровне, а не закопана в три вложенности.
3. Легче добавить новую проверку — просто ещё один if в начале.
4. Легче читать сверху вниз: «не то — выход, не то — выход, всё ок — работаем».

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

🧠 Interview Thinking

Задача

Дан массив из n - 1 различных чисел в диапазоне от 1 до n. Одно число пропущено. Найти его.

nums = [3, 1, 5, 2]   (n = 5)
→ 4

Как думает junior

«Перебираю все числа от 1 до n и проверяю, какого нет»:

def find_missing(nums, n):
    for i in range(1, n + 1):
        if i not in nums:
            return i

Работает. Но i not in nums — это O(n), и мы делаем его n раз. Итого — O(n²).

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

Junior часто этим и ограничивается. Главный признак: он не проверил себя на сложность перед сдачей решения.

Как думает чуть более опытный кандидат

«Положу в set для быстрого поиска»:

def find_missing(nums, n):
    seen = set(nums)
    for i in range(1, n + 1):
        if i not in seen:
            return i

O(n) по времени, O(n) по памяти. Уже хорошо.

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

Замечает структуру задачи: числа — это арифметическая прогрессия.

Сумма всех чисел от 1 до n известна заранее: n * (n + 1) / 2.

Если из этой суммы вычесть сумму того, что есть в массиве — получится пропущенное число.

def find_missing(nums, n):
    return n * (n + 1) // 2 - sum(nums)

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

Альтернатива через XOR (если интервьюер давит)

Если массив большой и есть риск переполнения сумм (для других языков, не Python) — XOR:

def find_missing(nums, n):
    result = 0
    for i in range(1, n + 1):
        result ^= i
    for x in nums:
        result ^= x
    return result

a ^ a = 0, поэтому всё, что встретилось дважды (в обоих циклах), сократится. Останется только пропущенное число.

В Python переполнения нет — но знание этого трюка показывает, что ты видишь задачу шире языка.

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

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

Задача

Дан отсортированный массив и число target. Найти два числа, сумма которых равна target. Вернуть их индексы.

nums = [1, 3, 5, 8, 11, 14], target = 13
→ (1, 4)   # 3 + 11

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

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(n)

Заводим два индекса: один на начало, другой на конец. На каждом шаге смотрим сумму:

- сумма меньше target → нужно больше → двигаем левый вправо
- сумма больше target → нужно меньше → двигаем правый влево
- равна → нашли

def two_sum(nums, target):
    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
    return None

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

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

⚖️ This vs That: copy vs deepcopy

Оба «копируют объект». Оба из модуля copy. Разница ловится в одной фразе.
copy.copy — поверхностная копия

Создаёт новый объект-обёртку. Но внутренние объекты остаются те же — копируются только ссылки на них.

import copy

original = [[1, 2], [3, 4]]
shallow = copy.copy(original)

shallow[0].append(99)
print(original)   # [[1, 2, 99], [3, 4]]   ❗️ изменился исходник

Внешний список новый — shallow.append(...) его не затронет. Но вложенные списки те же самые — мы только скопировали ссылки на них.

copy.deepcopy — глубокая копия

Рекурсивно копирует всё: и обёртку, и вложенные объекты, и вложенные во вложенные.

deep = copy.deepcopy(original)
deep[0].append(99)
print(original)   # [[1, 2], [3, 4]]   ✅ исходник цел

Полностью независимая копия. Никакие изменения в deep не влияют на original.

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

🧰 Code Cleanup

Плохой код

squares = []
for n in range(10):
    squares.append(n * n)

Три строки. Создаём пустой список, потом наполняем. Классика.

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

squares = [n * n for n in range(10)]

Одна строка. Та же логика, но сразу видно, что результат — это список квадратов.

С условием — тоже одна строка

# было
result = []
for n in nums:
    if n > 0:
        result.append(n * 2)

# стало
result = [n * 2 for n in nums if n > 0]

Сначала идёт что собираем (n * 2), потом откуда (for n in nums), потом фильтр (if n > 0).

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

⏱️ Big O Breakdown

Классическое «красивое» решение:

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

Выглядит как определение из учебника. Какая сложность?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(2ⁿ)


Правильный ответ: D — O(2ⁿ)

Разбор
Каждый вызов fib(n) порождает два новых: fib(n-1) и fib(n-2). Те — ещё по два. И так далее.
Дерево вызовов растёт экспоненциально:

                  fib(5)
                /        \
            fib(4)        fib(3)
           /     \        /    \
        fib(3) fib(2)  fib(2) fib(1)
        /   \    ...    ...
     fib(2) fib(1)

Заметь, как fib(3) считается дважды, fib(2) — трижды, fib(1) — ещё больше. Мы пересчитываем одно и то же.

fib(40) — уже больше миллиарда вызовов.

Почему именно 2ⁿ
Дерево вызовов имеет высоту n и каждый уровень удваивается. Узлов в нём — порядка 2ⁿ.

Точнее — O(φⁿ), где φ ≈ 1.618 (золотое сечение), но для big-O это эквивалентно O(2ⁿ).

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

📈 From O(n) to O(1)

Задача
Реализовать очередь: добавляем элементы в конец, забираем — с начала. Классический FIFO.

queue.add("a")   → ["a"]
queue.add("b")   → ["a", "b"]
queue.add("c")   → ["a", "b", "c"]
queue.pop_front() → "a"   осталось ["b", "c"]

Наивное решение через list — O(n) на pop

queue = []

queue.append("a")
queue.append("b")
queue.append("c")

first = queue.pop(0)   # ← вот тут проблема

append() — это O(1), отлично. А вот pop(0) — O(n).

Почему? Список в Python — это массив в памяти. Когда удаляешь нулевой элемент, все остальные сдвигаются на одну позицию влево. На миллионе элементов — миллион операций копирования.
При активной работе с очередью получаем O(n²) суммарно. На больших данных — катастрофа.

Решение: collections.deque — O(1) на оба конца

from collections import deque

queue = deque()

queue.append("a")
queue.append("b")
queue.append("c")

first = queue.popleft()   # O(1) ✅

deque (double-ended queue) внутри устроен как связный список блоков. Добавление и удаление с обоих концов — гарантированно O(1).

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

🧰 Code Cleanup

Плохой код

f = open("data.txt")
content = f.read()
f.close()

Работает. Но это бомба замедленного действия.

Что не так
Если между open и close вылетит исключение — close() никогда не выполнится. Файловый дескриптор остаётся открытым.

f = open("data.txt")
data = json.loads(f.read())   # ← упало с JSONDecodeError
f.close()                      # ← сюда мы уже не дошли

Один такой баг в цикле — и через час процесс падает с OSError: Too many open files. Лимит файловых дескрипторов в системе не резиновый.

Это касается не только файлов: сокеты, соединения с БД, lock'и, любые ресурсы, которые нужно явно освобождать.

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

with open("data.txt") as f:
    content = f.read()

with гарантирует, что close() вызовется при выходе из блока — независимо от того, было ли исключение.

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

🧠 Interview Thinking

Задача
Даны две строки. Вернуть True, если одна — анаграмма другой (содержит те же символы в любом порядке).

"listen", "silent"  → True
"hello",  "world"   → False
"rat",    "car"     → False

Как думает junior
«Отсортирую обе и сравню»:

def is_anagram(s1, s2):
    return sorted(s1) == sorted(s2)

Одна строка. Работает. Сложность — O(n log n) из-за сортировки.

На собесе это пройдёт. Но если интервьюер спросит «а быстрее можно?» — junior часто застревает.

Как думает сильный кандидат
Перед кодом задаёт себе вопрос: «Что я вообще проверяю?»
Не порядок символов. А то, что у каждой буквы одинаковое количество вхождений в обеих строках.

Это сравнение частот. Значит — счётчик.

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

Counter строится за O(n), сравнение двух Counter'ов — тоже O(n). Итого — O(n) по времени.

Edge case, который ловит интервьюер
Что если строки разной длины? Сортировка и Counter оба корректно вернут False — длина учтётся автоматически.

Но умный кандидат проверяет длину явно в начале:

def is_anagram(s1, s2):
    if len(s1) != len(s2):
        return False
    return Counter(s1) == Counter(s2)

Зачем? Это ранний выход за O(1). Если длины разные — даже Counter строить не нужно. На больших строках экономит время.
Это маленький штрих, но он показывает: ты не просто решаешь, а думаешь про производительность.

Уточнения, которые поднимают тебя выше
Сильный кандидат сам спросит ещё до кода:

«Регистр важен?» — "Listen" и "silent" — анаграммы?

«Пробелы учитываем?» — "conversation" и "voices rant on"?

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

🎭 Red Flag

Перехватываем ошибку и кидаем свою:

def load_config(path):
    try:
        with open(path) as f:
            return json.loads(f.read())
    except Exception:
        raise ValueError("Не удалось загрузить конфиг")

Выглядит чисто. На вызывающей стороне — понятное сообщение. Вроде всё хорошо.
Пока что-то не сломается в проде.

Что не так
Ты только что выкинул всю информацию о реальной причине.

Было:
FileNotFoundError: [Errno 2] No such file: '/etc/app.conf'
JSONDecodeError: Expecting value: line 3 column 1 (char 47)
PermissionError: [Errno 13] Permission denied

Стало:
ValueError: Не удалось загрузить конфиг

Дебажить такое — кошмар. В логах нет ни traceback'а оригинала, ни строки в JSON, ни пути файла. Только бесполезное сообщение.

Как надо — raise ... from

try:
    with open(path) as f:
        return json.loads(f.read())
except Exception as e:
    raise ValueError("Не удалось загрузить конфиг") from e

from e прицепляет оригинальное исключение к новому. В логах теперь увидишь:

JSONDecodeError: Expecting value: line 3 column 1

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

ValueError: Не удалось загрузить конфиг

Сохраняется обе части: твоё человекочитаемое сообщение и техническая причина.

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

📈 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