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

№	Задача	Источник	Глава
1	Пара с заданной суммой	LeetCode 167	8.4–8.6
2	Удаление повторов	LeetCode 26	8.7
3	Сжатие последовательности	LeetCode 443	8.7
4	Нули в конец	LeetCode 283	8.8
5	Разделение по порогу	шаг быстрой сортировки	8.8
6	Три цвета	LeetCode 75	8.8
7	Подпоследовательность	LeetCode 392	8.7
8	Подарки в пределах бюджета	похожа на LeetCode 1099	8.11

Задача 1 · Пара с заданной суммойLeetCode 167 · глава 8.4–8.6

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

«Цены товаров в каталоге отсортированы. Есть подарочный сертификат на сумму target. Найдите два товара, которые вместе стоят ровно эту сумму.»

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

«На входе отсортированный список и число. Нужно вернуть индексы двух разных элементов, сумма которых равна target, или None, если таких нет».

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

Пара с заданной суммой

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

«Цены товаров в каталоге отсортированы. Есть подарочный сертификат на сумму target. Найдите два товара, которые вместе стоят ровно эту сумму.»

уточнено

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

prices, target	Ответ	Что проверяет
`[300, 450, 700, 900, 1200, 1500], 1600`	`(2, 3)`	обычный случай
`[100, 250, 600], 500`	`None`	250 + 250 — один товар дважды
`[250, 250], 500`	`(0, 1)`	одинаковые цены у разных товаров
`[], 500`	`None`	пустой каталог
`[-7, -3, 0, 2, 9], -1`	`(1, 3)`	отрицательные числа

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

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

Перебор всех пар двумя вложенными циклами: n·(n − 1) / 2 проверок, время O(n²). При миллионе товаров это около 5·10¹¹ проверок, поэтому перебор называют и сразу переходят к быстрому решению.

Форма техникиКакая форма двух указателей подходит?

Верно. Цены отсортированы, ответ — пара элементов. Указатели навстречу стартуют с двух концов и сходятся. Они нужны, когда решение зависит от пары элементов с разных концов упорядоченных данных.
Чтение и запись нужны, когда список меняется на месте: r читает каждый элемент, w показывает, куда писать следующий оставленный.
По указателю на каждую последовательность идут, когда данных две: слово и текст, два отсортированных списка.

Правило шага

Старт. i — на самой дешёвой цене, j — на самой дорогой.
Сумма равна цели. Пара найдена, вернуть (i, j).
Сумма меньше цели. Цена prices[i] даже с самой дорогой из оставшихся даёт мало. Исключить её: i += 1.
Сумма больше цели. Цена prices[j] даже с самой дешёвой из оставшихся даёт много. Исключить её: j -= 1.
Указатели встретились. Пар не осталось, вернуть None.

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

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

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

Каждый шаг сдвигает один указатель, назад они не возвращаются: шагов не больше n − 1. Кроме трёх переменных i, j, s, памяти не нужно.
Каждый шаг сдвигает один указатель, назад они не возвращаются: шагов не больше n − 1. Кроме трёх переменных i, j, s, памяти не нужно.
Каждый шаг сдвигает один указатель, назад они не возвращаются: шагов не больше n − 1. Кроме трёх переменных i, j, s, памяти не нужно.
Верно. Каждый шаг сдвигает один указатель, назад они не возвращаются: шагов не больше n − 1. Кроме трёх переменных i, j, s, памяти не нужно.

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

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

pair_sumглава 8.4–8.6

def pair_sum(prices, target):
    i, j = 0, len(prices) - 1
    while i < j:
        s = prices[i] + prices[j]
        if s == target:
            return (i, j)
        if s < target:
            i += 1
        else:
            j -= 1
    return None

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

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

Верно. Указателям нужен порядок, а сортировка меняет индексы. Словарь находит парную цену target − p за один проход и хранит исходные индексы.
Указатели найдут пару, но в отсортированной копии индексы другие, а вернуть нужно исходные.
Без порядка сумма крайних цен не показывает, какую цену можно исключить. В главе 8.5 на таком входе пара потерялась.

Задача 2 · Удаление повторовLeetCode 26 · глава 8.7

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

«Дан отсортированный список идентификаторов заказов, при выгрузке некоторые продублировались. Уберите повторы и верните, сколько значений осталось.»

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

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

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

Удаление повторов

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

«Дан отсортированный список идентификаторов заказов, при выгрузке некоторые продублировались. Уберите повторы и верните, сколько значений осталось.»

уточнено

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

вход	ответ и список после вызова	Что проверяет
`[101, 101, 102, 105, 105, 105, 110]`	`4 · [101, 102, 105, 110]`	обычный случай
`[]`	`0 · []`	пустой список
`[5, 5, 5, 5]`	`1 · [5]`	все значения одинаковые
`[1, 2, 3, 4]`	`4 · [1, 2, 3, 4]`	повторов нет
`[1, 2, 3, 3, 3]`	`3 · [1, 2, 3]`	повторы в конце

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

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

Собрать новый список и добавлять значение, если его там ещё нет. Проверка in по списку стоит O(n), всего O(n²). Кроме того, нужна O(n) память, а условие запрещает новый список.

Форма техникиКакая форма двух указателей подходит?

Верно. Список меняется на месте, нужно решить для каждого элемента: оставить или пропустить. Чтение и запись нужны, когда список меняется на месте: r читает каждый элемент, w показывает, куда писать следующий оставленный.
По указателю на каждую последовательность идут, когда данных две: слово и текст, два отсортированных списка.
Указатели навстречу стартуют с двух концов и сходятся. Они нужны, когда решение зависит от пары элементов с разных концов упорядоченных данных.

Правило шага

Старт. Первый элемент остаётся всегда: w = 1, r идёт с 1. Пустой список — сразу вернуть 0.
Новое значение. Если ids[r] отличается от последнего записанного ids[w - 1], записать его в позицию w и сдвинуть w.
Повтор. Если равно — пропустить, w остаётся на месте.
Конец. После прохода удалить хвост del ids[w:] и вернуть w.

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

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

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

r проходит список один раз, w только растёт. Запись идёт в тот же список, дополнительной памяти нет.
r проходит список один раз, w только растёт. Запись идёт в тот же список, дополнительной памяти нет.
Верно. r проходит список один раз, w только растёт. Запись идёт в тот же список, дополнительной памяти нет.
r проходит список один раз, w только растёт. Запись идёт в тот же список, дополнительной памяти нет.

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

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

dedup_sortedглава 8.7

def dedup_sorted(ids):
    if not ids:
        return 0
    w = 1
    for r in range(1, len(ids)):
        if ids[r] != ids[w - 1]:
            ids[w] = ids[r]
            w += 1
    del ids[w:]
    return w

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

Вопрос интервьюераПочему прочитанное значение достаточно сравнить только с последним записанным ids[w - 1]?

Верно. Если ids[r] равно какому-то записанному значению, то оно равно и последнему записанному: между ними другого значения быть не может.
Повторы в ответе условие не допускает. Одного сравнения хватает из-за порядка в списке.
До del ids[w:] из списка ничего не удаляется. Значения левее w − 1 на месте, но сравнивать с ними незачем.

Задача 3 · Сжатие последовательностиLeetCode 443 · глава 8.7

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

«Дан список символов. Замените каждую серию одинаковых символов подряд на символ и длину серии. Результат запишите в тот же список и верните его новую длину.»

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

«Например, aaabcc превращается в a3bc2: для каждой серии пишется символ и, если серия длиннее одного символа, её длина. Всё это пишется в начало того же списка».

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

Сжатие последовательности

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

«Дан список символов. Замените каждую серию одинаковых символов подряд на символ и длину серии. Результат запишите в тот же список и верните его новую длину.»

уточнено

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

вход	ответ и список после вызова	Что проверяет
`['a', 'a', 'a', 'b', 'c', 'c']`	`5 · ['a', '3', 'b', 'c', '2']`	обычный случай
`['a', 'b', 'c']`	`3 · ['a', 'b', 'c']`	одиночные символы
`['x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x', 'x']`	`3 · ['x', '1', '2']`	серия из 12: две цифры
`['a', 'a', 'b', 'a', 'a']`	`5 · ['a', '2', 'b', 'a', '2']`	символ a в двух сериях
`[]`	`0 · []`	пустой список

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

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

Собрать сжатую запись в новой строке, например через "".join, и скопировать обратно. Время O(n), но память O(n), а условие разрешает только O(1).

Форма техникиКакая форма двух указателей подходит?

По указателю на каждую последовательность идут, когда данных две: слово и текст, два отсортированных списка.
Указатели навстречу стартуют с двух концов и сходятся. Они нужны, когда решение зависит от пары элементов с разных концов упорядоченных данных.
Верно. Результат пишется в тот же список, читаем по порядку. Чтение и запись нужны, когда список меняется на месте: r читает каждый элемент, w показывает, куда писать следующий оставленный.

Правило шага

Начало серии. Запомнить start = r.
Конец серии. Двигать r, пока символ тот же и список не кончился: r < n проверяется первым.
Символ. Записать chars[start] в позицию w, сдвинуть w.
Длина. Если r − start > 1, записать цифры длины по одной, сдвигая w.
Конец. Когда r дошёл до конца, удалить хвост del chars[w:] и вернуть w.

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

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

Внешний и внутренний циклы двигают один и тот же r, и он проходит список один раз. Запись идёт в тот же список.
Верно. Внешний и внутренний циклы двигают один и тот же r, и он проходит список один раз. Запись идёт в тот же список.
Внешний и внутренний циклы двигают один и тот же r, и он проходит список один раз. Запись идёт в тот же список.
Внешний и внутренний циклы двигают один и тот же r, и он проходит список один раз. Запись идёт в тот же список.

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

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

compressглава 8.7

def compress(chars):
    w = 0
    r = 0
    n = len(chars)
    while r < n:
        start = r
        while r < n and chars[r] == chars[start]:
            r += 1
        chars[w] = chars[start]
        w += 1
        count = r - start
        if count > 1:
            for d in str(count):
                chars[w] = d
                w += 1
    del chars[w:]
    return w

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

Вопрос интервьюераЗапись идёт в тот же список, который ещё читается. Почему она не затирает непрочитанные символы?

del chars[w:] выполняется после цикла, когда весь список уже прочитан.
Копии нет: chars[w] = … меняет сам список. Поэтому и нужно, чтобы w не обгонял r.
Верно. Серия длины c занимает c позиций, а её запись — символ и цифры числа c, это не больше c. Поэтому после каждой серии w ≤ r.

Задача 4 · Нули в конецLeetCode 283 · глава 8.8

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

«Перенесите все нули в конец списка, сохранив порядок остальных чисел. Копию списка создавать нельзя.»

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

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

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

Нули в конец

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

«Перенесите все нули в конец списка, сохранив порядок остальных чисел. Копию списка создавать нельзя.»

уточнено

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

вход	Список после вызова	Что проверяет
`[0, 4, 0, 0, 7, 2]`	`[4, 7, 2, 0, 0, 0]`	обычный случай
`[3, 1, 2]`	`[3, 1, 2]`	нулей нет
`[0, 0, 0]`	`[0, 0, 0]`	одни нули
`[0, 1]`	`[1, 0]`	два элемента
`[]`	`[]`	пустой список

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

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

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

Форма техникиКакая форма двух указателей подходит?

Указатели навстречу стартуют с двух концов и сходятся. Они нужны, когда решение зависит от пары элементов с разных концов упорядоченных данных.
Верно. Список меняется на месте, порядок ненулевых сохраняется. Чтение и запись нужны, когда список меняется на месте: r читает каждый элемент, w показывает, куда писать следующий оставленный.
По указателю на каждую последовательность идут, когда данных две: слово и текст, два отсортированных списка.

Правило шага

Старт. w = 0 — место для следующего ненулевого числа.
Не ноль. Поменять местами nums[w] и nums[r], сдвинуть w.
Ноль. Пропустить, w остаётся на месте.
Конец. Когда r прошёл список, нули уже в хвосте: обмен переносил их туда.

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

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

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

Верно. r проходит список один раз, каждый шаг — не больше одного обмена. Памяти нужно только под w и r.
r проходит список один раз, каждый шаг — не больше одного обмена. Памяти нужно только под w и r.
r проходит список один раз, каждый шаг — не больше одного обмена. Памяти нужно только под w и r.
r проходит список один раз, каждый шаг — не больше одного обмена. Памяти нужно только под w и r.

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

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

move_zerosглава 8.8

def move_zeros(nums):
    w = 0
    for r in range(len(nums)):
        if nums[r] != 0:
            nums[w], nums[r] = nums[r], nums[w]
            w += 1

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

Вопрос интервьюераИнтервьюер спрашивает, можно ли обойтись без обмена. Какой ответ верный?

Верно. Первый проход пишет nums[w] = nums[r], второй ставит нули с позиции w до конца. Это тоже O(n) по времени и O(1) по памяти.
Обмены с двух концов переставят ненулевые числа, а их порядок по условию нужно сохранить.
Нули пропадают, если только записывать и ничего не делать после цикла. Если заполнить хвост нулями, ответ верный.

Задача 5 · Разделение по порогушаг быстрой сортировки · глава 8.8

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

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

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

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

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

Разделение по порогу

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

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

уточнено

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

nums, limit	Ответ и список	Что проверяет
`[5, 12, 3, 18, 7, 25, 1], 10`	`4 · [5, 1, 3, 7, 18, 25, 12]`	обычный случай
`[8, 0, 12, 9, 5, 3], 10`	`5 · [8, 0, 3, 9, 5, 12]`	указатели сходятся на числе 5
`[11, 12], 10`	`0 · [11, 12]`	все не меньше порога
`[1, 2], 10`	`2 · [1, 2]`	все меньше порога
`[], 10`	`0 · []`	пустой список

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

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

Собрать два новых списка — числа меньше порога и остальные — и записать их обратно: O(n) по времени, но O(n) по памяти. Или отсортировать список: O(n log n), хотя полный порядок не нужен.

Форма техникиКакая форма двух указателей подходит?

Чтение и запись нужны, когда список меняется на месте: r читает каждый элемент, w показывает, куда писать следующий оставленный.
По указателю на каждую последовательность идут, когда данных две: слово и текст, два отсортированных списка.
Верно. Порядок не важен, менять можно элементы с разных концов. Указатели навстречу стартуют с двух концов и сходятся. Они нужны, когда решение зависит от пары элементов с разных концов упорядоченных данных.

Правило шага

Старт. i слева, j справа.
Левый на месте. Если nums[i] < limit, сдвинуть i.
Правый на месте. Иначе, если nums[j] >= limit, сдвинуть j.
Оба не на месте. Иначе поменять их местами и сдвинуть оба указателя.
Конец. Повторять, пока i <= j: элемент, на котором сошлись указатели, тоже проверяется. Вернуть i.

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

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

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

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

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

split_by_limitглава 8.8

def split_by_limit(nums, limit):
    i, j = 0, len(nums) - 1
    while i <= j:
        if nums[i] < limit:
            i += 1
        elif nums[j] >= limit:
            j -= 1
        else:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
    return i

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

Вопрос интервьюераЗачем в условии цикла нестрогое сравнение i <= j?

Верно. На [8, 0, 12, 9, 5, 3] версия с i < j не проверяет число 5 и возвращает 4 вместо 5.
Скорость сравнения от вида знака не зависит. Дело в том, какие элементы цикл успевает проверить.
Каждый шаг сдвигает хотя бы один указатель, цикл закончится и с i < j. Но ответ может оказаться на единицу меньше.

Задача 6 · Три цветаLeetCode 75 · глава 8.8

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

«Список состоит из чисел 0, 1 и 2. Расставьте их по возрастанию за один проход, на месте и без встроенной сортировки.»

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

«Нужно собрать нули в начале, двойки в конце, единицы посередине. Один проход по списку, без sort и без нового списка».

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

Три цвета

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

«Список состоит из чисел 0, 1 и 2. Расставьте их по возрастанию за один проход, на месте и без встроенной сортировки.»

уточнено

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

вход	Список после вызова	Что проверяет
`[2, 0, 2, 1, 1, 0]`	`[0, 0, 1, 1, 2, 2]`	обычный случай
`[1, 2, 0]`	`[0, 1, 2]`	после обмена с high приходит 0
`[2, 2]`	`[2, 2]`	одни двойки
`[0]`	`[0]`	один элемент
`[]`	`[]`	пустой список

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

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

Посчитать нули, единицы и двойки и перезаписать список: время O(n), память O(1), но это два прохода, а условие требует один.

Форма техникиКакая форма двух указателей подходит?

Чтение и запись нужны, когда список меняется на месте: r читает каждый элемент, w показывает, куда писать следующий оставленный.
По указателю на каждую последовательность идут, когда данных две: слово и текст, два отсортированных списка.
Верно. Три группы, один проход, обмены на месте. Три указателя нужны, когда групп три, как в задаче о трёх цветах.
Указатели навстречу стартуют с двух концов и сходятся. Они нужны, когда решение зависит от пары элементов с разных концов упорядоченных данных.

Правило шага

Старт. low = mid = 0, high — последний индекс. Левее low — нули, правее high — двойки.
Ноль. Обменять nums[mid] с nums[low], сдвинуть low и mid.
Единица. Сдвинуть только mid.
Двойка. Обменять с nums[high], сдвинуть high. mid остаётся: пришедшее число ещё не проверено.
Конец. Повторять, пока mid <= high.

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

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

Каждый шаг сдвигает mid вправо или high влево, расстояние между ними уменьшается: шагов не больше n.
Каждый шаг сдвигает mid вправо или high влево, расстояние между ними уменьшается: шагов не больше n.
Верно. Каждый шаг сдвигает mid вправо или high влево, расстояние между ними уменьшается: шагов не больше n.
Каждый шаг сдвигает mid вправо или high влево, расстояние между ними уменьшается: шагов не больше n.

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

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

sort_colorsглава 8.8

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

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

Вопрос интервьюераПочему после обмена с high указатель mid остаётся на месте?

Без сдвига mid шагов не меньше. Сдвиг пропускает непроверенное число, и ответ становится неверным.
Верно. Это может быть 0, 1 или 2, и его нужно проверить. На [1, 2, 0] версия со сдвигом mid пропускает 0 и даёт [1, 0, 2].
mid всегда не левее low, сдвиг вправо этого не меняет. Дело в числе, которое пришло на место mid.

Задача 7 · ПодпоследовательностьLeetCode 392 · глава 8.7

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

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

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

«Буквы слова должны встретиться в тексте в том же порядке, между ними могут стоять любые другие буквы. Вернуть True или False».

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

Подпоследовательность

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

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

уточнено

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

word, text	Ответ	Что проверяет
`'кот', 'компот'`	`True`	буквы с пропусками
`'кот', 'картошка'`	`False`	после «о» нет «т»
`'', 'abc'`	`True`	пустое слово
`'abcd', 'abc'`	`False`	слово длиннее текста
`'aab', 'abab'`	`True`	повторяющиеся буквы

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

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

Перебрать все способы вычеркнуть буквы из текста: их 2 в степени длины текста. Для текста из 40 букв это больше триллиона вариантов.

Форма техникиКакая форма двух указателей подходит?

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

Правило шага

Старт. i = 0: найдено ноль букв слова.
Чтение. j проходит все буквы текста по порядку.
Совпадение. Если i < len(word) и text[j] == word[i], сдвинуть i. Проверка i < len(word) стоит первой: после того как слово найдено, word[i] не существует.
Ответ. После текста вернуть i == len(word).

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

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

j проходит текст один раз, i только растёт. Каждая буква текста сравнивается не больше одного раза.
Верно. j проходит текст один раз, i только растёт. Каждая буква текста сравнивается не больше одного раза.
j проходит текст один раз, i только растёт. Каждая буква текста сравнивается не больше одного раза.
j проходит текст один раз, i только растёт. Каждая буква текста сравнивается не больше одного раза.

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

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

is_subsequenceглава 8.7

def is_subsequence(word, text):
    i = 0
    for j in range(len(text)):
        if i < len(word) and text[j] == word[i]:
            i += 1
    return i == len(word)

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

Вопрос интервьюераСколько раз выполнится проверка в цикле для слова из 3 букв и текста из 1000 букв?

Цикл идёт по буквам текста. Даже когда слово найдено, текст дочитывается до конца.
Так работал бы перебор. Здесь i не возвращается к началу слова.
Верно. j проходит текст один раз, время O(len(text)).

Задача 8 · Подарки в пределах бюджетапохожа на LeetCode 1099 · глава 8.11

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

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

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

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

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

Подарки в пределах бюджета

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

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

уточнено

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

prices, budget	Ответ	Что проверяет
`[700, 250, 1200, 450, 900, 300], 1400`	`1350`	обычный случай: 450 + 900
`[500, 500], 1000`	`1000`	сумма ровно в бюджет
`[900, 800], 1500`	`-1`	единственная пара не укладывается
`[500], 1000`	`-1`	один подарок
`[], 1000`	`-1`	пустой список

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

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

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

Форма техникиКакая форма двух указателей подходит?

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

Правило шага

Сортировка. prices = sorted(prices) — копия, исходный список не меняется.
Сумма в бюджете. Кандидат в ответ: best = max(best, s). Для левой цены лучшая пара уже найдена — сдвинуть i.
Сумма больше бюджета. Правая цена не укладывается даже с самой дешёвой — сдвинуть j.
Конец. Указатели встретились, вернуть best: лучшая сумма или −1.

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

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

Верно. Сортировка копии стоит 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 МБ.

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

best_pair_sumглава 8.11

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

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

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

Верно. Список сортируется на месте, копия на n элементов не создаётся. Время остаётся O(n log n).
Если менять вход разрешено, лишняя копия только тратит O(n) памяти.
Порядка во входе по-прежнему нет, сортировать всё равно нужно. Меняется только то, где лежит отсортированный список.

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

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

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

§3Тренажёр

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