⏱️ Big O Breakdown

Посмотри на код:

def strange(n):
    i = n
    while i > 1:
        for j in range(i):
            print(j)
        i //= 2

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

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

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

Да, не O(n log n). И вот почему 👇

🧠 Разбираем пошагово:

Первая итерация:
цикл на n операций

Вторая:
n/2

Третья:
n/4

Потом:
n/8
и так далее…

Суммарно получаем:

n + n/2 + n/4 + n/8 + ...

Это убывающая геометрическая прогрессия.
Её сумма стремится к 2n.

А значит итоговая сложность — O(n).

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

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

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

✅ Правильный ответ: [1, 2, 3, 4]

🧠 Разбираем:

Строка:

lst += [4]

Для списка это in-place изменение.
Объект x действительно меняется.

А вот дальше:

lst = [0]

Это уже просто переопределение локальной переменной lst.
К исходному списку x это отношения не имеет.

Именно поэтому:

x стал [1, 2, 3, 4]

🔹присваивание [0] не повлияло на него

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

Коллизия — ситуация, когда разные ключи дают одинаковый хеш или попадают в один индекс хеш-таблицы.

Как обходится

Open Addressing (открытая адресация)

🔹 Если ячейка занята — ищется следующая свободная

Используются стратегии:

🔹линейное пробирование

🔹квадратичное

🔹двойное хеширование

Так работает dict в Python.

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

📈 From O(n²) to O(n)
Задача: найти два числа в массиве, сумма которых равна target

Это одна из классических задач, которую очень любят на Python-собеседованиях.

❌ Неоптимальное решение — O(n²)

nums = [3, 7, 2, 9, 7, 5]
target = 14

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            print(i, j)

Идея простая:
для каждого элемента проверяем все остальные.

Работает.
Но у такого решения квадратичная сложность O(n²).

Если элементов станет много, программа начнёт работать заметно медленнее.

✅ Оптимальное решение — O(n)

nums = [3, 7, 2, 9, 7, 5]
target = 14
seen = {}

for i, num in enumerate(nums):
    need = target - num
    if need in seen:
        print(seen[need], i)
    seen[num] = i

🧠 Что изменилось

🔹 массив проходим только один раз
🔹 используем словарь (hash map) для хранения уже просмотренных чисел
🔹 проверка in dict работает за O(1)

В итоге получаем линейную сложность O(n) вместо O(n²).

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

❌ Rookie Mistakes

Тема: изменяемый объект как значение по умолчанию

Это одна из самых коварных ошибок в Python.
Многие новички даже не подозревают, что здесь происходит.

❌ Ошибка

def add_item(item, items=[]):
    items.append(item)
    return items

print(add_item(1))
print(add_item(2))
print(add_item(3))

На первый взгляд кажется, что функция каждый раз создаёт новый список.

Но вывод будет такой:

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

🧠 Почему так происходит

Значения по умолчанию в Python создаются один раз — в момент определения функции, а не при каждом вызове.

Поэтому список items используется один и тот же при каждом вызове функции.

✅ Правильный вариант

def add_item(item, items=None):
    if items is None:
        items = []
    items.append(item)
    return items

print(add_item(1))
print(add_item(2))
print(add_item(3))

Теперь список будет создаваться каждый раз заново, и функция будет работать ожидаемо.

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

В Python используется модель call by object reference (передача ссылки на объект).

Это означает:

🔹 В функцию передаётся ссылка на объект
🔹 Но сама ссылка передаётся по значению

в Python аргументы передаются по ссылке на объект, но переприсваивание внутри функции не влияет на внешний объект

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

⏱️ Big O Breakdown

Разберём пример.

import math

n = 1000000
i = 1

while i * i <= n:
    i += 1

❓ Вопрос: какая здесь временная сложность?

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

✅ Ответ: O(√n)

🧠 Разбор

Цикл работает, пока выполняется условие:

i * i <= n


Это то же самое что:

i <= √n


То есть переменная i увеличится примерно до корня из n.

Если n = 1 000 000,
цикл выполнится примерно 1000 раз, а не миллион.

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

Оконные функции — функции SQL, которые выполняют вычисления по группе строк (окну), при этом не объединяют строки в одну, как это делает GROUP BY.

Каждая строка сохраняется, а результат вычисления добавляется к ней.

Как задаётся окно

🔹 PARTITION BY — разбивает данные на группы
🔹 ORDER BY — задаёт порядок внутри группы

Частые функции

🔹 ROW_NUMBER() — нумерация строк
🔹 RANK() — ранжирование
🔹 SUM() / AVG() — агрегаты по окну
🔹 LAG() / LEAD() — доступ к соседним строкам

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

📈 From O(n²) to O(n)
Задача: проверить, есть ли в строке повторяющиеся символы

Очень частая задача на собеседованиях.

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

def has_duplicates(s):
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if s[i] == s[j]:
                return True
    return False

Логика простая:
каждый символ сравниваем со всеми остальными.

Работает.
Но это два вложенных цикла —> O(n²).

На длинных строках будет медленно.

✅ Оптимальное решение — O(n)

def has_duplicates(s):
    seen = set()

    for char in s:
        if char in seen:
            return True
        seen.add(char)

    return False

🧠 Что изменилось

🔹 строку проходим один раз
🔹 используем set для хранения символов
🔹 проверка in set работает за O(1)

В итоге вся функция работает за O(n).

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

⏱️ Big O Breakdown

Посмотри на код:

def process(n):
    i = 1
    while i < n:
        for j in range(i):
            print(j)
        i *= 2

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

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

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

🧠 Разбираем

Значение i растёт так:

1
2
4
8
16
...


То есть цикл выполняется log n раз.

Но внутренний цикл каждый раз работает:

1
2
4
8
16
...

Если сложить все итерации:

1 + 2 + 4 + 8 + ... + n

Это геометрическая прогрессия.

Её сумма примерно 2n

📌 Итог

Общее количество операций примерно 2n

А значит итоговая сложность:

O(n)

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

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

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

Разбор по шагам:

1️⃣ Список изначально

[1, 2, 3]

2️⃣ Первая итерация
i = 1
ничего не происходит.

3️⃣ Вторая итерация
i = 2
выполняется:

x.remove(2)

Список становится:

[1, 3]

4️⃣ Итератор пытается перейти к следующему индексу,
но список уже сократился, поэтому цикл завершается.

Итог:

[1, 3]

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

🧰 Code Cleanup — выпуск 27
Тема: лишний else после return

Иногда код работает нормально, но читается тяжелее, чем должен.

❌ Плохо:

def check_age(age):
    if age >= 18:
        return "adult"
    else:
        return "minor"

Функция работает.
Но else здесь вообще не нужен.

✅ Code Cleanup:

def check_age(age):
    if age >= 18:
        return "adult"
    return "minor"

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

🔹 код короче
🔹 меньше уровней вложенности
🔹 читается быстрее
🔹 легче поддерживать

После return выполнение функции и так заканчивается,
поэтому else становится лишним.

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

REST (Representational State Transfer) — архитектурный стиль построения веб-сервисов, использующий возможности HTTP.

Основные принципы

🔹 HTTP-методы по назначению
GET — получение
POST — создание
PUT / PATCH — обновление
DELETE — удаление

🔹 Stateless — сервер не хранит состояние клиента между запросами

🔹 Единый интерфейс — предсказуемая структура URL и ответов

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

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

⏱️ Big O Breakdown

Посмотри на код:

def example(n):
    for i in range(n):
        j = 1
        while j < n:
            print(i, j)
            j *= 2

❓ Какая здесь сложность?

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

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

🧠 Разбор

Внешний цикл:

for i in range(n)


выполняется n раз → O(n)

Внутренний цикл:

j *= 2


значение растёт так:

1 —> 2 —> 4 —> 8 —> 16 —> ...


Количество шагов примерно log₂(n) —> O(log n)

Теперь объединяем:

O(n) * O(log n) = O(n log n)

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

🧰 Code Cleanup — выпуск 28
Тема: лишний вызов len()

Иногда код делает одну и ту же работу несколько раз.

❌ Плохо:

def get_last(nums):
    if len(nums) > 0:
        return nums[len(nums) - 1]
    return None

Работает.
Но выглядит тяжелее, чем должен.

✅ Code Cleanup:

def get_last(nums):
    if nums:
        return nums[-1]
    return None

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

🔹 if nums — питоничный способ проверить пустоту
🔹 nums[-1] сразу берёт последний элемент
🔹 код короче и читается быстрее
🔹 не вызываем len() лишний раз

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

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

Задача: проверить, является ли строка анаграммой другой строки.
(то есть состоят ли строки из одинаковых символов)

Например:

"listen" и "silent" → True

❌ Популярное решение — O(n log n)

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

Почему O(n log n)?

Потому что sorted() использует сортировку,
а сортировка имеет сложность O(n log n).

Работает нормально…
но можно сделать быстрее.

✅ Оптимальное решение — O(n)

from collections import Counter

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

🧠 Почему теперь O(n)

Мы просто считаем,
сколько раз встречается каждый символ.

Например:

listen —> {l:1, i:1, s:1, t:1, e:1, n:1}
silent —> {s:1, i:1, l:1, e:1, n:1, t:1}


И сравниваем два словаря.

Один проход по строке —> O(n).

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

HTTP/1.1 — самая распространённая версия, долгое время была стандартом интернета.
Особенности:

🔹 постоянные соединения (keep-alive)
🔹 текстовый протокол
🔹 один запрос за раз в одном соединении

HTTP/2 — современная версия, используемая большинством браузеров и серверов.

🔹 бинарный протокол
🔹 мультиплексирование (несколько запросов в одном соединении)
🔹 сжатие заголовков
🔹 уменьшение задержек

HTTP/3 — новейшая версия.

🔹 работает поверх QUIC (UDP)
🔹 быстрее устанавливает соединение
🔹 лучше работает при потере пакетов

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