Prosto Python | вопросы с собесов

📈 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(ii, n + 1, i): is_prime[j] = False return [i for i, v in enumerat...

⏱️ 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 + ...

🧩 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 — сю...

Diamond problem — проблема множественного наследования, когда класс получает один и тот же базовый класс по двум путям. Схема A / \ B C \ / D 🔹 D наследуется от B и C 🔹 B и C наследуются от A В чём проблема 🔹 Неочевидно, какой метод из A будет вызван 🔹 Возможен двойной вызов конструктора 🔹 Возникает неоднозначность порядка вызовов 🐍Вопросы с собесов -> 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 вычис...

📈 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)): win...

🧩 Code Cleanup Декораторы: не пиши один и тот же код дважды Часто вижу такое: def get_user(user_id): print(f"Вызов get_user с {user_id}") result = db.query(user_id) print(f"get_user выполнился за ...") return result def get_orders(user_id): print(f"Вызов get_orders с {user_id}") result = db.query_orders(user_id) print(f"get_orders выполнился за ...") return result Логирование копируется в каждую функцию. Если нужно что-то поменять — правишь везде. После: import functools import time def log(fun...

⏱️ Big O Breakdown sorted() vs list.sort(): в чём разница по памяти Оба сортируют. Оба используют Timsort. Какова сложность каждого? nums = [3, 1, 4, 1, 5, 9, 2, 6] result = sorted(nums) nums.sort() Варианты: А) Оба O(n log n) время, O(1) память Б) sorted — O(n log n) / O(n), list.sort() — O(n log n) / O(1) В) Оба O(n log n) время, O(n) память Г) sorted — O(n), list.sort() — O(n log n) Ответ: Б Алгоритм один и тот же — Timsort, O(n log n) в среднем и худшем случае. Разница в памяти. list.sort() ...

🧠 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: Не ищу пары — ищу до...

🧩 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]) # Tr...