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

Признаки

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

Пример

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

git push — команда для отправки локальных коммитов в удалённый репозиторий.

Что делает

🔹 передаёт изменения из локальной ветки в удалённую
🔹 обновляет удалённую ветку
🔹 синхронизирует состояние репозиториев

Пример

git push origin main

🔹 origin — удалённый репозиторий
🔹 main — ветка

Важно

🔹 отправляются только закоммиченные изменения

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

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

Longest Common Prefix: от O(n·m²) до O(n·m)

Задача: найти наидлиннейший общий префикс среди списка строк.

words = ["flower", "flow", "flight"]
# Ответ: "fl"

words = ["dog", "racecar", "car"]
# Ответ: ""

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

def longest_prefix(words):
    prefix = ""
    for i in range(len(words[0])):
        ch = words[0][i]
        for word in words:
            if i >= len(word) or word[i] != ch:
                return prefix
        prefix += ch
    return prefix

prefix += ch внутри цикла — конкатенация строк. Каждый раз создаётся новая строка. O(n·m²) где m — длина префикса.

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

def longest_prefix(words):
    if not words:
        return ""
    prefix = words[0]
    for word in words[1:]:
        while not word.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

O(n·m) время, O(1) дополнительной памяти.

Идея: берём первое слово как кандидат. Сравниваем с каждым следующим — укорачиваем пока не совпадёт. Никакой конкатенации — только срезы.

prefix = "flower"
"flow".startswith("flower")? Нет → "flow"
"flow".startswith("flow")?   Да
"flight".startswith("flow")? Нет → "flo" → "fl"
"flight".startswith("fl")?   Да

Ещё один подход — через zip:

def longest_prefix(words):
    prefix = []
    for chars in zip(*words):
        if len(set(chars)) == 1:
            prefix.append(chars[0])
        else:
            break
    return "".join(prefix)

zip(*words) транспонирует — даёт кортежи символов по позициям. Чисто, читаемо, O(n·m).

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

⏱️ Big O Breakdown

Генераторы vs списки. Где прячется память

Какова сложность по памяти?

# Вариант 1
def get_squares(n):
    return [x**2 for x in range(n)]

# Вариант 2
def get_squares(n):
    return (x**2 for x in range(n))

result = get_squares(1_000_000)

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

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

List comprehension создаёт весь список сразу. На миллионе элементов — миллион объектов в памяти.

Генератор не вычисляет ничего при создании. Он возвращает следующее значение только когда его просят — next() или итерация в цикле.

import sys

lst = [x**2 for x in range(1_000_000)]
gen = (x**2 for x in range(1_000_000))

sys.getsizeof(lst)  # ~8 МБ
sys.getsizeof(gen)  # ~112 байт

Когда генератор не поможет:

# Нужен random access — только список
squares = [x**2 for x in range(100)]
print(squares[42])  # OK

gen = (x**2 for x in range(100))
print(gen[42])  # TypeError — генератор не поддерживает индексы

Генератор одноразовый:

gen = (x**2 for x in range(5))
list(gen)  # [0, 1, 4, 9, 16]
list(gen)  # [] — исчерпан

После прохода генератор пуст. Список можно итерировать сколько угодно раз.

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

🧠 Interview Thinking

Обнаружение цикла в связном списке

Классика на собесах уровня middle. Задача простая на словах — сложная в реализации.

# Есть ли цикл в связном списке?
# 1 -> 2 -> 3 -> 4 -> 2 (цикл!)

Как думает junior:

Хранить все посещённые узлы в множестве:

def has_cycle(head):
    seen = set()
    curr = head
    while curr:
        if curr in seen:
            return True
        seen.add(curr)
        curr = curr.next
    return False

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

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

Алгоритм Флойда — два указателя, медленный и быстрый.

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

O(n) время, O(1) память.

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

Медленный идёт по одному шагу, быстрый — по два. Если цикл есть — быстрый догонит медленного внутри цикла. Если нет — быстрый дойдёт до None.

1 -> 2 -> 3 -> 4
          ^         |
          |_________|

slow: 1 -> 2 -> 3
fast: 1 -> 3 -> 3  встретились!

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

1. Сначала назвал решение с множеством и его сложность
2. Сам предложил оптимизацию по памяти
3. Объяснил почему fast догоняет slow — не просто «так работает»
4. Использовал "is" для сравнения узлов — это сравнение объектов, не значений

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

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

Проверка палиндрома: от O(n) памяти до O(1)

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

"racecar"  # True
"hello"    # False

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

def is_palindrome(s):
    return s == s[::-1]

Коротко и читаемо. Но s[::-1] создаёт новую строку целиком — O(n) памяти.

Два указателя — O(1) памяти:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Никакой новой строки. Два индекса идут навстречу друг другу — сравниваем символы с краёв к центру.

Ещё плюс — ранний выход. При первом несовпадении сразу возвращаем False, не проверяя остаток.

Реальный собесный вариант:

Обычно строка содержит пробелы и регистр:

def is_palindrome(s):
    s = s.lower()
    s = "".join(ch for ch in s if ch.isalnum())
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

is_palindrome("A man a plan a canal Panama")  # True

Сравнение:

s[::-1]        → O(n) время, O(n) память
два указателя  → O(n) время, O(1) память

По времени одинаково. Разница только в памяти.

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

🧩 Code Cleanup

Перестань писать длинные if-elif цепочки — используй словарь

Типичный код:

def get_discount(role):
    if role == "student":
        return 0.2
    elif role == "teacher":
        return 0.3
    elif role == "admin":
        return 0.5
    elif role == "guest":
        return 0.0
    else:
        return None

Чем больше ролей — тем длиннее функция. Добавить новый вариант — лезть внутрь и дописывать elif.

После:

DISCOUNTS = {
    "student": 0.2,
    "teacher": 0.3,
    "admin": 0.5,
    "guest": 0.0,
}

def get_discount(role):
    return DISCOUNTS.get(role)

Данные отделены от логики. Добавить новую роль — просто дописать строку в словарь.

Когда нужна функция для каждого случая:

def handle_click(action):
    if action == "save":
        save()
    elif action == "delete":
        delete()
    elif action == "export":
        export()

Тоже заменяется словарём — но значениями становятся функции:

ACTIONS = {
    "save": save,
    "delete": delete,
    "export": export,
}

def handle_click(action):
    handler = ACTIONS.get(action)
    if handler:
        handler()

Когда if-elif всё же уместен:

Если условия сложные — диапазоны, комбинации нескольких переменных, вложенная логика. Словарь заменяет только простые проверки на равенство.

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

⏱️ Big O Breakdown

copy vs deepcopy. Где прячется скрытая мутация

Какой результат выведет код?

import copy

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

shallow[0][0] = 99

print(original)
print(shallow)

Варианты:
А) [[1, 2], [3, 4]] и [[99, 2], [3, 4]]
Б) [[99, 2], [3, 4]] и [[99, 2], [3, 4]]
В) [[1, 2], [3, 4]] и [[1, 2], [3, 4]]
Г) ошибка

Ответ: Б) Оба изменились

Поверхностная копия создаёт новый список — но вложенные объекты не копирует, а копирует ссылки на них.

original → [ref_a, ref_b]
shallow  → [ref_a, ref_b]  ← те же ссылки!

shallow[0][0] = 99
→ меняем объект по ref_a
→ original[0] тоже видит изменение

Фикс — глубокая копия:

deep = copy.deepcopy(original)

deep[0][0] = 99

print(original)  # [[1, 2], [3, 4]] — не изменился
print(deep)      # [[99, 2], [3, 4]]

deepcopy рекурсивно копирует все вложенные объекты. Полная независимость.

Цена deepcopy:

import timeit

timeit.timeit("copy.copy(data)", setup="import copy; data = [[1,2]]*1000", number=10000)
# ~0.05 сек

timeit.timeit("copy.deepcopy(data)", setup="import copy; data = [[1,2]]*1000", number=10000)
# ~2.5 сек — в 50 раз медленнее

deepcopy дорогой. Используй только когда реально нужна полная независимость.

Когда что:

copy.copy()      # плоские структуры — списки чисел, строк
copy.deepcopy()  # вложенные структуры — списки списков, словари словарей
lst[:]           # быстрая поверхностная копия списка без импорта

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

🧩 Code Cleanup

Используй property вместо геттеров и сеттеров

Привычка из Java — писать геттеры и сеттеры явно:

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

    def get_name(self):
        return self._name

    def set_name(self, value):
        self._name = value

user = User("alice")
user.set_name("bob")
print(user.get_name())

В Python это антипаттерн. Код многословный, непитоничный.

После:

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

    @property
    def name(self):
        return self._name

    @name.setter
    def name(self, value):
        if not value:
            raise ValueError("Имя не может быть пустым")
        self._name = value

user = User("alice")
user.name = "bob"
print(user.name)

Обращаемся как к атрибуту — но под капотом работает логика.

Главный плюс — можно добавить логику позже:

Начал с простого атрибута:

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

Понадобилась валидация — добавил property без изменения интерфейса. Все кто писал "user.name" — ничего не заметят.

В Java пришлось бы сразу писать геттеры — иначе потом сломаешь API.

Только для чтения:

class Circle:
    def __init__(self, radius):
        self.radius = radius

    @property
    def area(self):
        return 3.14 * self.radius ** 2

c = Circle(5)
print(c.area)   # 78.5
c.area = 100    # AttributeError — нет сеттера

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

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

Подмассив с максимальной суммой: алгоритм Кадане

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

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

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

def max_subarray(nums):
    max_sum = float("-inf")
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            max_sum = max(max_sum, sum(nums[i:j+1]))
    return max_sum

Два цикла + sum внутри. O(n³) время.

С предвычисленными суммами можно до O(n²) — но это всё равно медленно.

Алгоритм Кадане — O(n):

def max_subarray(nums):
    max_sum = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)
    return max_sum

Один проход. Две переменные.

Идея:

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

current = max(num, current + num)

Если current стал отрицательным — он только тянет вниз. Выгоднее начать заново с num.

nums:    -2   1  -3   4  -1   2   1  -5   4
current: -2   1  -2   4   3   5   6   1   5
max_sum: -2   1   1   4   4   5   6   6   6

От O(n³) до O(n) — смена подхода целиком.

Не перебираем все подмассивы. Спрашиваем на каждом шаге: стоит ли продолжать?

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

🧠 Interview Thinking

Найди все уникальные пути в матрице

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

# Матрица 3x3
# S . .
# . . .
# . . E

# Ответ: 6

Как думает junior:

Рекурсия — перебрать все пути:

def count_paths(m, n):
    if m == 1 or n == 1:
        return 1
    return count_paths(m-1, n) + count_paths(n-1, m)

Много повторных вычислений. O(2^(m+n)) — экспоненциально.

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

Каждая клетка — сумма путей сверху и слева. Считаем снизу вверх.

def count_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

O(m·n) время, O(m·n) память.

Визуализация для 3x3:

1  1  1
1  2  3
1  3  6

Первая строка и столбец — всегда 1: путь только один — прямо или вниз. Каждая остальная клетка — сумма соседей сверху и слева.

Оптимизация по памяти до O(n):

def count_paths(m, n):
    row = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

Не храним всю матрицу — только одну строку.

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

1. Назвал рекурсию и её проблему — повторные вычисления
2. Предложил DP — объяснил почему dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. Сам предложил оптимизацию по памяти
4. Проверил edge cases

count_paths(1, 1)  # 1 — уже на месте
count_paths(1, n)  # 1 — только прямо

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

⏱️ Big O Breakdown

LRU Cache: что происходит когда кеш переполнен

Какова сложность операций get и put в LRU кеше?

from functools import lru_cache

@lru_cache(maxsize=3)
def heavy_compute(n):
    return n ** 2

heavy_compute(1)
heavy_compute(2)
heavy_compute(3)
heavy_compute(4)  # кеш переполнен — что вытесняется?
heavy_compute(1)  # попадёт в кеш или нет?

Варианты:
А) get O(1), put O(1) — вытесняется случайный элемент
Б) get O(n), put O(n) — вытесняется самый старый
В) get O(1), put O(1) — вытесняется давно не использованный
Г) get O(log n), put O(log n)

Ответ: В) get O(1), put O(1) — вытесняется давно не использованный

LRU — Least Recently Used. При переполнении вылетает тот элемент, к которому дольше всего не обращались.

Добавляем 1, 2, 3 → кеш: [1, 2, 3]
Добавляем 4       → вытесняем 1 (давно не использован)
                  → кеш: [2, 3, 4]
Запрашиваем 1     → промах, считаем заново
                  → вытесняем 2
                  → кеш: [3, 4, 1]

Как достигается O(1):

Под капотом — хеш-таблица + двусвязный список. Хеш-таблица даёт O(1) доступ, список отслеживает порядок использования.

# Реализация вручную через OrderedDict
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

move_to_end — O(1). popitem — O(1). Всё работает за константное время.

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

🧩 Code Cleanup

Генераторы вместо списков — когда не нужно всё сразу

Типичный код:

def get_even_squares(nums):
    result = []
    for n in nums:
        if n % 2 == 0:
            result.append(n ** 2)
    return result

squares = get_even_squares(range(1_000_000))
for sq in squares:
    print(sq)

Создаём весь список в памяти — только чтобы сразу же итерироваться по нему.

После:

def get_even_squares(nums):
    for n in nums:
        if n % 2 == 0:
            yield n ** 2

squares = get_even_squares(range(1_000_000))
for sq in squares:
    print(sq)

Память — O(1). Значения вычисляются по одному, только когда нужны.

Или через выражение-генератор:

squares = (n ** 2 for n in range(1_000_000) if n % 2 == 0)

Одна строка, никакого списка в памяти.

Когда список всё же нужен:

# Нужен random access
squares = list(get_even_squares(nums))
print(squares[42])

# Нужно пройти несколько раз
squares = list(get_even_squares(nums))
for sq in squares: ...
for sq in squares: ...  # генератор был бы уже исчерпан

Сигнал что нужен генератор:

Функция возвращает список — и его сразу итерируют. Никто не обращается по индексу, никто не проходит дважды.

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

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

Подсчёт островов: от рекурсии к BFS

Задача: дана матрица из 0 и 1. Найти количество островов — связных групп единиц.

grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"],
]
# Ответ: 3

Наивное решение — рекурсивный DFS:

def num_islands(grid):
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == "1":
                dfs(grid, i, j)
                count += 1
    return count

def dfs(grid, i, j):
    if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
        return
    if grid[i][j] != "1":
        return
    grid[i][j] = "0"
    dfs(grid, i+1, j)
    dfs(grid, i-1, j)
    dfs(grid, i, j+1)
    dfs(grid, i, j-1)

O(m·n) время — но рекурсия накапливает стек вызовов. На большой матрице — RecursionError.

Итеративный BFS — O(m·n) время, O(min(m,n)) память:

from collections import deque

def num_islands(grid):
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == "1":
                bfs(grid, i, j)
                count += 1
    return count

def bfs(grid, i, j):
    queue = deque([(i, j)])
    grid[i][j] = "0"
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == "1":
                grid[nr][nc] = "0"
                queue.append((nr, nc))

Никакой рекурсии — явная очередь. Стек не растёт.

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