Python: от основ до собеседования и работы / Подготовка к собеседованию / урок 96 из 99

Live coding: как решать задачи вслух

⏱ 60 мин · 🧩 заданий: 6

Что оценивают на live coding

Не только «решил или нет». Интервьюер заполняет примерно такую форму:

Понимание задачи — уточнил ли условие и граничные случаи.
Решение — пришёл ли к рабочему и эффективному алгоритму, знает ли его сложность.
Код — понятные имена, разбиение на функции, идиоматичный Python.
Проверка — тестирует ли сам, находит ли свои ошибки.
Коммуникация — объясняет ли ход мысли, реагирует ли на подсказки.

Кандидат, который решил задачу молча за 15 минут, часто получает оценку ниже, чем тот, кто решал 30 минут, но всё время понятно рассуждал и сам нашёл баг.

Алгоритм на 45 минут

1. Уточнить (3–5 мин) входные данные, размеры, граничные случаи, формат ответа 2. Примеры (2–3 мин) свой маленький пример + крайние случаи 3. Идея (5–10 мин) наивное решение → его сложность → как улучшить 4. Код (15 мин) сначала скелет, потом детали; комментировать вслух 5. Проверка (5 мин) прогнать пример руками, крайние случаи, исправить баги 6. Анализ (2 мин) сложность по времени и памяти, что можно улучшить

1. Уточнить

Вопросы, которые почти всегда уместны:

Какой размер входа? (1000 элементов или 10⁹ — разные решения.)
Могут ли быть пустые данные, дубликаты, отрицательные числа, None?
Отсортированы ли данные? Можно ли менять вход?
Что вернуть, если ответа нет? Какой порядок результата?
Важнее скорость или память?

2–3. Примеры и идея

Проговорите наивное решение, даже если оно плохое: «Можно перебрать все пары — это O(n²). Для n = 10⁵ это 10¹⁰ операций, слишком медленно. Нужен быстрый поиск дополнения — заведу множество...». Это показывает, что вы видите компромиссы, и даёт запасной вариант.

Шаблоны из модуля про алгоритмы: хеш-таблица для поиска за O(1), два указателя и скользящее окно для массивов и строк, сортировка + проход, стек для вложенности, BFS/DFS для графов и сеток, куча для top-k, бинарный поиск по ответу, ДП для «сколько способов» и «оптимум».

4. Код

def solve(data):
    # 1. частный случай
    if not data:
        return []
    # 2. подготовка: словарь, сортировка…
    # 3. основной цикл
    # 4. результат

Сначала напишите скелет с комментариями-шагами, потом заполняйте.
Говорите, что пишете и зачем: «тут храню индекс последнего вхождения, чтобы сдвигать левую границу окна».
Используйте стандартную библиотеку: collections.Counter, defaultdict, deque, heapq, bisect, itertools — это плюс, а не «жульничество». Если сомневаетесь — спросите, можно ли.
Не оптимизируйте преждевременно, но не пишите O(n²) там, где обсудили O(n).

5. Проверка

Не говорите «готово» сразу. Прогоните маленький пример по коду, строчка за строчкой, с текущими значениями переменных. Затем крайние случаи: пустой вход, один элемент, все одинаковые, максимум. Половина багов — на границах циклов и в пустых входах.

6. Анализ

«Время O(n log n) из-за сортировки, дополнительная память O(n) на словарь. Если бы данные были отсортированы, можно было бы двумя указателями за O(n) и O(1) памяти.»

Если застряли

Скажите вслух, что именно не получается: «не понимаю, как избежать повторного подсчёта».
Решите задачу руками на маленьком примере и посмотрите, что вы делаете интуитивно.
Упростите: решите для отсортированных данных, для n ≤ 10, без одного из ограничений.
Переберите шаблоны: «а если хеш-таблица? а если отсортировать? а если с конца?»
Принимайте подсказки — это нормально и ожидаемо. Плохо — игнорировать их.
Если время уходит — доведите до конца рабочее наивное решение и расскажите, как улучшили бы.

Разбор решения вслух: пример

Задача: «Найдите в строке длину самой длинной подстроки без повторяющихся символов».

— Уточню: строка может быть пустой? Учитываем регистр? Только ASCII или любой Юникод? Ок. — Наивно: перебрать все подстроки и проверить каждую — O(n³) или O(n²) с множеством. Для длинных строк медленно. — Заметил: если подстрока [left, right) без повторов, а символ s[right] уже в ней, то все подстроки с началом до позиции его прошлого вхождения тоже содержат повтор. Значит, левую границу можно сразу прыгнуть за это вхождение. Это скользящее окно, O(n). — Буду хранить словарь «символ → последний индекс».

def longest_unique(s: str) -> int:
    last_seen = {}
    best = left = 0
    for right, ch in enumerate(s):
        if last_seen.get(ch, -1) >= left:       # символ внутри текущего окна
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

# проверка: обычные и крайние случаи
for s, expected in [("abcabcbb", 3), ("bbbbb", 1), ("pwwkew", 3), ("", 0), ("a", 1), ("abba", 2)]:
    result = longest_unique(s)
    print(f"{s!r:12} → {result} {'✓' if result == expected else '✗ ожидалось ' + str(expected)}")

— "abba" — коварный случай: когда встречаем вторую a, её прошлый индекс 0 уже левее окна, поэтому проверяю >= left. Время O(n), память O(размер алфавита).

Пройдите пример 👣 Пошагово и посмотрите, как двигаются left и right.

Частые ошибки

Начать писать код, не поняв задачу (и решить другую).
Молчать.
Спорить с подсказками или защищать заведомо медленное решение.
Не проверить код на примере и пустом входе.
Изменять список во время обхода, забыть return, перепутать < и <= на границе.
Переусложнять: писать класс и три вспомогательные функции там, где хватит пяти строк.

Задачи для тренировки

Ниже шесть задач в формате настоящего интервью. Засеките 25–30 минут на задачу, решайте вслух (можно записывать себя на диктофон), сначала уточняющие вопросы и примеры, потом код. Автопроверка покажет, какие случаи вы упустили.

Итог

Уточнить → примеры → наивное решение → оптимизация → код → проверка → сложность.
Думать вслух, принимать подсказки, тестировать самому.
Знать шаблоны и стандартную библиотеку — половина успеха.

Практика решено 0 из 6

Вы не вошли — ответы проверяются, но прогресс не сохранится. Войти или зарегистрироваться.

Задание 1 Программа на Python

Группировка анаграмм. Дан список слов. Сгруппируйте анаграммы (слова из одних и тех же букв). Верните список групп; внутри группы сохраните исходный порядок слов, группы упорядочьте по первому появлению. Ожидаемая сложность — O(n · k log k), где k — длина слова (или O(n · k) с подсчётом букв).

def group_anagrams(words):
    groups = []
    for w in words:
        for g in groups:
            if sorted(g[0]) == sorted(w):
                g.append(w)
                break
        else:
            groups.append([w])
    return groups

Какие тесты проверяют код (3)

assert group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) == [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
assert group_anagrams([]) == [] and group_anagrams(["", ""]) == [["", ""]] and group_anagrams(["ab", "ba", "abc"]) == [["ab", "ba"], ["abc"]]
import random, string
class W(str):                      # слово, которое считает, сколько раз его перебирали по буквам
    reads = 0
    def __iter__(self):
        W.reads += 1
        return super().__iter__()
r = random.Random(3)
words = [W("".join(r.choices(string.ascii_lowercase[:6], k=6))) for _ in range(2000)]
W.reads = 0
groups = group_anagrams(words)
assert sum(map(len, groups)) == 2000
assert W.reads <= 2 * len(words), "Каждое слово нужно разобрать один раз; сравнение с каждой группой — это O(n²)"

Эталонное решение (ваше может отличаться):

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)          # dict сохраняет порядок первого появления ключа
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

Задание 2 Программа на Python

LRU-кеш. Реализуйте класс LRUCache(capacity) с методами get(key) (значение или -1) и put(key, value). При переполнении удаляется давно не использованный ключ; get и put считаются использованием. Обе операции — O(1). Подсказка: collections.OrderedDict и move_to_end.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}

    def get(self, key):
        return self.data.get(key, -1)

    def put(self, key, value):
        if len(self.data) >= self.capacity:
            self.data.pop(next(iter(self.data)))
        self.data[key] = value

Какие тесты проверяют код (2)

c = LRUCache(2)
c.put(1, "a"); c.put(2, "b")
assert c.get(1) == "a"          # 1 стал свежим
c.put(3, "c")                   # вытесняется 2
assert c.get(2) == -1 and c.get(3) == "c" and c.get(1) == "a"

c = LRUCache(2)
c.put(1, 1); c.put(2, 2); c.put(1, 10)   # обновление тоже использование
c.put(3, 3)                               # вытесняется 2
assert (c.get(1), c.get(2), c.get(3)) == (10, -1, 3)
c = LRUCache(1); c.put("x", 1); c.put("y", 2)
assert c.get("x") == -1 and c.get("y") == 2

Эталонное решение (ваше может отличаться):

from collections import OrderedDict

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

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

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

Задание 3 Программа на Python

Выравнивание вложенной структуры. Напишите генератор flatten(data), который обходит произвольно вложенные списки и кортежи и выдаёт «листья» по порядку. Строки и байты — листья (не разбивать на символы!), словари — тоже листья. Глубина вложенности может быть больше предела рекурсии (до 5000), поэтому решите итеративно со стеком итераторов.

def flatten(data):
    for item in data:
        if isinstance(item, (list, tuple)):
            yield from flatten(item)
        else:
            yield item

Какие тесты проверяют код (3)

assert list(flatten([1, [2, (3, [4])], [], "ab", [{"k": 1}], b"x"])) == [1, 2, 3, 4, "ab", {"k": 1}, b"x"]
import types; assert isinstance(flatten([1]), types.GeneratorType) and list(flatten([])) == []
deep = [7]
for _ in range(5000):
    deep = [deep]
assert list(flatten([1, deep, 2])) == [1, 7, 2]

Эталонное решение (ваше может отличаться):

def flatten(data):
    stack = [iter(data)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, (list, tuple)):
                stack.append(iter(item))
                break
            yield item
        else:
            stack.pop()

Задание 4 Программа на Python

Ограничитель частоты запросов. Реализуйте RateLimiter(limit, window): метод allow(user, now) возвращает True, если за последние window секунд (полуинтервал (now - window, now]) у пользователя было меньше limit разрешённых запросов, и тогда запоминает этот запрос; иначе False (отклонённые запросы не учитываются). Время now передаётся явно (секунды, неубывающие). Каждый вызов — амортизированно O(1): храните для каждого пользователя deque времён и выбрасывайте устаревшие слева.

class RateLimiter:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.counts = {}

    def allow(self, user, now):
        self.counts[user] = self.counts.get(user, 0) + 1
        return self.counts[user] <= self.limit

Какие тесты проверяют код (2)

rl = RateLimiter(limit=2, window=10)
assert [rl.allow("a", t) for t in (0, 1, 2, 9)] == [True, True, False, False]
assert rl.allow("b", 2) is True, "Лимиты у пользователей независимы"
assert rl.allow("a", 10) is True and rl.allow("a", 10.5) is False and rl.allow("a", 11) is True

rl = RateLimiter(limit=3, window=1)
assert sum(rl.allow("u", i / 10) for i in range(10)) == 3
assert all(rl.allow("u", 100 + i) for i in range(50))

Эталонное решение (ваше может отличаться):

from collections import defaultdict, deque

class RateLimiter:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.hits = defaultdict(deque)

    def allow(self, user, now):
        q = self.hits[user]
        while q and q[0] <= now - self.window:
            q.popleft()
        if len(q) < self.limit:
            q.append(now)
            return True
        return False

Задание 5 Программа на Python

Анализ логов. Строки лога имеют вид 2026-03-01T12:00:03 GET /api/orders 200 0.153 (время, метод, путь, статус, длительность в секундах). Напишите analyze(lines, top=3), возвращающую словарь:

"total" — число корректных строк (строки с другим числом полей или нечисловым статусом/длительностью пропускайте);
"errors" — доля ответов со статусом ≥ 500, округлённая до 3 знаков (0, если строк нет);
"slowest" — список из top путей с наибольшей средней длительностью, по убыванию (при равенстве — по алфавиту), элементы — кортежи (path, средняя_длительность_округлённая_до_3_знаков);
"by_status" — словарь статус (int) → количество.

def analyze(lines, top=3):
    return {"total": len(lines), "errors": 0, "slowest": [], "by_status": {}}

Какие тесты проверяют код (2)

log = [
    "2026-03-01T12:00:01 GET /api/orders 200 0.150",
    "2026-03-01T12:00:02 GET /api/orders 200 0.250",
    "2026-03-01T12:00:03 POST /api/pay 502 1.200",
    "битая строка",
    "2026-03-01T12:00:04 GET /health 200 0.002",
    "2026-03-01T12:00:05 GET /api/users 500 0.200",
    "2026-03-01T12:00:06 GET /api/users 200 abc",
]
r = analyze(log, top=2)
assert r["total"] == 5 and r["errors"] == 0.4
assert r["slowest"] == [("/api/pay", 1.2), ("/api/orders", 0.2)]
assert r["by_status"] == {200: 3, 502: 1, 500: 1}

assert analyze([]) == {"total": 0, "errors": 0, "slowest": [], "by_status": {}}
r = analyze(["t GET /b 200 0.5", "t GET /a 200 0.5", "t GET /c 200 0.1"], top=5)
assert r["slowest"] == [("/a", 0.5), ("/b", 0.5), ("/c", 0.1)]

Эталонное решение (ваше может отличаться):

from collections import Counter, defaultdict

def analyze(lines, top=3):
    total, errors = 0, 0
    by_status = Counter()
    durations = defaultdict(list)
    for line in lines:
        parts = line.split()
        if len(parts) != 5:
            continue
        _, _, path, status, duration = parts
        try:
            status, duration = int(status), float(duration)
        except ValueError:
            continue
        total += 1
        by_status[status] += 1
        errors += status >= 500
        durations[path].append(duration)
    averages = [(path, round(sum(d) / len(d), 3)) for path, d in durations.items()]
    averages.sort(key=lambda item: (-item[1], item[0]))
    return {
        "total": total,
        "errors": round(errors / total, 3) if total else 0,
        "slowest": averages[:top],
        "by_status": dict(by_status),
    }

Задание 6 Программа на Python

Свободное время для встречи. Даны занятые интервалы нескольких людей (списки пар (начало, конец) в минутах от начала дня, могут пересекаться и быть не отсортированы), рабочий день (day_start, day_end) и длительность встречи duration. Верните список свободных у всех окон (начало, конец) длиной не меньше duration, отсортированный по началу.

def free_slots(busy, day, duration):
    return [day]

Какие тесты проверяют код (2)

anna = [(540, 600), (720, 780)]        # 9:00–10:00, 12:00–13:00
boris = [(570, 630), (900, 960)]       # 9:30–10:30, 15:00–16:00
assert free_slots([anna, boris], (540, 1080), 30) == [(630, 720), (780, 900), (960, 1080)]
assert free_slots([anna, boris], (540, 1080), 120) == [(780, 900), (960, 1080)]
assert free_slots([anna, boris], (540, 1080), 121) == []

assert free_slots([], (600, 660), 60) == [(600, 660)] and free_slots([], (600, 660), 61) == []
assert free_slots([[(500, 700)]], (540, 1080), 30) == [(700, 1080)]
assert free_slots([[(1000, 1200)], [(560, 580)]], (540, 1080), 20) == [(540, 560), (580, 1000)]
assert free_slots([[(600, 650), (640, 700)]], (600, 700), 1) == []

Эталонное решение (ваше может отличаться):

def free_slots(busy, day, duration):
    day_start, day_end = day
    intervals = sorted(iv for person in busy for iv in person)
    result, cursor = [], day_start
    for start, end in intervals:
        if start > cursor:
            free_end = min(start, day_end)
            if free_end - cursor >= duration:
                result.append((cursor, free_end))
        cursor = max(cursor, end)
        if cursor >= day_end:
            break
    if day_end - cursor >= duration:
        result.append((cursor, day_end))
    return result

Войдите, чтобы отмечать пройденные уроки.