Алгозадачи 1: один проход и хеш-таблица

Первый из трёх уроков алгопрактики. Берём классические задачи уровня easy и решаем каждую дважды: императивно, с var и циклом, и функционально, через reduce и конвейер. Цель не в самих задачах, а в том, чтобы наработать переводчик: слышишь задачу, видишь паттерн, пишешь Janet, не подглядывая.

Правила игры

Три договорённости на весь блок.

Первая: решаем в REPL или в файле с assert, как в уроке про тесты. Каждое решение сразу закрепляем проверкой:

(assert (deep= (two-sum [2 7 11 15] 9) [0 1]))

Вторая: сложность оцениваем всегда. Проговаривай про себя «время O(n), память O(n)» после каждого решения, на собеседовании этот вопрос прозвучит обязательно.

Третья: у большинства задач будет два решения. Императивное с изменяемым состоянием и функциональное, где состояние протаскивается через свёртку. Janet не заставляет выбирать стиль, и в этом его прелесть: сравнивай и бери тот, что читается лучше.

Два слагаемых

Дан массив чисел и цель. Найти индексы двух элементов, дающих в сумме цель. Классика номер один, задача Two Sum.

Лобовое решение перебирает все пары. В Janet вложенный перебор записывается одним loop с двумя глаголами, это ты помнишь из урока про циклы:

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

Время O(n), память O(n). Обрати внимание на строчку (when j ...): индекс j может быть нулём, и в JavaScript проверка if (j) тут дала бы ложный промах. В Janet ложны только nil и false, ноль истинен, поэтому код честен без дополнительной проверки на существование ключа.

Лучшая сделка

Массив цен по дням. Купить один раз, продать один раз, не раньше покупки. Какая прибыль максимальна?

Инсайт: для каждого дня лучшая сделка это цена дня минус минимум всех предыдущих дней. Значит, хватит одного прохода с двумя переменными:

Теперь функционально. Пара переменных превращается в кортеж-аккумулятор, тело цикла в функцию:

Деструктуризация аккумулятора прямо в параметрах функции делает перевод дословным. Это общий рецепт: любой однопроходный алгоритм с переменными это reduce с кортежем. Императивная версия здесь читается чуть легче, функциональная не создаёт изменяемого состояния вовсе. Оба ответа правильные.

Анаграммы

Являются ли две строки анаграммами? Задача Valid Anagram, и она про то, что строки в Janet перебираются по байтам.

Функциональное решение почти однострочник:

frequencies строит таблицу «байт, сколько раз встретился». Ловушка в сравнении: = для таблиц сравнивает ссылки, а не содержимое, мы разбирали это в уроке про значения. Поэтому deep= обязателен, с = функция всегда отвечала бы false.

Императивная версия не строит двух таблиц, ей хватает одного массива счётчиков на все 256 байтов:

Память O(1): массив фиксированного размера, какой бы длинной ни была строка. Для юникода за пределами ASCII оба решения работают одинаково честно, потому что одинаковые строки состоят из одинаковых байтов.

Лидер массива

Найти элемент, который встречается больше чем в половине позиций. Задача Majority Element.

Решение через frequencies пишется конвейером из урока про переходы:

Таблица частот, пары «число и счётчик», сортировка по счётчику, последняя пара, её первый элемент. Читается сверху вниз как рецепт. Время O(n log n) из-за сортировки, память O(n).

Но у этой задачи есть красивое решение за O(n) времени и O(1) памяти, голосование Бойера и Мура. Держим кандидата и счёт голосов: совпал элемент с кандидатом, голос плюс, не совпал, минус, счёт обнулился, меняем кандидата:

Лидер по условию занимает больше половины позиций, поэтому перекричать его невозможно. Этот алгоритм в функциональный стиль переводится, но хуже читается: изредка императив выигрывает чисто, и это нормально.

Двоичный поиск

Найти элемент в отсортированном массиве за O(log n). Задача, в которой ошибаются на границах чаще, чем во всех остальных вместе взятых.

div это целочисленное деление из урока про литералы, обычный / вернул бы дробный индекс.

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

Заметь инвариант: слева от lo всё меньше цели, начиная с hi всё не меньше. Цикл сжимает зазор между ними до нуля. Держи эту формулировку в голове, и границы перестанут путаться. Левая граница ещё вернётся в третьем уроке блока внутри задачи про подпоследовательности.

Что запомнить

• Хеш-таблица превращает «найди пару» из O(n²) в O(n): один проход, для каждого элемента спрашиваем таблицу о недостающей половине.
• Ноль в Janet истинен, поэтому (when index ...) безопасен даже для нулевого индекса.
• Однопроходный алгоритм с переменными механически переводится в reduce с кортежем-аккумулятором. Выбирай стиль по читаемости.
• Строки перебираются по байтам, frequencies строит таблицу частот, сравнивать таблицы нужно через deep=.
• Голосование Бойера и Мура находит лидера за O(n) времени и O(1) памяти.
• Левая граница полезнее точного двоичного поиска. Формулируй инвариант границ, а не заучивай плюс-минус единицы.

Упражнения

Все шесть это реальные задачи easy с собеседований. К каждой напиши assert на пример из условия и на пустой массив.

Дальше

Разминка позади. Дальше уровень medium: два указателя, скользящее окно, префиксные суммы и группировка. Там один паттерн закрывает целое семейство задач.