Как выдать сумму банкоматом с наименьшим количеством купюр

Что проверяют

Узнаете ли вы задачу о размене и понимаете ли, когда жадный алгоритм даёт верный ответ, а когда нет. Жадное решение пишут почти все. Следом спрашивают: «А если номиналы произвольные?» или «А если в кассетах ограниченное число купюр?»

Как отвечать

Начните с уточнений: какие номиналы, есть ли лимит купюр каждого вида, что вернуть, если сумму выдать нельзя. Затем идите от простого к сложному:

• жадный алгоритм: сортируете номиналы по убыванию и берёте крупную купюру, пока она помещается. Сложность O(k) по числу номиналов. Для рублёвого ряда 100, 200, 500, 1000, 2000, 5000 при неограниченном запасе он даёт оптимум, но это свойство набора, а не алгоритма;
• контрпример: номиналы 500 и 200, сумма 600. Жадный возьмёт 500 и застрянет на остатке 100, хотя три купюры по 200 подходят. На наборе 1, 3, 4 и сумме 6 он даст 4+1+1 вместо 3+3;
• динамика: массив dp длиной amount + 1, заполненный Infinity, dp[0] = 0, переход dp[s] = min(dp[s], dp[s - d] + 1) для каждого номинала. Сложность O(amount * k). Суммы в банкомате кратны 100, поэтому всё делится на общий делитель номиналов, и массив становится в сто раз короче;
• ограниченный запас купюр: это уже ограниченный рюкзак. Номиналов мало, поэтому часто хватает перебора с возвратом и отсечением по текущему лучшему ответу.

Для фронтенда проговорите интерфейс функции: на вход число и объект номиналов с остатками, на выход Map или объект вида «номинал: количество», а невыдаваемую сумму лучше возвращать как null или бросать ошибку, но не строкой вперемешку с объектом. Сумма в рублях целая, поэтому Number тут безопасен, но проверьте вход на Number.isInteger и отрицательные значения.

Где спотыкаются

Называют жадное решение динамическим программированием. Это разные подходы, и интервьюер сразу попросит объяснить разницу.

Утверждают, что жадный алгоритм всегда оптимален, и не могут привести контрпример.

Не проверяют граничные случаи: сумма 0, сумма меньше минимального номинала, сумма, не кратная ни одной комбинации, пустой банкомат.