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

Категория

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

Уровень

Средний

Опирается на

Главы 8.2–8.10

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

Уложить решение в 25 минут секции и ничего не пропустить

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

В календарно-тематическом плане курса ход решения записан как шаблон interview canvas: условие → уточнения → примеры → brute force → оптимизация → сложность → код → проверка. Сложность называют до кода: так интервьюер соглашается с выбранным решением раньше, чем кандидат потратит время на его запись. Журнал Яндекс Образования советует иметь решение первой задачи примерно через полчаса, поэтому ориентир в таблице — 25 минут.

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

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

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

§3Уточнения

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

Решение меняет первый ответ: цены не отсортированы. В задаче 1 порядок был дан, здесь его придётся создать самим.

§4Примеры

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

§5Перебор

Перебор здесь достаточно назвать, писать его не обязательно: «Проверю все пары, из подходящих запомню наибольшую сумму. Это O(n²): при 10⁵ подарков около 5·10⁹ пар, это слишком долго». Интервьюер видит, что верное решение есть, и дальше разговор идёт о том, как его ускорить.

def best_pair_sum_brute(prices, budget):
    best = -1
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            s = prices[i] + prices[j]
            if s <= budget:
                best = max(best, s)
    return best

§6Оптимизация

Задача похожа на задачу 1: пара, сумма, сравнение с числом. Разница в том, что ищется не точная сумма, а наибольшая допустимая, и вход не отсортирован. Сначала сортируем копию, потом ставим указатели на самую дешёвую и самую дорогую цену. Правило сдвига меняется так:

1. Сумма не больше бюджета. Это кандидат в ответ — запоминаем, если он больше прежнего. Для левой цены лучшей пары уже не будет: правая цена самая дорогая из оставшихся, с любой другой сумма меньше. Левую цену исключаем: i += 1.
2. Сумма больше бюджета. Правая цена не укладывается даже с самой дешёвой из оставшихся, значит, с остальными тоже. Её исключаем: j -= 1.
3. Указатели встретились. Все цены исключены, в запомненном значении — лучшая сумма или −1.

Обоснование то же, что в главе 8.5: каждый ход исключает цену, у которой гарантированно нет лучшей пары среди оставшихся. Инвариант: «лучшая пара всего списка либо уже учтена в best, либо лежит на участке с i по j».

§7Сложность и сортировка

Сложность называют до кода. Здесь она складывается из двух частей, и её стоит разложить явно — об этом на review спрашивают отдельно.

Проход указателями быстрее сортировки, поэтому итоговую сложность задаёт сортировка: O(n log n) + O(n) = O(n log n). Это всё равно намного быстрее перебора: при n = 10⁵ перебор делает около 5·10⁹ проверок, а n·log₂n — около 1,7·10⁶. Если бы интервьюер разрешил менять вход, вместо копии подошёл бы prices.sort(): список сортируется на месте, копия не создаётся.

Следующий этап — код. На секции его пишет кандидат, поэтому до готового кода в §8 напишите функцию сами в окне ниже. «Запустить тесты» проверяет её на пяти входах из §4; часть из них заготовка проходит сразу.

§8Код

Код записывает правило из §6 и почти повторяет задачу 1. Отличий три: сортировка в начале, переменная best и нестрогое сравнение с бюджетом.

def best_pair_sum(prices, budget):
    prices = sorted(prices)
    i, j = 0, len(prices) - 1
    best = -1
    while i < j:
        s = prices[i] + prices[j]
        if s <= budget:
            best = max(best, s)
            i += 1
        else:
            j -= 1
    return best

>>> max(-1, 1150)
1150

>>> a = [3, 1, 2]
>>> b = sorted(a)
>>> a, b
([3, 1, 2], [1, 2, 3])
>>> a.sort()
>>> a
[1, 2, 3]
>>> print(a.sort())
None

Строка prices = sorted(prices) создаёт новый отсортированный список и связывает с ним имя prices внутри функции. Список вызывающего кода не меняется, как и требовал интервьюер.

§9Проверка

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

Остальные примеры проверяют быстрее, без записи каждого шага. На [500, 500] сумма 1000 проходит по <=, ответ 1000. На [500] и [] цикл не выполняется, и функция возвращает −1. На [900, 800] единственная сумма 1700 больше бюджета, j сдвигается, указатели встречаются, ответ −1. Все пять ответов совпадают с таблицей в §4.

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

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