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

№	Задача	Источник	Глава
1	Сумма каждого окна	скользящая сумма	9.3
2	Лучший отрезок длины k	задача 1 КТП	9.4
3	События во временном окне	задача 2 КТП	9.5
4	Гласные в окне	LeetCode 1456	9.4, §8
5	Наибольшее среднее	LeetCode 643	9.4, §7
6	Среднее вокруг элемента	LeetCode 2090	9.2, 9.3
7	Карты с краёв ряда	LeetCode 1423	9.8
8	Разница оценок	LeetCode 1984	—

Задача 1 · Сумма каждого окнаскользящая сумма · глава 9.3

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

«Дан список посещений сайта по часам и число k. Верните сумму посещений для каждых k часов подряд.»

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

«Нужен новый список: на месте s — сумма nums[s:s + k], всего n − k + 1 сумм».

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

Сумма каждого окна

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

«Дан список посещений сайта по часам и число k. Верните сумму посещений для каждых k часов подряд.»

уточнено

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

nums, k	Ответ	Что проверяет
`[12, 15, 9, 20, 18, 7, 25], 3`	`[36, 44, 47, 45, 50]`	обычный случай
`[3, -2, 7], 1`	`[3, -2, 7]`	k = 1: суммы — сами элементы
`[4, 1, 2], 3`	`[7]`	k = n: одно окно
`[-5, -2, -8, -1], 2`	`[-7, -10, -9]`	отрицательные числа
`[5, 1, 4, 2], 2`	`[6, 5, 6]`	короткий список

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

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

Для каждого начала окна взять срез nums[s:s + k] и сложить: n − k + 1 окон по k элементов, время O(n·k). При k около n/2 это порядка n²/4 операций.

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

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

Правило шага

Первое окно. total = sum(nums[:k]), записать в ответ.
Сдвиг. Для каждого r от k до n − 1: total += nums[r] − nums[r − k].
Запись. После каждого сдвига дописать total в ответ.

Пройдите сдвиг окна руками: неверный щелчок не выполняется, вместо него появляется объяснение.

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

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

Первое окно стоит k операций, каждый из n − k сдвигов — две. Память — только переменная total, кроме самого ответа.
Первое окно стоит k операций, каждый из n − k сдвигов — две. Память — только переменная total, кроме самого ответа.
Первое окно стоит k операций, каждый из n − k сдвигов — две. Память — только переменная total, кроме самого ответа.
Верно. Первое окно стоит k операций, каждый из n − k сдвигов — две. Память — только переменная total, кроме самого ответа.

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

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

window_sumsглава 9.3

def window_sums(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    total = sum(nums[:k])
    sums = [total]
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]
        sums.append(total)
    return sums

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

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

Верно. Сдвиг остаётся тем же, меняется только запись: sums.append(total / k). Время по-прежнему O(n).
Пересчитывать среднее не нужно: сдвигом пересчитывается сумма, а среднее получается из неё делением.
Для суммы и среднего хватает одной переменной total. Хранить элементы окна нужно для максимума, это занятие 25.

Задача 2 · Лучший отрезок длины kзадача 1 КТП · глава 9.4

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

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

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

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

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

Лучший отрезок длины k

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

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

уточнено

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

nums, k	Ответ	Что проверяет
`[12, 15, 9, 20, 18, 7, 25], 3`	`(4, 50)`	лучшее окно — последнее
`[5, 1, 5, 1], 2`	`(0, 6)`	равные суммы — самое левое
`[-5, -2, -8, -1], 2`	`(0, -7)`	все суммы отрицательные
`[3, -2, 7], 1`	`(2, 7)`	k = 1
`[4, 1, 2], 3`	`(0, 7)`	k = n

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

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

Посчитать сумму каждого среза и выбрать наибольшую: O(n·k). Или через window_sums: O(n), но список всех сумм занимает O(n) памяти.

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

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

Правило шага

Первое окно. total = sum(nums[:k]), оно же лучшее: best, start = total, 0.
Сдвиг. total += nums[r] − nums[r − k] для каждого r от k.
Сравнение. Если total > best, запомнить best = total, start = r − k + 1.
Ответ. Вернуть (start, best).

Посмотрите правило на блоке ниже: сдвигайте окно и следите за состоянием.

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

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

Один проход со сдвигом окна; кроме total, best и start, памяти не нужно.
Один проход со сдвигом окна; кроме total, best и start, памяти не нужно.
Верно. Один проход со сдвигом окна; кроме total, best и start, памяти не нужно.
Один проход со сдвигом окна; кроме total, best и start, памяти не нужно.

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

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

best_windowглава 9.4

def best_window(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    total = sum(nums[:k])
    best, start = total, 0
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]
        if total > best:
            best, start = total, r - k + 1
    return (start, best)

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

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

Так тоже можно, но это больше переделок. Достаточно поменять знак сравнения.
При строгом знаке > равная сумма лучшее окно не заменяет — возвращается самое левое.
Верно. При нестрогом сравнении каждое следующее окно с той же суммой заменяет лучшее, и в конце остаётся самое правое.

Задача 3 · События во временном окнезадача 2 КТП · глава 9.5

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

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

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

«Моменты отсортированы. Нужно найти промежуток [s, s + w), в который попадает больше всего событий, и вернуть их число».

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

События во временном окне

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

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

уточнено

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

times, w	Ответ	Что проверяет
`[1, 3, 4, 10, 12, 13, 14, 30], 5`	`4`	обычный случай: окно [10, 15)
`[0, 5], 5`	`1`	событие на правой границе
`[7, 7, 7], 1`	`3`	одинаковые моменты
`[], 3`	`0`	пустой список
`[42], 10`	`1`	одно событие

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

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

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

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

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

Правило шага

Новое событие. Для каждого r событие times[r] входит в окно справа.
Сжатие. Пока times[r] − times[l] >= w, сдвигать l: старое событие не помещается в окно.
Подсчёт. В окне r − l + 1 событий, обновить best.

Посмотрите правило на блоке ниже: сдвигайте окно и следите за состоянием.

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

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

l только растёт и не превышает r: за всю работу сдвигов l не больше n, сдвигов r — n.
Верно. l только растёт и не превышает r: за всю работу сдвигов l не больше n, сдвигов r — n.
l только растёт и не превышает r: за всю работу сдвигов l не больше n, сдвигов r — n.
l только растёт и не превышает r: за всю работу сдвигов l не больше n, сдвигов r — n.

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

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

max_eventsглава 9.5

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

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

Вопрос интервьюераИнтервьюер уточняет: правая граница окна входит, окно [s, s + w]. Что изменится?

На примере ответ совпадает, но на [0, 5] с w = 5 закрытое окно даёт 2, а открытое — 1.
Верно. Событие ровно на расстоянии w теперь помещается в окно, и левую границу двигают только при разности больше w.
Подсчёт событий между l и r включительно не зависит от вида границы окна.

Задача 4 · Гласные в окнеLeetCode 1456 · глава 9.4, §8

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

«Дана строка и число k. Верните наибольшее число гласных в подстроке длины k.»

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

«Нужно пройти все подстроки длины k и найти ту, где больше всего букв a, e, i, o, u. Вернуть число».

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

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

s, k	Ответ	Что проверяет
`'abciiidef', 3`	`3`	пример LeetCode: окно iii
`'aeiou', 2`	`2`	одни гласные
`'leetcode', 3`	`2`	пример LeetCode
`'rhythms', 4`	`0`	гласных нет
`'bcdfaa', 2`	`2`	лучшее окно — последнее

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

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

Для каждой подстроки длины k посчитать гласные заново: O(n·k).

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

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

Правило шага

Первое окно. Посчитать гласные в s[:k].
Сдвиг. count += (s[r] in vowels) − (s[r − k] in vowels).
Ответ. best = max(best, count), вернуть best.

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

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

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

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

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

max_vowelsглава 9.4, §8

def max_vowels(s, k):
    vowels = set("aeiou")
    count = sum(1 for ch in s[:k] if ch in vowels)
    best = count
    for r in range(k, len(s)):
        count += (s[r] in vowels) - (s[r - k] in vowels)
        best = max(best, count)
    return best

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

Вопрос интервьюераИнтервьюер просит вернуть саму подстроку с наибольшим числом гласных. Что добавить?

Верно. Как в best_window: при строго большем счётчике запомнить start = r − k + 1, подстроку вырезать один раз в конце.
Это O(n·k) памяти и времени на срезы. Достаточно начала лучшего окна.
Сдвиг остаётся тем же, добавляется только запоминание индекса.

Задача 5 · Наибольшее среднееLeetCode 643 · глава 9.4, §7

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

«Дан список чисел и число k. Найдите непрерывный отрезок длины k с наибольшим средним и верните это среднее.»

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

«Среднее — сумма, делённая на k, а k одно для всех окон. Значит, нужно окно с наибольшей суммой, и в конце разделить её на k».

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

Наибольшее среднее

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

«Дан список чисел и число k. Найдите непрерывный отрезок длины k с наибольшим средним и верните это среднее.»

уточнено

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

nums, k	Ответ	Что проверяет
`[1, 12, -5, -6, 50, 3], 4`	`12.75`	пример LeetCode
`[5], 1`	`5.0`	один элемент
`[-3, -2, -1], 2`	`-1.5`	все отрицательные
`[4, 1, 2], 3`	`2.3333333333333335`	k = n
`[0, 0, 0, 9], 2`	`4.5`	лучшее окно — последнее

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

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

Посчитать среднее каждого среза длины k: O(n·k).

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

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

Правило шага

Первое окно. total = sum(nums[:k]), best = total.
Сдвиг. total += nums[r] − nums[r − k], best = max(best, total).
Ответ. best / k — одно деление в конце.

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

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

Сдвиг окна за O(1), один проход. Делится только итоговая сумма.
Сдвиг окна за O(1), один проход. Делится только итоговая сумма.
Сдвиг окна за O(1), один проход. Делится только итоговая сумма.
Верно. Сдвиг окна за O(1), один проход. Делится только итоговая сумма.

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

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

find_max_averageглава 9.4, §7

def find_max_average(nums, k):
    total = sum(nums[:k])
    best = total
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]
        best = max(best, total)
    return best / k

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

Вопрос интервьюераПочему не нужно делить на k сумму каждого окна?

Делить можно: / в Python даёт float. Деление в каждом окне не нужно.
Точность здесь ни при чём: дело в том, что порядок окон по среднему и по сумме один и тот же.
Верно. Если одна сумма больше другой, то и после деления обеих на k она больше. Поэтому сравнивают суммы, а делят один раз.

Задача 6 · Среднее вокруг элементаLeetCode 2090 · глава 9.2, 9.3

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

«Для каждого индекса i найдите среднее элементов с i − k по i + k, целочисленным делением. Если слева или справа меньше k элементов, запишите −1.»

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

«Окно — 2k + 1 элементов с центром в i. Для центров, у которых полного окна нет, ответ −1. Ответ — список длины n».

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

Среднее вокруг элемента

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

«Для каждого индекса i найдите среднее элементов с i − k по i + k, целочисленным делением. Если слева или справа меньше k элементов, запишите −1.»

уточнено

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

nums, k	Ответ	Что проверяет
`[7, 4, 3, 9, 1, 8, 5, 2, 6], 3`	`[-1, -1, -1, 5, 4, 4, -1, -1, -1]`	пример LeetCode
`[100000], 0`	`[100000]`	k = 0
`[8], 100000`	`[-1]`	k больше длины
`[1, 2, 3], 1`	`[-1, 2, -1]`	одно полное окно
`[5, 5], 0`	`[5, 5]`	k = 0, два элемента

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

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

Для каждого центра сложить 2k + 1 элементов заново: O(n·k).

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

Окно по времени нужно, когда длина окна задана в секундах, а число элементов в нём меняется: левую границу двигают циклом while.
Указатели навстречу стартуют с двух концов отсортированных данных и ищут пару элементов. Участок подряд они не проходят.
Сортировка нужна, когда элементы выбираются в любом порядке, не подряд: после неё близкие значения стоят рядом.
Верно. Окно — участок подряд длины 2k + 1. Окно фиксированной длины проходит все участки из k элементов подряд и исправляет состояние по ушедшему и пришедшему элементу.

Правило шага

Ответ из −1. avgs = [-1] * n, длина окна size = 2k + 1; если size > n, вернуть сразу.
Первое окно. Сумма nums[:size], центр — индекс k.
Сдвиг. Для r от size: total += nums[r] − nums[r − size], записать avgs[r − k].

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

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

Каждый сдвиг — две операции и одна запись, проход один.
Каждый сдвиг — две операции и одна запись, проход один.
Верно. Каждый сдвиг — две операции и одна запись, проход один.
Каждый сдвиг — две операции и одна запись, проход один.

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

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

k_radius_averagesглава 9.2, 9.3

def k_radius_averages(nums, k):
    n = len(nums)
    avgs = [-1] * n
    size = 2 * k + 1
    if size > n:
        return avgs
    total = sum(nums[:size])
    avgs[k] = total // size
    for r in range(size, n):
        total += nums[r] - nums[r - size]
        avgs[r - k] = total // size
    return avgs

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

Вопрос интервьюераСколько элементов получат −1 при n = 9 и k = 3?

Длина окна 7, но −1 зависит от числа центров без полного окна: их 9 − 3 = 6.
Окна нет и у последних трёх: справа от них меньше трёх элементов.
Верно. Центры полных окон — индексы с k по n − 1 − k, это 3, 4, 5. Остальные 6 элементов получают −1.

Задача 7 · Карты с краёв рядаLeetCode 1423 · глава 9.8

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

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

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

«Взятые карты — начало ряда длины left и конец длины k − left. Нужна наибольшая сумма таких карт».

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

Карты с краёв ряда

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

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

уточнено

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

cards, k	Ответ	Что проверяет
`[1, 2, 3, 4, 5, 6, 1], 3`	`12`	пример LeetCode
`[2, 2, 2], 2`	`4`	все способы равны
`[9, 7, 7, 9, 7, 7, 9], 7`	`55`	k = n
`[100, 40, 17, 9, 73, 75], 3`	`248`	одна слева, две справа
`[1, 1000, 1], 1`	`1`	середина недоступна

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

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

Перебрать left от 0 до k и сложить срезы: k + 1 способов по k карт, O(k²).

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

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

Правило шага

Сведение. Взятые = все − оставшиеся. Оставшиеся — окно длины size = n − k.
Окно. Найти окно длины size с наименьшей суммой сдвигом.
Ответ. sum(cards) − smallest.

Посмотрите правило на блоке ниже: сдвигайте окно и следите за состоянием.

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

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

k сдвигов окна по O(1), плюс сумма всех карт и первое окно — O(n).
Верно. k сдвигов окна по O(1), плюс сумма всех карт и первое окно — O(n).
k сдвигов окна по O(1), плюс сумма всех карт и первое окно — O(n).
k сдвигов окна по O(1), плюс сумма всех карт и первое окно — O(n).

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

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

max_card_pointsглава 9.8

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

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

Вопрос интервьюераИнтервьюер меняет условие: очки бывают отрицательными. Что изменится в решении через окно?

Верно. Равенство не зависит от знака чисел, окно с наименьшей суммой по-прежнему даёт ответ. Сломается только перебор с best = 0.
Сумма всех карт постоянна, поэтому наибольшие взятые — это наименьшие оставшиеся при любых знаках.
Оставшиеся карты по-прежнему отрезок подряд длины n − k, окно работает.

Задача 8 · Разница оценокLeetCode 1984 · только в тренажёре

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

«Даны оценки студентов и число k. Выберите любых k студентов так, чтобы разница между наибольшей и наименьшей оценкой среди них была наименьшей. Верните эту разницу.»

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

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

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

Разница оценок

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

«Даны оценки студентов и число k. Выберите любых k студентов так, чтобы разница между наибольшей и наименьшей оценкой среди них была наименьшей. Верните эту разницу.»

уточнено

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

scores, k	Ответ	Что проверяет
`[9, 4, 1, 7], 2`	`2`	пример LeetCode
`[90], 1`	`0`	один студент
`[1, 5, 3, 9], 3`	`4`	группа из трёх
`[7, 7, 7], 2`	`0`	равные оценки
`[10, 1, 100, 50], 1`	`0`	k = 1

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

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

Перебрать все группы из k студентов и для каждой найти разницу: число групп — сочетания из n по k, при n = 1000 и k = 500 это астрономическое число.

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

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

Правило шага

Сортировка. scores = sorted(scores).
Окно. В отсортированном окне длины k разница — последний минус первый: scores[i + k − 1] − scores[i].
Ответ. Наименьшая разница по всем окнам.

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

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

Верно. Сортировка копии — O(n log n) и O(n) памяти, проход окнами — O(n). Итог задаёт сортировка.
Сортировка копии — O(n log n) и O(n) памяти, проход окнами — O(n). Итог задаёт сортировка.
Сортировка копии — O(n log n) и O(n) памяти, проход окнами — O(n). Итог задаёт сортировка.
Сортировка копии — O(n log n) и O(n) памяти, проход окнами — O(n). Итог задаёт сортировка.

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

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

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

def min_difference(scores, k):
    scores = sorted(scores)
    best = scores[k - 1] - scores[0]
    for i in range(1, len(scores) - k + 1):
        best = min(best, scores[i + k - 1] - scores[i])
    return best

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

Вопрос интервьюераПочему после сортировки достаточно смотреть только группы, стоящие подряд?

sorted ничего не удаляет: повторы остаются рядом друг с другом.
Условие разрешает любых студентов. Подряд достаточно смотреть по свойству отсортированного списка.
Верно. Наименьший и наибольший элементы группы стоят в отсортированном списке на местах a и b, и все элементы между ними укладываются в тот же разброс. Отрезок длины k внутри [a, b] даёт разницу не больше.

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

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

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

§3Тренажёр

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