Таймированная симуляция собеседования

Это самостоятельная репетиция. Поставьте таймер на 35 минут, возьмите лист и не читайте раскрытия, пока не закончится время или пока не зафиксируете полное решение. Оценивается не угадывание имени метода, а цепочка: уточнения → медленный эталон → состояние → инвариант → код → тесты.

Таймер на 35 минут: три условия без диагноза

Основная карточка A

Есть прямоугольная карта склада: 0 — свободная клетка, 1 — стеллаж. Робот стартует в верхней левой клетке и должен попасть в нижнюю правую. За ход разрешены только верх, низ, лево, право. Верните минимальное число ходов либо -1. Карта может быть пустой; закрытые старт или финиш означают -1.

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

Карточка B

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

Карточка C

Даны непересекающиеся встречи в одном дне. Нужно проверить, можно ли посетить все, если между разными зданиями нужно 10 минут на переход. Время начала и конца целочисленное.

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

Раскрытие после таймера: с чего начать

Раскрытие A — медленный эталон

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

Раскрытие B — форма состояния

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

Раскрытие C — альтернативы

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

Почему истории путей нельзя хранить целиком

В A для будущего пути важно не то, каким маршрутом робот пришёл в клетку, а минимальное число сделанных ходов. Если клетка уже достигнута за d ходов, приход в неё за d+2 не сможет улучшить ни один следующий путь при одинаковой цене каждого хода.

Раскрытие A: как открывать расстояния слоями

Положите старт в очередь с расстоянием 0. Когда извлекается клетка с расстоянием d, все её ещё не посещённые допустимые соседи впервые получают d+1. Очередь обрабатывает все клетки слоя d раньше слоя d+1, поэтому первое присваивание расстояния — минимальное.

Это поиск в ширину. Название приходит после доказательства: одинаковая цена ребра и послойная очередь делают первое посещение окончательным. При разных ценах это рассуждение уже не работает.

Что гарантирует очередь в каждый момент

У клетки с distance = d уже известен кратчайший путь длины d. В очереди расстояния не убывают. Клетка получает расстояние только один раз, когда впервые найдена из предыдущего слоя. Поэтому, когда финиш извлечён или впервые добавлен, меньшего маршрута к нему уже не существует.

Как провести разговор до кода

1. Уточните форму карты, цену ходов, диагонали и поведение закрытых клеток.
2. Верните -1 для пустой, непрямоугольной или закрытой по контракту карты; здесь непрямоугольная карта считается недопустимым вводом.
3. Положите старт в очередь и отметьте расстояние 0.
4. Извлекайте клетки, проверяйте четыре соседние координаты.
5. Разрешённому непосещённому соседу присвойте distance + 1 и добавьте его в очередь.
6. Верните расстояние финиша или -1 после исчерпания очереди.
7. Если интервьюер меняет цену ходов, остановитесь и назовите причину, по которой этот алгоритм больше не доказывает минимум.

Код после самостоятельной попытки

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

C++17

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

using namespace std;

int shortestPath(const vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return -1;

    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    for (const auto& row : grid) {
        if (static_cast<int>(row.size()) != cols) {
            throw invalid_argument("grid must be rectangular");
        }
        for (int cell : row) {
            if (cell != 0 && cell != 1) throw invalid_argument("cell must be 0 or 1");
        }
    }
    if (grid[0][0] == 1 || grid[rows - 1][cols - 1] == 1) return -1;

    vector<vector<int>> distance(rows, vector<int>(cols, -1));
    queue<pair<int, int>> frontier;
    distance[0][0] = 0;
    frontier.push({0, 0});
    const array<pair<int, int>, 4> directions = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};

    while (!frontier.empty()) {
        auto [row, col] = frontier.front();
        frontier.pop();
        if (row == rows - 1 && col == cols - 1) return distance[row][col];

        for (auto [dr, dc] : directions) {
            int nextRow = row + dr;
            int nextCol = col + dc;
            if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) continue;
            if (grid[nextRow][nextCol] == 1 || distance[nextRow][nextCol] != -1) continue;
            distance[nextRow][nextCol] = distance[row][col] + 1;
            frontier.push({nextRow, nextCol});
        }
    }
    return -1;
}

int main() {
    assert(shortestPath({{0, 0, 0}, {1, 1, 0}, {0, 0, 0}}) == 4);
    assert(shortestPath({{0}}) == 0);
    assert(shortestPath({{1}}) == -1);
    assert(shortestPath({{0, 1}, {1, 0}}) == -1);
    cout << "ok\n";
}

Python 3

from collections import deque


def shortest_path(grid: list[list[int]]) -> int:
    if not grid or not grid[0]:
        return -1

    rows = len(grid)
    cols = len(grid[0])
    for row in grid:
        if len(row) != cols:
            raise ValueError("grid must be rectangular")
        if any(cell not in (0, 1) for cell in row):
            raise ValueError("cell must be 0 or 1")
    if grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1

    distance = [[-1] * cols for _ in range(rows)]
    frontier = deque([(0, 0)])
    distance[0][0] = 0
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    while frontier:
        row, col = frontier.popleft()
        if row == rows - 1 and col == cols - 1:
            return distance[row][col]

        for dr, dc in directions:
            next_row = row + dr
            next_col = col + dc
            if not (0 <= next_row < rows and 0 <= next_col < cols):
                continue
            if grid[next_row][next_col] == 1 or distance[next_row][next_col] != -1:
                continue
            distance[next_row][next_col] = distance[row][col] + 1
            frontier.append((next_row, next_col))

    return -1


assert shortest_path([[0, 0, 0], [1, 1, 0], [0, 0, 0]]) == 4
assert shortest_path([[0]]) == 0
assert shortest_path([[1]]) == -1
assert shortest_path([[0, 1], [1, 0]]) == -1
print("ok")

Почему время зависит от числа клеток

Каждая свободная клетка добавляется в очередь не более одного раза и просматривает четыре направления. Время O(rows × cols), память O(rows × cols) на матрицу расстояний и очередь. Наличие четырёх соседей — константа; не записывайте O(4 × rows × cols) как отдельный класс сложности.

На каких условиях ломается доказательство

• Пустая карта и закрытые старт/финиш возвращают -1.
• Открытая карта 1 × 1 имеет ответ 0.
• Непрямоугольный ввод отвергается, а не индексируется случайно.
• При диагоналях нужно добавить направления и заново подтвердить контракт.
• При весах ходов 1 и 5 первое посещение больше не гарантирует кратчайшую стоимость; нужен другой алгоритм.

Четыре обязательные репетиции

Отладка

Уберите проверку distance != -1 и мысленно прогоните цикл из четырёх свободных клеток. Одна клетка начнёт добавляться снова через соседа. Объясните, какой тест должен заметить повторные посещения.

Границы

Проверьте 1 × 1, закрытый старт, закрытый финиш, отсутствие пути, карту с единственным узким коридором и прямоугольность строк.

Сложность

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

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

За 60 секунд объясните: «Все ходы стоят одинаково; очередь завершает слой d до слоя d+1; поэтому первое расстояние клетки минимально». Затем назовите точную причину, по которой это нельзя без изменений применять к разным весам.

Какие признаки требуют послойного рассуждения

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

Когда первый приход ещё не лучший

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

Самопроверка: момент ответа

Вопрос: почему можно вернуть расстояние, когда финиш впервые добавлен в очередь?
Ответ: он добавляется из клетки слоя d, значит получает d+1. До обработки слоя d+1 в очереди не может появиться путь короче; все более короткие слои уже полностью рассмотрены.

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

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

Репетируем интервью на взвешенной сетке

Измените карту так, чтобы было несколько стартовых зарядных станций и нужно найти расстояние до ближайшей для каждой свободной клетки. Сначала опишите медленный эталон. Затем сверяйтесь: все станции должны попасть в очередь с расстоянием 0 до начала обхода.

Два задания после таймера без подсказок

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

Задача 1

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

Задача 2

В матрице 0 означает проход, 1 — препятствие. Найдите минимальное число ходов от каждой клетки первого столбца до любой клетки последнего столбца или сообщите об отсутствии пути. Ходы разрешены только вверх, вниз и вправо.

Как оценить собственную собеседовательную попытку

Успешная попытка — не обязательно идеальный код за 35 минут. Она должна оставить проверяемый след: что уточнили, почему перебор не проходит, какое состояние достаточно, какой инвариант обеспечивает корректность, где код проверен и при каком изменении условия выбранный метод надо заменить.