Выпускной разбор и следующий цикл

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

Сначала три новых условия, затем разбор

Карточка A

Есть N учебных модулей с номерами от 0 до N-1 и пары «модуль X должен быть пройден до Y». Нужно вернуть любой порядок модулей или сообщить, что никакой порядок невозможен. N и число пар могут быть большими.

Карточка B

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

Карточка C

В рецепте сборки у каждого компонента есть зависимости. Нужно найти компоненты, которые можно начинать прямо сейчас, и обновлять этот список после завершения компонента.

До раскрытия для каждой карточки заполните лист выпускника: медленный эталон; состояние; момент, когда объект становится доступным; инвариант; альтернатива; сложность; тест на цикл. Не пишите название знакомого метода вместо этих ответов.

Раскрытие медленного эталона

Раскрытие A — после собственного листа

Можно проверять перестановки N модулей и оставлять ту, где каждая пара стоит в правильном порядке. Это быстро становится N! и не объясняет, как строить следующий элемент.

Раскрытие B — после собственного листа

Можно для каждой работы рекурсивно идти по зависимостям и отмечать путь вызовов. Это рабочая альтернатива для обнаружения цикла, но для явного порядка надо аккуратно определить момент записи работы.

Раскрытие C — после собственного листа

Полезный вопрос не «какой компонент нравится следующим?», а «какие требования у него уже закрыты?». Это даёт состояние, которое обновляется локально после одного завершения.

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

Если после завершения модуля снова сканировать все пары, чтобы найти доступные модули, одна и та же зависимость будет проверяться много раз. Для каждого модуля достаточно хранить число ещё не закрытых входящих требований и список тех, чьё число изменится после его завершения.

Раскрытие A: что делает модуль доступным

Модуль с нулём незакрытых требований можно поставить следующим без нарушения условий. После его выбора уменьшается счётчик только у его непосредственных последователей. Если все N модулей удалось выбрать, порядок существует; если очередь доступных модулей опустела раньше, оставшиеся требования образуют цикл.

Это топологическая сортировка по алгоритму Кана. Название вторично: ключевые факты — счётчик невыполненных требований и очередь именно тех модулей, которые стали доступны.

Что означает нулевой счётчик

Перед извлечением из очереди indegree[v] равен числу требований для v, чьи исходные модули ещё не добавлены в answer. Каждый модуль в очереди имеет indegree 0, поэтому его добавление не нарушает ни одной зависимости. Когда выбран u, уменьшаются счётчики только для пар u → v; переход v к нулю означает, что все его требования уже расположены раньше.

Как построить или опровергнуть порядок

1. Проверьте номера модулей и создайте список последователей для каждой зависимости X → Y.
2. Посчитайте indegree каждого Y.
3. Добавьте в очередь все модули с indegree 0.
4. Пока очередь не пуста, извлекайте модуль, добавляйте его к ответу и уменьшайте счётчики его последователей.
5. Каждый последовательно ставший нулевым счётчик добавляйте в очередь.
6. Если в ответе N модулей, верните порядок; иначе верните отсутствие порядка из-за цикла.

Код после выпускной попытки

Обе версии возвращают отсутствие результата при цикле, а не частичный список, который мог бы выглядеть убедительно, но нарушал бы контракт. Дубликат одной и той же зависимости учитывается дважды и дважды же снимается, поэтому поведение остаётся согласованным.

C++17

#include <cassert>
#include <iostream>
#include <optional>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>

using namespace std;

optional<vector<int>> buildOrder(
    int moduleCount,
    const vector<pair<int, int>>& requirements
) {
    if (moduleCount < 0) throw invalid_argument("module count must be non-negative");

    vector<vector<int>> next(moduleCount);
    vector<int> indegree(moduleCount, 0);
    for (auto [before, after] : requirements) {
        if (before < 0 || before >= moduleCount || after < 0 || after >= moduleCount) {
            throw invalid_argument("module index out of range");
        }
        next[before].push_back(after);
        ++indegree[after];
    }

    queue<int> ready;
    for (int module = 0; module < moduleCount; ++module) {
        if (indegree[module] == 0) ready.push(module);
    }

    vector<int> order;
    while (!ready.empty()) {
        int module = ready.front();
        ready.pop();
        order.push_back(module);
        for (int after : next[module]) {
            --indegree[after];
            if (indegree[after] == 0) ready.push(after);
        }
    }
    if (static_cast<int>(order.size()) != moduleCount) return nullopt;
    return order;
}

bool respectsRequirements(
    const vector<int>& order,
    const vector<pair<int, int>>& requirements
) {
    vector<int> position(order.size());
    for (int index = 0; index < static_cast<int>(order.size()); ++index) {
        position[order[index]] = index;
    }
    for (auto [before, after] : requirements) {
        if (position[before] >= position[after]) return false;
    }
    return true;
}

int main() {
    vector<pair<int, int>> requirements = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
    auto order = buildOrder(4, requirements);
    assert(order && respectsRequirements(*order, requirements));
    assert(!buildOrder(2, {{0, 1}, {1, 0}}));
    assert(buildOrder(0, {}).value().empty());
    cout << "ok\n";
}

Python 3

from collections import deque


def build_order(
    module_count: int, requirements: list[tuple[int, int]]
) -> list[int] | None:
    if module_count < 0:
        raise ValueError("module count must be non-negative")

    next_modules = [[] for _ in range(module_count)]
    indegree = [0] * module_count
    for before, after in requirements:
        if not (0 <= before < module_count and 0 <= after < module_count):
            raise ValueError("module index out of range")
        next_modules[before].append(after)
        indegree[after] += 1

    ready = deque(
        module for module in range(module_count) if indegree[module] == 0
    )
    order: list[int] = []
    while ready:
        module = ready.popleft()
        order.append(module)
        for after in next_modules[module]:
            indegree[after] -= 1
            if indegree[after] == 0:
                ready.append(after)

    return order if len(order) == module_count else None


def respects_requirements(
    order: list[int], requirements: list[tuple[int, int]]
) -> bool:
    position = [0] * len(order)
    for index, module in enumerate(order):
        position[module] = index
    return all(position[before] < position[after] for before, after in requirements)


requirements = [(0, 1), (0, 2), (1, 3), (2, 3)]
order = build_order(4, requirements)
assert order is not None and respects_requirements(order, requirements)
assert build_order(2, [(0, 1), (1, 0)]) is None
assert build_order(0, []) == []
print("ok")

Почему каждая зависимость обрабатывается один раз

Создание графа занимает O(N + E) памяти. Каждый модуль входит и выходит из очереди не более одного раза, каждая пара X → Y уменьшает один счётчик один раз: время O(N + E). Это лучше, чем перестановки или повторный полный скан всех требований после каждого выбранного модуля.

Где выпускной пример обязан сказать «нет»

• При N = 0 корректный порядок — пустой список.
• Модуль без требований должен быть доступен сразу.
• Самозависимость X → X образует цикл.
• Несвязанные компоненты могут появиться в любом относительном порядке.
• Повтор пары не меняет существование порядка, но должен быть последовательно учтён и при увеличении, и при уменьшении счётчика.
• Номер вне диапазона — ошибка входа, а не тихое игнорирование.

Четыре проверки зрелого решения

Отладка

Уберите условие «добавить в очередь только при indegree == 0». На зависимостях 0 → 2 и 1 → 2 модуль 2 станет доступен после первого уменьшения и нарушит порядок. Это точный тест против преждевременного добавления.

Границы

Проверьте N = 0, одиночный модуль, цикл длины 2, самозависимость, две независимые цепочки и индекс вне диапазона.

Сложность

Объясните, почему в графе с миллионом пар каждая пара не сканируется после каждого выбранного модуля: она хранится ровно у своего before и посещается при его извлечении.

Объяснение вслух

За минуту произнесите: «В очереди только модули без незакрытых требований. Когда я выбираю один, меняются только его последователи. Если очередь закончилась раньше модулей, оставшиеся зависят друг от друга циклически». Добавьте одну фразу о памяти.

Когда условие просит строить порядок

Сигналы: «до», «после», «предварительное требование», «зависимость», «можно ли завершить всё», «любой допустимый порядок». Сначала спросите, ориентированы ли зависимости и нужен ли именно порядок или только факт существования цикла.

Когда порядок не является всей задачей

Такое рассуждение не найдёт критический путь с длительностями, оптимальный порядок по стоимости или решение при циклических зависимостях, которые разрешены контрактом. Для динамически меняющегося графа повторный полный запуск может быть слишком дорог. Не маскируйте стоимость и ресурсы простым порядком: они требуют отдельного состояния.

Самопроверка: раннее завершение

Вопрос: почему пустая очередь до добавления всех модулей означает цикл?
Ответ: у каждого оставшегося модуля есть хотя бы одно незакрытое требование среди оставшихся. Следуя по таким требованиям в конечном множестве, мы неизбежно вернёмся к уже встреченному модулю.

Самопроверка: неединственный ответ

Вопрос: почему два разных правильных порядка не делают алгоритм неверным?
Ответ: контракт требует любой порядок, где каждая зависимость соблюдена. Если одновременно доступны несколько модулей, очередь может выбрать их по разному порядку, но инвариант нулевого indegree сохраняет корректность.

Собираем выпускной протокол с ограниченным раскрытием

Добавьте к модели длительность каждого модуля и найдите минимальное число параллельных «волн», если можно запускать все доступные модули одновременно, а каждая волна длится один шаг. Сначала определите, какой результат означает цикл. Затем сверяйтесь: одна волна состоит из всех модулей, чей indegree уже равен нулю до её запуска.

Две финальные задачи без подсказок

Выполните задачи без поиска названия паттерна и без открытия решений до окончания таймера. Для каждой сдайте самому себе короткий протокол: контракт, медленный эталон, состояние, инвариант, альтернативу, сложность, два крайних теста и устное объяснение.

Задача 1

Есть N задач и зависимости. Верните список задач, которые принадлежат хотя бы одному циклу, или пустой список. Требуется определить контракт для дубликатов и несвязных компонент.

Задача 2

Даны курсы, их длительности и требования «A до B». Верните длину самого долгого пути выполнения при неограниченном параллелизме или сообщите, что расписание невозможно.

Выпускной чек-лист без фиктивной метрики

Актуальный LeetCode 75

• Откройте официальную страницу LeetCode 75 в день начала: план заявляет 75 essential and trending interview problems, поэтому не заменяйте его старой локальной копией.
• Для каждого текущего пункта зафиксируйте дату попытки, статус «самостоятельно / с подсказкой / не начал», медленный эталон, инвариант, время, память и один крайний тест.
• Считайте пункт выпускным только после самостоятельного решения с нуля, устного объяснения и повторной попытки через несколько дней; не подменяйте это просто отметкой о прочтении решения.
• Если список на официальной странице изменится, сохраните дату синхронизации и работайте с её текущими 75 пунктами, а не с придуманным постоянным перечнем.

Дополнительная русскоязычная интервью-практика

• Проведите два 45-минутных интервью на русском: одно про массивы/строки, второе про граф или DP. Партнёр задаёт уточнения и меняет одно условие в конце.
• Решите не меньше шести задач с русским условием на доступной площадке, например Яндекс CodeRun или Яндекс Контест, без автодополнения решения и без чтения разбора до своей попытки.
• Для двух задач напишите один и тот же алгоритм на C++17 и Python, затем сравните инвариант, границы и сложность, а не синтаксис.
• Проведите один code review вслух: найдите в чужом или старом решении конкретный контрпример, исправьте его и объясните, какой тест теперь защищает от регрессии.
• В журнале повторения оставляйте факты: где остановились, что оказалось ложным предположением, какой следующий вопрос проверит этот пробел. Никаких streak, XP или рейтингов для выпуска не нужно.