1. Жадный алгоритм в задаче банкомата
Задача реализации банкомата — абсолютная классика на секциях лайвкодинга в крупных IT-компаниях. На первый взгляд она кажется тривиальной: нужно просто отнимать числа. Однако реальная цель интервьюера — проверить ваше умение работать с состоянием, обеспечивать потокобезопасность и грамотно проектировать контракты.
Анатомия жадного алгоритма
В основе логики выдачи наличных лежит жадный алгоритм (greedy algorithm). Его суть заключается в принятии локально оптимальных решений на каждом шаге. В контексте банкомата это означает: чтобы выдать запрошенную сумму минимальным количеством купюр, нужно всегда начинать с самого крупного доступного номинала.
Представьте, что клиент запрашивает 6550 руб. Алгоритм действует пошагово:
!Визуализация работы жадного алгоритма при выдаче наличных
Ограничения алгоритма
Жадный алгоритм работает безупречно и со скоростью (где — количество номиналов) только для канонических систем счисления. В таких системах каждый следующий номинал кратен предыдущим или суммам предыдущих (например, 50, 100, 500, 1000).
Если система номиналов неканоническая, жадный подход может дать сбой.
Представьте банкомат в вымышленной стране, где есть купюры номиналом 40 и 30. Клиент просит выдать 60. Жадный алгоритм возьмёт купюру 40. Останется 20. Купюр по 20 нет, поэтому алгоритм выдаст ошибку: «Сумму собрать невозможно». При этом реальное решение существует: две купюры по 30. Для решения таких задач используется динамическое программирование (dynamic programming), которое требует памяти и работает медленнее.
> Упоминание на собеседовании того факта, что вы знаете, в каких случаях жадный алгоритм ломается, гарантированно добавит вам баллов в глазах интервьюера.
Проектирование контракта
Прежде чем писать алгоритм, необходимо определить интерфейс. Частая ошибка новичков — выбрасывать исключения (например, NotEnoughMoneyException), если сумму выдать нельзя.
Нехватка подходящих купюр — это штатная бизнес-ситуация, а не системный сбой. Исключения в Java дороги в создании (из-за сбора stack trace) и не должны использоваться для управления потоком выполнения. Лучше использовать Optional.
Для хранения состояния банкомата идеально подходит TreeMap с компаратором Collections.reverseOrder(). Эта структура данных автоматически сортирует ключи (номиналы) по убыванию — от 5000 к 50, что является фундаментом для нашего жадного прохода.
Транзакционность и потокобезопасность
Банкомат — классический пример системы, подверженной состоянию гонки (race condition). Если два пользователя одновременно попытаются снять деньги через разные терминалы, обращающиеся к одному бэкенду, баланс может уйти в минус.
Для синхронизации мы будем использовать ReentrantLock. В отличие от ключевого слова synchronized, локи предоставляют больше гибкости. Например, в будущем можно использовать метод tryLock(1, TimeUnit.SECONDS), чтобы не блокировать поток навечно, если банкомат завис, а быстро отдать клиенту ошибку таймаута.
Главное правило реализации метода withdraw — fail-fast (быстрый отказ) и транзакционность. Мы не имеем права списывать купюры из хранилища по одной. Если в середине процесса окажется, что точную сдачу выдать нельзя, банкомат останется в сломанном состоянии (часть денег уже списана, но клиенту они не выданы).
Обратите внимание на локальную переменную result. Это наш буфер. Мы проводим все вычисления в памяти, и только если remaining достигает нуля, применяем изменения к основному inventory. Это классический паттерн Commit/Rollback.
Защитное копирование состояния
Реализуя метод получения текущего баланса, легко совершить фатальную ошибку — просто вернуть ссылку на внутреннюю мапу.
Мы используем защитное копирование (defensive copying). В Java коллекции мутабельны. Если вернуть оригинальный inventory, любой внешний код сможет вызвать atm.getInventory().clear(). Это мгновенно обнулит кассу банкомата в обход всех наших блокировок и проверок. Возвращая новый экземпляр TreeMap, мы инкапсулируем состояние.
Сравнение подходов к задаче
| Подход | Преимущества | Недостатки |
|--------|--------------|------------|
| Жадный алгоритм | Максимальная скорость . Идеально для стандартных валют. Прост в поддержке. | Не найдёт решение для неканонических номиналов. |
| Динамическое программирование | Найдёт решение всегда, если оно физически существует. | Сложнее в реализации. Потребляет больше памяти . |
| ConcurrentHashMap | Быстрое чтение без блокировок. | Не подходит для withdraw, так как операция проверки и списания нескольких ключей должна быть атомарной транзакцией. |
Тестирование логики
При написании юнит-тестов критически важно проверять не только возвращаемый результат, но и изменение внутреннего состояния (мутации).
Каждый тест должен выполняться в изоляции. Для этого в JUnit 5 используется аннотация @BeforeEach, которая пересоздаёт объект банкомата перед каждым тестовым методом. Если этого не сделать, первый тест снимет деньги, а второй упадёт из-за пустой кассы.
В тесте выше мы проверяем ключевое требование безопасности: если операция не удалась, состояние системы должно остаться абсолютно идентичным тому, каким оно было до начала операции.