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

Категория

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

Уровень

Средний

Опирается на

Главы 9.2–9.7; глава 8.11: этапы interview canvas

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

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

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

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

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

Интервьюер формулирует задачу коротко:

Первое действие — пересказать условие и дождаться подтверждения: «Я беру несколько карт с левого края и остальные с правого, всего k. Порядок ходов на сумму не влияет, важно только, сколько карт взято слева. Нужно вернуть наибольшую сумму». Пересказ уже содержит первый вывод: взятые карты — это начало ряда длины left и конец ряда длины k − left.

§3Уточнения

Вопросы те же по смыслу, что в главе 9.2, ответы взяты из ограничений LeetCode. Задайте их по очереди.

Решение меняет первый ответ: раз порядок не важен, взятые карты всегда образуют префикс и суффикс ряда, а способов всего k + 1.

§4Примеры

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

§5Перебор

Перебор следует из пересказа: для каждого left от 0 до k взять left карт слева и k − left справа и сложить. «Проверю все k + 1 способов, сумму каждого считаю срезами — это O(k) на способ, всего O(k²). При k = 10⁵ это около 10¹⁰ операций, слишком долго».

def max_card_points_brute(cards, k):
    best = 0
    for left in range(k + 1):
        right = k - left
        points = sum(cards[:left]) + sum(cards[len(cards) - right:])
        best = max(best, points)
    return best

>>> cards = [1, 2, 3, 4, 5, 6, 1]
>>> cards[len(cards) - 2:]
[6, 1]
>>> cards[len(cards) - 0:]
[]
>>> cards[-0:]
[1, 2, 3, 4, 5, 6, 1]

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

§6Оптимизация: окно в оставшихся картах

Задача похожа на окно, но окно в условии не названо: взятые карты лежат по краям, не подряд. Решение находится, если посмотреть на карты, которые остались. Пусть взяты left карт слева и k − left справа. Тогда остались карты с индекса left по left + n − k − 1. Это отрезок подряд, и его длина всегда n − k.

left = 0:   ·  ·  ·  · [5  6  1]     остались [1 2 3 4], сумма 10 → взято 22 − 10 = 12
left = 1:  [1] ·  ·  ·  · [6  1]     остались [2 3 4 5], сумма 14 → взято 22 − 14 = 8
left = 2:  [1  2] ·  ·  ·  · [1]     остались [3 4 5 6], сумма 18 → взято 22 − 18 = 4
left = 3:  [1  2  3] ·  ·  ·  ·      остались [4 5 6 1], сумма 16 → взято 22 − 16 = 6

Сумма взятых карт равна сумме всех карт минус сумма оставшихся. Сумма всех карт для всех способов одна и та же. Значит, наибольшая сумма взятых карт получается там, где сумма оставшегося отрезка наименьшая. Задача сводится к уже решённой: найти окно длины n − k с наименьшей суммой — это best_window из главы 9.4 со знаком «меньше».

1. Длина окна. size = n − k — сколько карт останется.
2. Первое окно. total = sum(cards[:size]), оно же пока наименьшее.
3. Сдвиг. Для каждого r от size до n − 1: total += cards[r] − cards[r − size], запомнить наименьшую сумму. Сдвиг окна на одну позицию — это одна карта, которая переходит из правой взятой части в левую.
4. Ответ. sum(cards) − smallest.

Блок ниже — окно над картами примера, но ищется наименьшая сумма. Сдвиньте окно до конца.

§7Сложность

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

Срез первого окна создаёт временный список. Если на review спросят про память O(1), первое окно складывают циклом по индексам или выражением sum(cards[i] for i in range(size)) — оно не создаёт копию.

§8Код

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

def max_card_points(cards, k):
    size = len(cards) - k
    total = sum(cards[:size])
    smallest = total
    for r in range(size, len(cards)):
        total += cards[r] - cards[r - size]
        smallest = min(smallest, total)
    return sum(cards) - smallest

При k = n длина окна 0: первое окно пустое, его сумма 0. В цикле r − size = r, и на каждом шаге прибавляется и вычитается одна и та же карта — сумма остаётся 0. Ответ — сумма всех карт, что и требуется. Отдельный if для этого случая не нужен, тест test_take_all это проверяет.

§9Проверка

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

Остальные примеры проверяют быстрее. На [2, 2, 2] с k = 2 окно длины 1, все его суммы равны 2, ответ 6 − 2 = 4. На [9, 7, 7, 9, 7, 7, 9] с k = 7 окно пустое, ответ 55. На [1, 1000, 1] с k = 1 окно длины 2 даёт суммы 1001 и 1001, ответ 1002 − 1001 = 1. Все ответы совпадают с таблицей в §4.

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

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