Используйте правильный инструмент для задачи.

На моём первом собеседовании после окончания вуза мне задали классическую задачу про размен монет:

Дан набор номиналов монет, нужно найти минимальное количество монет, чтобы набрать заданную сумму. Например, для американских монет и 37 центов минимум — четыре монеты (квотер, дайм и 2 пенни).

Я реализовал простой жадный алгоритм и сразу попался в ловушку этого вопроса: жадный алгоритм работает только для «хорошо устроенных» наборов номиналов. Если номиналы равны [10, 9, 1], то для 37 центов жадный алгоритм возьмёт 10 монет, а оптимальное решение — 4 монеты (10+9+9+9). «Правильный» ответ — использовать алгоритм динамического программирования, которому я тогда был не обучен. Поэтому я провалил собеседование.

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

int: total;
array[int] of int: values = [10, 9, 1];
array[index_set(values)] of var 0..: coins;

constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
solve minimize sum(coins);

Вы можете попробовать это онлайн здесь. Вас попросят ввести total, а затем покажут последовательно улучшающиеся решения:

coins = [0, 0, 37];
----------
coins = [0, 1, 28];
----------
coins = [0, 2, 19];
----------
coins = [0, 3, 10];
----------
coins = [0, 4, 1];
----------
coins = [1, 3, 0];
----------

Многие похожие вопросы на собеседованиях — это такого рода задачи математической оптимизации, где нужно найти максимум или минимум функции при заданных ограничениях. Они кажутся сложными в обычных языках программирования, потому что сами языки слишком низкоуровневые. Зато ровно под такие задачи и создавались решатели ограничений (англ. constraint solvers). Сложные leetcode-задачи — это простые задачи на ограничения. Здесь я использую MiniZinc, но вы вполне можете взять Z3, OR-Tools или любой другой любимый универсальный решатель.

Больше примеров

Рассмотрим еще одну задачу с другого собеседования (которое я, к счастью, прошёл):

Дан список цен акций в течение дня. Найдите максимальную прибыль, которую можно получить, купив одну акцию и продав её позже.

Легко сделать это за O(n²), а если чуть подумать — и за O(n). Или можно вообще не быть «хитрым» и просто записать задачу как задачу на ограничения:

array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
var int: buy;
var int: sell;
var int: profit = prices[sell] - prices[buy];

constraint sell > buy;
constraint profit > 0;
solve maximize profit;

Когда я уже работал в той компании, мы тестировали ещё один вопрос для собеседований:

Дан список чисел. Определите, можно ли выбрать из него три числа и, складывая или вычитая их, получить 0?

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

include "globals.mzn";
array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array[index_set(numbers)] of var {0, -1, 1}: choices;

constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
constraint count(choices, -1) + count(choices, 1) = 3;
solve satisfy;

Ещё один пример напоследок — задача, с которой я столкнулся в прошлом году на Chipy AlgoSIG. Формат там такой: берут несколько задач с LeetCode, и мы все их решаем. Вот эту задачу я решить не смог:

Дан массив целых чисел heights, представляющий высоты столбцов гистограммы, где ширина каждого столбца равна 1. Нужно вернуть площадь наибольшего прямоугольника в этой гистограмме.

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

array[int] of int: numbers = [2,1,5,6,2,3];

var 1..length(numbers): x; 
var 1..length(numbers): dx;
var 1..: y;

constraint x + dx <= length(numbers);
constraint forall (i in x..(x+dx)) (y <= numbers[i]);

var int: area = (dx+1)*y;
solve maximize area;

output ["(\(x)->\(x+dx))*\(y) = \(area)"]

Есть даже способ автоматически визуализировать решение (с помощью vis_geost_2d), но разбираться с этим к выходу очередного выпуска рассылки мне было уже лень.

Это лучше?

Если бы я действительно приносил такие задачи на собеседование, кандидат легко мог бы испортить мне день вопросом «Какова временная сложность вашего решения?». Время работы решателей ограничений плохо предсказуемо и почти всегда хуже, чем у идеального «заточенного» алгоритма, потому что решатели гораздо более выразительны. Я называю это компромиссом между возможностями и вычислительной сложностью (capability/tractability tradeoff). Но даже так они обычно работают значительно лучше, чем плохо написанный «самодельный» алгоритм, а я недостаточно силён в ручной реализации алгоритмов, чтобы стабильно обгонять решатель.

Однако настоящая сила решателей — в том, как легко они переваривают новые ограничения. Взглянем снова на задачу про выбор моментов покупки и продажи акций. Я могу написать алгоритм O(n²) за несколько минут и алгоритм O(n), если дать мне немного подумать. А теперь изменим условие:

Максимизировать прибыль, покупая и продавая до max_sales акций, при этом в каждый момент времени можно либо купить, либо продать только одну акцию, и одновременно можно держать не более max_hold акций.

Это уже гораздо более сложная задача даже для неэффективного алгоритма! Зато как задача на ограничения она усложняется лишь немного:

include "globals.mzn";
int: max_sales = 3;
int: max_hold = 2;
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array [1..max_sales] of var int: buy;
array [1..max_sales] of var int: sell;
array [index_set(prices)] of var 0..max_hold: stocks_held;
var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);

constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
constraint profit > 0;

constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
constraint alldifferent(buy ++ sell);
solve maximize profit;

output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];

Большинство примеров использования решателей ограничений в интернете — это головоломки вроде судоку или «SEND + MORE = MONEY». Решать задачи с LeetCode было бы куда более интересной демонстрацией. К тому же они дают больше поводов поговорить про оптимизации, например про разрушение симметрии (symmetry breaking).

Если идея «сложную задачу формулируем, а дальше за нас работает оптимизатор» откликается, можно посмотреть, как это устроено в мире ML. В декабре как раз пройдут бесплатные демо-уроки:

• 3 декабря. Механика обучения: как нейросеть находит правильные веса. Подробнее

• 8 декабря. PyTorch с нуля: работа с тензорами и обучение нейросетей. Подробнее

• 10 декабря. Секреты дообучения трансформеров на примере BERT. Подробнее