10.11 Мок-интервью по задачам модуля · Алгоритмы на массивах

№	Задача	Источник	Глава
1	Самый длинный отрезок в пределах лимита	расходы и бюджет	10.3
2	Минимальный отрезок с суммой не меньше S	LeetCode 209	10.4
3	Подстрока без повторов	LeetCode 3	10.5
4	Две корзины	LeetCode 904	10.8
5	Каждое значение не больше k раз	LeetCode 2958	—
6	Наибольшая сумма отрезка без повторов	LeetCode 1695	—
7	Свести x к нулю	LeetCode 1658	—
8	Самый короткий отрезок со всеми видами	задача тренажёра	—

Задача 1 · Самый длинный отрезок в пределах лимитарасходы и бюджет · глава 10.3

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

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

Пересказ кандидата

«Нужна длина самого длинного отрезка подряд, сумма которого не больше limit».

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Самый длинный отрезок в пределах лимита

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

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

уточнено

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

nums, limit	Ответ	Что проверяет
`[4, 2, 5, 1, 1, 2, 1, 9], 7`	`4`	обычный случай: [1, 1, 2, 1]
`[3, 4], 7`	`2`	сумма точно на лимите
`[8, 1, 1], 2`	`2`	первый элемент больше лимита
`[5, 9, 8], 4`	`0`	каждый элемент больше лимита
`[0, 0, 0], 0`	`3`	нули и лимит 0

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

Перебор, который называет кандидат

Для каждого начала накапливать сумму вправо и записывать длину, пока сумма не больше лимита: отрезков n·(n + 1)/2, время O(n²).

ТехникаКакая техника подходит?

Верно. Участок подряд, длина не задана, на сумму стоит ограничение, нужен самый длинный. Для самого длинного отрезка окно сжимают, пока оно недопустимо, а длину записывают после цикла while: там окно допустимо.
Для самого короткого отрезка окно сжимают, пока оно подходит, и записывают длину перед каждым сжатием: после цикла окно уже не подходит.
Окно фиксированной длины нужно, когда длина участка задана числом. Здесь длину определяет условие на содержимое.
Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.

Правило шага

Расширение. total += nums[r].
Сжатие. Пока total > limit: total -= nums[l], l += 1.
Запись. После цикла: best = max(best, r − l + 1).

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

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

Каждая граница проходит список один раз, сдвигов не больше 2·n. Кроме total, best и l, памяти не нужно.
Каждая граница проходит список один раз, сдвигов не больше 2·n. Кроме total, best и l, памяти не нужно.
Каждая граница проходит список один раз, сдвигов не больше 2·n. Кроме total, best и l, памяти не нужно.
Верно. Каждая граница проходит список один раз, сдвигов не больше 2·n. Кроме total, best и l, памяти не нужно.

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

Код эталонного решения

longest_withinглава 10.3

def longest_within(nums, limit):
    if limit < 0:
        raise ValueError("limit должно быть не меньше 0")
    best = 0
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total > limit:
            total -= nums[l]
            l += 1
        best = max(best, r - l + 1)
    return best

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераИнтервьюер добавляет: «Расходы могут быть отрицательными — это возвраты». Что станет с решением?

Верно. С отрицательными числами по сумме нельзя решить, какую границу сдвигать, глава 10.2, §4. Нужны другие техники, например префиксные суммы, занятие 11.
Окно переменного размера проходит не все отрезки. Оно пропускает отрезки, про которые по знаку чисел известно, что они не подходят.
Замена цикла на if не связана со знаком чисел. Проблема в том, что сумма перестаёт меняться в одну сторону.

Задача 2 · Минимальный отрезок с суммой не меньше SLeetCode 209 · глава 10.4

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

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

Пересказ кандидата

«Нужна длина самого короткого отрезка подряд с суммой не меньше s».

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Минимальный отрезок с суммой не меньше S

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

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

уточнено

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

nums, s	Ответ	Что проверяет
`[2, 3, 1, 2, 4, 3], 7`	`2`	сумма лучшего отрезка точно 7
`[5, 8, 3, 12, 20, 6, 22, 9], 30`	`2`	заказы по часам
`[4, 40, 1], 30`	`1`	достаточно одного элемента
`[1, 1, 1, 1], 5`	`0`	отрезка нет
`[0, 0, 5, 0], 5`	`1`	нули в списке

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

Перебор, который называет кандидат

Для каждого начала удлинять отрезок, пока сумма не достигла s, и сравнивать длину: в худшем случае, когда отрезка нет, O(n²).

ТехникаКакая техника подходит?

Верно. Участок подряд, на сумму стоит нижняя граница, нужен самый короткий. Для самого короткого отрезка окно сжимают, пока оно подходит, и записывают длину перед каждым сжатием: после цикла окно уже не подходит.
Окно фиксированной длины нужно, когда длина участка задана числом. Здесь длину определяет условие на содержимое.
Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.
Для самого длинного отрезка окно сжимают, пока оно недопустимо, а длину записывают после цикла while: там окно допустимо.

Правило шага

Расширение. total += nums[r].
Запись и сжатие. Пока total >= s: сравнить r − l + 1 с лучшей, затем total -= nums[l], l += 1.
Ответ. Вернуть лучшую длину или 0.

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

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

Каждая граница проходит список один раз. Память — total, best и l.
Каждая граница проходит список один раз. Память — total, best и l.
Верно. Каждая граница проходит список один раз. Память — total, best и l.
Каждая граница проходит список один раз. Память — total, best и l.

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

Код эталонного решения

shortest_windowглава 10.4

def shortest_window(nums, s):
    if s < 1:
        raise ValueError("s должно быть не меньше 1")
    best = 0
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total >= s:
            length = r - l + 1
            if best == 0 or length < best:
                best = length
            total -= nums[l]
            l += 1
    return best

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераПочему длина записывается внутри цикла while?

l не выходит за конец списка: сумма пустого окна 0, порог не меньше 1, и цикл останавливается раньше.
Внутри цикла запись выполняется даже чаще. Место определяется тем, когда окно подходит.
Верно. Цикл работает, пока окно подходит. Запись после цикла сравнивала бы длину окна, которое не подходит, глава 10.4, §6.

Задача 3 · Подстрока без повторовLeetCode 3 · глава 10.5

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

«Дана строка. Найдите длину самой длинной подстроки, в которой нет повторяющихся символов.»

Пересказ кандидата

«Нужна длина самого длинного отрезка строки подряд, в котором все символы разные».

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Подстрока без повторов

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

«Дана строка. Найдите длину самой длинной подстроки, в которой нет повторяющихся символов.»

уточнено

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

text	Ответ	Что проверяет
`'abcabcbb'`	`3`	обычный случай: "abc"
`'bbbbb'`	`1`	все символы одинаковые
`'pwwkew'`	`3`	повтор рядом
`'abba'`	`2`	повтор символа, который вышел из окна
`''`	`0`	пустая строка

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

Перебор, который называет кандидат

Для каждого начала удлинять подстроку до первого повтора, символы хранить в множестве: O(n·m), m — число разных символов; на строке из разных символов это O(n²).

ТехникаКакая техника подходит?

Окно фиксированной длины нужно, когда длина участка задана числом. Здесь длину определяет условие на содержимое.
Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.
Верно. Участок подряд, ограничение на содержимое — без повторов, нужен самый длинный. Для самого длинного отрезка окно сжимают, пока оно недопустимо, а длину записывают после цикла while: там окно допустимо.
Для самого короткого отрезка окно сжимают, пока оно подходит, и записывают длину перед каждым сжатием: после цикла окно уже не подходит.

Правило шага

Расширение. count[ch] = count.get(ch, 0) + 1 для пришедшего символа.
Сжатие. Пока count[ch] > 1: count[text[l]] -= 1, l += 1.
Запись. После цикла: best = max(best, r − l + 1).

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

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

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

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

Код эталонного решения

longest_uniqueглава 10.5

def longest_unique(text):
    count = {}
    best = 0
    l = 0
    for r in range(len(text)):
        ch = text[r]
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:
            count[text[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераИнтервьюер спрашивает: «Почему в условии цикла проверяется только счётчик count[ch]?»

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

Задача 4 · Две корзиныLeetCode 904 · глава 10.8

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

«Деревья растут в ряд, fruits[i] — вид фрукта. У вас две корзины, в каждой фрукты одного вида. Вы начинаете с любого дерева, идёте вправо и с каждого срываете один фрукт, пока он подходит к корзинам. Верните наибольшее число фруктов.»

Пересказ кандидата

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

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Две корзины

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

«Деревья растут в ряд, fruits[i] — вид фрукта. У вас две корзины, в каждой фрукты одного вида. Вы начинаете с любого дерева, идёте вправо и с каждого срываете один фрукт, пока он подходит к корзинам. Верните наибольшее число фруктов.»

уточнено

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

fruits	Ответ	Что проверяет
`[1, 2, 3, 2, 2]`	`4`	третий вид внутри: [2, 3, 2, 2]
`[1, 2, 1]`	`3`	весь ряд
`[0, 1, 2, 2]`	`3`	начать со второго дерева
`[3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]`	`5`	лучший отрезок в середине
`[5, 5, 5]`	`3`	один вид

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

Перебор, который называет кандидат

Для каждого начала идти вправо, собирая виды в множество, до третьего вида: в худшем случае O(n²).

ТехникаКакая техника подходит?

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

Правило шага

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

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

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

Верно. Каждое дерево входит в окно и выходит один раз. В карте не больше трёх ключей.
Каждое дерево входит в окно и выходит один раз. В карте не больше трёх ключей.
Каждое дерево входит в окно и выходит один раз. В карте не больше трёх ключей.
Каждое дерево входит в окно и выходит один раз. В карте не больше трёх ключей.

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

Код эталонного решения

total_fruitглава 10.8

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

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераИнтервьюер меняет условие: корзин теперь k. Что изменится в коде?

Верно. Схема и удаление ключей те же, память станет O(k).
Частотная карта уже хранит счётчик каждого вида. Меняется только число в условии.
Ограничение «не больше k видов» так же нарушается расширением и восстанавливается сжатием.

Задача 5 · Каждое значение не больше k разLeetCode 2958 · только в тренажёре

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

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

Пересказ кандидата

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

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Каждое значение не больше k раз

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

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

уточнено

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

nums, k	Ответ	Что проверяет
`[1, 2, 3, 1, 2, 3, 1, 2], 2`	`6`	пример LeetCode 1
`[1, 2, 1, 2, 1, 2, 1, 2], 1`	`2`	пример LeetCode 2
`[5, 5, 5, 5, 5, 5, 5], 4`	`4`	одно значение
`[1, 2, 3], 1`	`3`	весь список хороший
`[7], 1`	`1`	один элемент

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

Перебор, который называет кандидат

Для каждого начала удлинять отрезок со счётчиками, пока частота пришедшего значения не превысила k: O(n²).

ТехникаКакая техника подходит?

Верно. Участок подряд, ограничение на частоту каждого значения, нужен самый длинный. Для самого длинного отрезка окно сжимают, пока оно недопустимо, а длину записывают после цикла while: там окно допустимо.
Для самого короткого отрезка окно сжимают, пока оно подходит, и записывают длину перед каждым сжатием: после цикла окно уже не подходит.
Окно фиксированной длины нужно, когда длина участка задана числом. Здесь длину определяет условие на содержимое.
Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.

Правило шага

Расширение. count[x] = count.get(x, 0) + 1.
Сжатие. Пока count[x] > k: count[nums[l]] -= 1, l += 1.
Запись. После цикла: best = max(best, r − l + 1).

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

Каждая граница проходит список один раз. В карте не больше ключей, чем разных значений m.
Каждая граница проходит список один раз. В карте не больше ключей, чем разных значений m.
Каждая граница проходит список один раз. В карте не больше ключей, чем разных значений m.
Верно. Каждая граница проходит список один раз. В карте не больше ключей, чем разных значений m.

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

Код эталонного решения

max_frequencyтолько в тренажёре

def max_frequency(nums, k):
    count = {}
    best = 0
    l = 0
    for r in range(len(nums)):
        x = nums[r]
        count[x] = count.get(x, 0) + 1
        while count[x] > k:
            count[nums[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераЧем эта задача отличается от подстроки без повторов из главы 10.5?

Условие читает счётчик одного значения, число ключей в нём не участвует. Удаление не нужно, как в главе 10.5.
Ищется самый длинный отрезок: длина записывается после цикла, когда окно допустимо.
Верно. Подстрока без повторов — это частный случай с k = 1. Код главы 10.5 работает, если в условии цикла поставить k.

Задача 6 · Наибольшая сумма отрезка без повторовLeetCode 1695 · только в тренажёре

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

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

Пересказ кандидата

«Среди отрезков подряд без повторов нужна наибольшая сумма».

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Наибольшая сумма отрезка без повторов

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

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

уточнено

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

nums	Ответ	Что проверяет
`[4, 2, 4, 5, 6]`	`17`	пример LeetCode 1: [2, 4, 5, 6]
`[5, 2, 1, 2, 5, 2, 1, 2, 5]`	`8`	пример LeetCode 2: [5, 2, 1]
`[7, 7, 7]`	`7`	все одинаковые
`[1, 2, 3]`	`6`	весь список без повторов
`[10, 1, 1, 2, 3]`	`11`	короткий [10, 1] дороже длинного [1, 2, 3]

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

Перебор, который называет кандидат

Для каждого начала удлинять отрезок до первого повтора, накапливая сумму: O(n²) в худшем случае.

ТехникаКакая техника подходит?

Для самого короткого отрезка окно сжимают, пока оно подходит, и записывают длину перед каждым сжатием: после цикла окно уже не подходит.
Окно фиксированной длины нужно, когда длина участка задана числом. Здесь длину определяет условие на содержимое.
Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.
Верно. Участок подряд без повторов; числа положительные, поэтому из допустимых окон с концом в r лучшее — самое длинное. Для самого длинного отрезка окно сжимают, пока оно недопустимо, а длину записывают после цикла while: там окно допустимо.

Правило шага

Сжатие до расширения. Пока nums[r] уже в множестве: убрать nums[l] из множества и из суммы, l += 1.
Расширение. Добавить nums[r] в множество и в сумму.
Запись. best = max(best, total).

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

Каждое число входит в окно и выходит один раз. Множество хранит до n чисел.
Каждое число входит в окно и выходит один раз. Множество хранит до n чисел.
Верно. Каждое число входит в окно и выходит один раз. Множество хранит до n чисел.
Каждое число входит в окно и выходит один раз. Множество хранит до n чисел.

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

Код эталонного решения

max_erasureтолько в тренажёре

def max_erasure(nums):
    seen = set()
    total = 0
    best = 0
    l = 0
    for r in range(len(nums)):
        while nums[r] in seen:
            seen.remove(nums[l])
            total -= nums[l]
            l += 1
        seen.add(nums[r])
        total += nums[r]
        best = max(best, total)
    return best

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераИнтервьюер спрашивает: «А если числа могут быть отрицательными?»

Множество хранит любые числа, знак ему не мешает.
Верно. С отрицательными числами короткий отрезок может дать большую сумму, чем длинный с тем же концом. Запись best = max(best, total) только для самого длинного окна станет неверной.
Повторы проверяются так же, но сумма окна перестаёт расти с длиной, и ответ больше не обязан приходиться на самое длинное окно.

Задача 7 · Свести x к нулюLeetCode 1658 · только в тренажёре

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

«Дан список положительных чисел и число x. За одну операцию можно убрать число с левого или правого края списка и вычесть его из x. Верните наименьшее число операций, после которых x станет ровно 0, или −1, если это невозможно.»

Пересказ кандидата

«Убранные числа — начало и конец списка с суммой x. Оставшиеся — отрезок подряд с суммой sum(nums) − x. Чем он длиннее, тем меньше операций».

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Свести x к нулю

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

«Дан список положительных чисел и число x. За одну операцию можно убрать число с левого или правого края списка и вычесть его из x. Верните наименьшее число операций, после которых x станет ровно 0, или −1, если это невозможно.»

уточнено

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

nums, x	Ответ	Что проверяет
`[1, 1, 4, 2, 3], 5`	`2`	пример LeetCode 1
`[5, 6, 7, 8, 9], 4`	`-1`	пример LeetCode 2: невозможно
`[3, 2, 20, 1, 1, 3], 10`	`5`	пример LeetCode 3: с обоих краёв
`[1, 1], 3`	`-1`	x больше суммы
`[2, 3], 5`	`2`	убрать всё

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

Перебор, который называет кандидат

Перебрать, сколько чисел убрать слева, от 0 до n, и для каждого варианта добирать числа справа, пока сумма меньше x: O(n²).

ТехникаКакая техника подходит?

Окно фиксированной длины нужно, когда длина участка задана числом. Здесь длину определяет условие на содержимое.
Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.
Верно. Окно в условии не названо: оставшиеся числа — отрезок подряд с суммой sum − x, нужен самый длинный. Для самого длинного отрезка окно сжимают, пока оно недопустимо, а длину записывают после цикла while: там окно допустимо.
Для самого короткого отрезка окно сжимают, пока оно подходит, и записывают длину перед каждым сжатием: после цикла окно уже не подходит.

Правило шага

Цель. target = sum(nums) − x; если меньше 0 — вернуть −1.
Расширение и сжатие. total += nums[r]; пока total > target — сжимать.
Запись. Если total == target — best = max(best, r − l + 1).
Ответ. −1, если best не менялся, иначе len(nums) − best.

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

Сумма списка — один проход, окно — ещё один. Память — несколько переменных.
Верно. Сумма списка — один проход, окно — ещё один. Память — несколько переменных.
Сумма списка — один проход, окно — ещё один. Память — несколько переменных.
Сумма списка — один проход, окно — ещё один. Память — несколько переменных.

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

Код эталонного решения

min_operationsтолько в тренажёре

def min_operations(nums, x):
    target = sum(nums) - x
    if target < 0:
        return -1
    best = -1
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total > target:
            total -= nums[l]
            l += 1
        if total == target:
            best = max(best, r - l + 1)
    return -1 if best == -1 else len(nums) - best

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераПочему при target = 0 код возвращает len(nums), хотя ни одно окно с суммой 0 не содержит элементов?

Верно. После сжатия пустое окно с суммой 0 проходит проверку total == target, best становится 0, и ответ — len(nums) − 0.
Первая строка проверяет только target < 0. Случай target = 0 обрабатывается общим кодом.
Тест test_take_all проходит: пустое окно даёт best = 0.

Задача 8 · Самый короткий отрезок со всеми видамизадача тренажёра · только в тренажёре

Интервьюер формулирует задачу. Перескажите её своими словами: что на входе, что вернуть, что нельзя делать. Пересказ — проверка, что условие понято одинаково.

«В списке записаны виды товаров на полке по порядку. Найдите самый короткий участок полки подряд, на котором есть товары всех видов, что встречаются в списке, и верните его длину.»

Пересказ кандидата

«Нужна длина самого короткого отрезка, в котором встречаются все разные значения списка».

До кода выясняют то, чего в условии нет. Задайте вопросы по одному: справа появится ответ интервьюера и то, что он меняет в решении, слева — уточнённое условие.

Самый короткий отрезок со всеми видами

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

«В списке записаны виды товаров на полке по порядку. Найдите самый короткий участок полки подряд, на котором есть товары всех видов, что встречаются в списке, и верните его длину.»

уточнено

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

nums	Ответ	Что проверяет
`[5, 5, 1, 5, 5, 2, 1]`	`3`	обычный случай: [5, 2, 1]
`[1, 2, 3]`	`3`	все разные — весь список
`[4, 4, 4]`	`1`	один вид
`[1, 2, 1, 1, 3, 2]`	`3`	третий вид приходит последним: [1, 3, 2]
`[]`	`0`	пустой список

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

Перебор, который называет кандидат

Для каждого начала удлинять отрезок, пока в нём не соберутся все виды: O(n²).

ТехникаКакая техника подходит?

Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.
Для самого длинного отрезка окно сжимают, пока оно недопустимо, а длину записывают после цикла while: там окно допустимо.
Верно. Участок подряд, условие «есть все виды», нужен самый короткий: окно сжимают, пока оно подходит. Для самого короткого отрезка окно сжимают, пока оно подходит, и записывают длину перед каждым сжатием: после цикла окно уже не подходит.
Окно фиксированной длины нужно, когда длина участка задана числом. Здесь длину определяет условие на содержимое.

Правило шага

Расширение. count[x] = count.get(x, 0) + 1.
Запись и сжатие. Пока len(count) == need: записать длину, уменьшить счётчик левого вида, при нуле удалить ключ, l += 1.
Ответ. Лучшая длина или 0.

Сложность называют до кода: интервьюер соглашается с решением раньше, чем на запись потрачено время.

СложностьСколько стоит быстрое решение?

Верно. Каждая граница проходит список один раз; в карте не больше m ключей — разных видов.
Каждая граница проходит список один раз; в карте не больше m ключей — разных видов.
Каждая граница проходит список один раз; в карте не больше m ключей — разных видов.
Каждая граница проходит список один раз; в карте не больше m ключей — разных видов.

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

Код эталонного решения

shortest_all_kindsтолько в тренажёре

def shortest_all_kinds(nums):
    need = len(set(nums))
    count = {}
    best = 0
    l = 0
    for r in range(len(nums)):
        x = nums[r]
        count[x] = count.get(x, 0) + 1
        while len(count) == need:
            length = r - l + 1
            if best == 0 or length < best:
                best = length
            count[nums[l]] -= 1
            if count[nums[l]] == 0:
                del count[nums[l]]
            l += 1
    return best

Код проходят по шагам на первом примере. На секции это делают руками; ниже тот же проход — пошаговым прогоном эталонного решения. Затем интервьюер задаёт вопрос по решению.

Вопрос интервьюераЧто будет, если не удалять ключ со счётчиком 0?

Влияет: условие цикла считает ключи, и ключ со счётчиком 0 засчитывается как вид в окне.
Окно будет сжиматься дальше нужного, записанные длины окажутся меньше верных, а затем индекс l выйдет за окно.
Верно. Ключ ушедшего вида останется в карте, условие len(count) == need будет истинно и для окна без этого вида. Такую ошибку разбирает глава 10.8, §9.

Мок-интервью
по задачам модуля

§1Как устроен тренажёр

§2Задачи тренажёра

§3Тренажёр

§4Как оценить свою попытку