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

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

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

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

Условие

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

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

«подмассив»

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

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

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

«длину»

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

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

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

«не больше k»

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

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

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

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

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

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

Вот ловушка.

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

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

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

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

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

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

«1 ≤ n ≤ 200000»

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

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

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

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

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

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

Последняя строка главная.

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

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

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

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

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

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

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

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

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

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

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

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