Как решать алгоритмические задачи на собеседовании: сначала условие

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

Разберём одно условие.

Условие

Дан массив целых чисел и число k. Верни длину самого длинного подмассива, сумма которого не больше k. В массиве могут быть отрицательные числа. 1 ≤ n ≤ 200000.

Двадцать восемь слов. Шесть из них решают, какой будет алгоритм.

«подмассив»

Подмассив идёт подряд. Подпоследовательность нет.

Одно слово, и половина вариантов отпала. Подряд означает окно или префиксные суммы. Не подряд означает сортировку или динамику.

Слово «подряд» читают неправильно чаще всего. Оно самое дорогое на странице.

«длину»

Ты возвращаешь число. Значит сам подмассив хранить не нужно.

Нужен максимум. Одна переменная с лучшим значением. Одно сравнение.

Вся бухгалтерия.

«не больше k»

Не больше, а не ровно.

Ровно k тянуло бы к словарю префиксных сумм.

Не больше k это диапазон. Тут помогает порядок. Словарь бесполезен.

Ровно k это как раз случай для префиксных сумм в словаре.

Разница в одном слове. Структуры данных разные.

«могут быть отрицательные»

Вот ловушка.

Если чисел меньше нуля нет, расширение окна всегда увеличивает сумму. Именно это делает два указателя законными.

Отрицательные ломают правило. Сумма перестаёт двигаться в одну сторону.

Значит сужение окна может её поднять.

Два указателя стали неверными. Верны префиксные суммы плюс упорядоченная структура.

Одна фраза превратила решение на 5 строк в решение на 20.

Фраза всё это время была в условии.

«1 ≤ n ≤ 200000»

200 тысяч отсекают всё квадратичное. Это 40 миллиардов операций.

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

n log n проходит спокойно. Сортировка по карману. Бинарный поиск внутри цикла тоже.

Граница на n прямо говорит, какую сложность ждёт интервьюер. Читай её как инструкцию. Что разрешает каждая граница, собрано в таблице сложности алгоритмов.

Шесть строк до кода

• Что на входе и что на выходе.
• Размер входа.
• Подряд или нет.
• Отсортировано или нет.
• Края: пусто, один элемент, все отрицательные.
• Какой это паттерн. И какое слово тебя к нему привело.

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

Не можешь назвать слово, значит угадал. Угаданный ответ не учит ничему.

Две минуты, а не тридцать секунд

В интервью на 45 минут две минуты на чтение кажутся роскошью. Если от часов пустеет голова, есть скрипт спасения на пять минут.

Две минуты на чтение стоят дешевле всего в интервью.

Неправильно прочитанное условие стоит всей сессии. Узнаешь ты на тридцатой минуте. На доске уже чужой ответ.

Быстрое чтение никто не оценивает.

Остальная рутина вокруг этого в статье как готовиться правильно.

Где это тренируется

В AlgoPath каждый шаг начинается с сигналов. Это слова в задаче, которые указывают на паттерн.

Назвать паттерн надо до кода.

В тренажёре распознавания задача приходит без метки. Сначала называешь паттерн и обосновываешь.

Первые 33 шага бесплатные.