Задача целиком:
решение на интервью

Категория

Разбор задачи

Уровень

Средний

Опирается на

Главы 10.2–10.7; глава 9.8: этапы interview canvas

Зачем это знать

Узнать окно в задаче, где оно не названо, и уложиться в 25 минут

§1Этапы и время

Порядок этапов — шаблон interview canvas из КТП, как в главах 8.11 и 9.8. Этапы: условие → уточнения → примеры → перебор → оптимизация → сложность → код → проверка. Ориентир — 25 минут на задачу.

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

§2Условие и пересказ

Интервьюер читает условие:

Пересказ делается по правилам, по одному выводу на правило. Сравнение из жизни помогает удержать их вместе: сборщик — это рамка, которую ведут вдоль ряда, а корзины — ограничение на то, что может оказаться внутри рамки.

Пересказ для интервьюера: «Нужно найти самый длинный подотрезок списка, в котором не больше двух разных чисел, и вернуть его длину». После этой фразы задача узнаётся по признакам из главы 10.2: участок подряд, длина не задана, на содержимое стоит ограничение. Ограничение — число разных значений, поэтому состояние окна — частотная карта, как в главе 10.5.

§3Уточнения

Ответы интервьюера взяты из ограничений LeetCode. Задайте вопросы по очереди.

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

§4Примеры

Шесть входов, записанных до кода. Первые три — примеры из условия LeetCode, остальные проверяют ответы на уточнения. Ответы получены запуском итогового решения и совпадают с перебором.

§5Перебор

Перебор следует из пересказа и устроен как перебор подстрок в главе 10.5. Для каждого начала l отрезок удлиняется вправо, виды собираются в множество, и внутренний цикл прерывается, когда видов стало три. «Проверю каждое начало и пойду вправо до третьего вида. В худшем случае, когда третьего вида нет, это n·(n + 1)/2 шагов, O(n²). При 10⁵ деревьев это около 5·10⁹ шагов, слишком долго».

def total_fruit_brute(fruits):
    best = 0
    for l in range(len(fruits)):
        kinds = set()
        for r in range(l, len(fruits)):
            kinds.add(fruits[r])
            if len(kinds) > 2:
                break
            best = max(best, r - l + 1)
    return best

Прогон на третьем примере, [1, 2, 3, 2, 2], ответ 4. Множество kinds никогда не содержит больше трёх видов: на третьем цикл прерывается. Поэтому память перебора — O(1).

Перебор повторяет ту же работу, что в главе 10.5: при переходе к следующему началу множество собирается заново. При этом отрезок с началом l + 1 почти совпадает с уже пройденным.

§6Оптимизация: окно с частотной картой

Это задача на самый длинный отрезок, поэтому схема — из главы 10.3: расширить окно, сжать, пока оно недопустимо, записать длину после цикла while. Остаётся выбрать состояние окна и записать через него условие допустимости.

Условие — «в окне не больше двух разных видов». Частотная карта из главы 10.5 хранит для каждого вида, сколько деревьев этого вида в окне. Если в карте лежат только виды, которые в окне есть, то число разных видов — это число ключей, len(count). Условие допустимости — len(count) <= 2, условие цикла сжатия — len(count) > 2.

1. Расширение. count[f] = count.get(f, 0) + 1 для вида f пришедшего дерева.
2. Сжатие. Пока len(count) > 2: уменьшить счётчик вида на левом дереве. Если счётчик стал 0, удалить ключ: вида в окне больше нет, корзина освободилась. Затем l += 1.
3. Запись. best = max(best, r - l + 1) после цикла.

В главе 10.5 ключи со счётчиком 0 оставались в словаре, и это не мешало: условие цикла читало счётчик одного символа. Здесь условие читает число ключей, поэтому ключ ушедшего вида нужно удалять. Что будет без удаления, показано в §9.

>>> count = {1: 0, 2: 1, 3: 1}
>>> len(count)
3
>>> del count[1]
>>> count
{2: 1, 3: 1}
>>> len(count)
2

Сделайте проход сами на четвёртом примере. Под лентой показана частотная карта окна; виды, которых в окне не осталось, в ней не показываются.

§7Сложность

Сложность называют до кода.

Память здесь — O(1). В главе 10.5 она была O(m), по числу разных символов. Ключи ушедших видов удаляются, а третий ключ появляется только на время сжатия. Поэтому в карте никогда не бывает больше трёх ключей, сколько бы разных видов ни было в ряду.

§8Код

На секции код пишет кандидат, поэтому до готового кода напишите функцию сами в окне ниже. «Запустить тесты» проверяет её на шести примерах из §4, на пустом ряде и сравнивает с перебором на трёхстах случайных рядах; часть тестов заготовка проходит сразу. Первый запуск загружает Python в браузер, около 10 МБ.

def total_fruit(fruits):
    count = {}
    best = 0
    l = 0
    for r in range(len(fruits)):
        f = fruits[r]
        count[f] = count.get(f, 0) + 1
        while len(count) > 2:
            count[fruits[l]] -= 1
            if count[fruits[l]] == 0:
                del count[fruits[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

Порядок строк в теле цикла while важен. Проверка count[fruits[l]] == 0 и удаление стоят до l += 1: пока l не сдвинут, fruits[l] — вид ушедшего дерева. После сдвига эта же запись означала бы уже другое дерево.

§9Проверка

Готовый код проверяют на примерах из §4. Если сжатие написать так же, как в главе 10.5, без удаления ключа, проверка на третьем примере находит ошибку сразу. Ниже два прогона на одном входе: первая версия кода и исправленная.

IndexErrorНа шаге 18 из окна уходит единственное дерево вида 1, его счётчик становится 0, но ключ остаётся. На шаге 20 в окне [2, 3] два вида, а в карте три ключа, и цикл продолжает сжимать окно. Окно становится пустым, счётчики уходят в минус, и на шаге 33 индекс l = 5 выходит за конец ряда.

4На шаге 20 ключ вида 1 удалён, и на шаге 22 в карте два ключа: окно [2, 3] допустимо. Дальше окно только расширяется, на шаге 33 записан ответ 4.

Остальные примеры проверяют быстрее. На [5, 5, 5] в карте один ключ, цикл while не выполняется ни разу, ответ 3. На [1, 2, 1, 2, 1, 2] ключей всегда два, ответ — длина ряда. На четвёртом примере цикл while срабатывает три раза. Первый раз — когда после трёх троек приходит вид 2. Второй — когда после отрезка из единиц и двоек приходит вид 3. Третий — когда после двух троек приходит вид 4. Все ответы совпадают с таблицей в §4.

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

§10Проверьте себя