Используйте правильный инструмент для задачи.
На моём первом собеседовании после окончания вуза мне задали классическую задачу про размен монет:
Дан набор номиналов монет, нужно найти минимальное количество монет, чтобы набрать заданную сумму. Например, для американских монет и 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. В декабре как раз пройдут бесплатные демо-уроки:
