#2241

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Design an ATM Machine

Design an ATM machine that stores and withdraws money with given denominations and prioritizes larger values during withdrawals.

array greedy design

Problem Statement

Design an ATM machine that stores and manages money with five denominations: 20, 50, 100, 200, and 500 dollars. Initially, the machine is empty. It can process deposits and withdrawals of any amount. The goal is to maintain and adjust the banknotes stored in the machine after each transaction.

When a user withdraws money, the machine should prioritize larger denominations, using the highest value banknotes first. If the requested amount cannot be fully withdrawn with the available denominations, the withdrawal should be rejected. Implement the ATM class to handle both deposit and withdrawal operations, while ensuring the correct banknotes are available and the correct values are returned.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"] [[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]] Output [null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

Explanation ATM atm = new ATM(); atm.deposit([0,0,1,2,1]); // Deposits 1 $100 banknote, 2$ 200 banknotes, // and 1 $500 banknote. atm.withdraw(600); // Returns [0,0,1,0,1]. The machine uses 1$ 100 banknote // and 1 $500 banknote. The banknotes left over in the // machine are [0,0,0,2,0]. atm.deposit([0,1,0,1,1]); // Deposits 1$ 50, $200, and$ 500 banknote. // The banknotes in the machine are now [0,1,0,3,1]. atm.withdraw(600); // Returns [-1]. The machine will try to use a $500 banknote // and then be unable to complete the remaining$ 100, // so the withdraw request will be rejected. // Since the request is rejected, the number of banknotes // in the machine is not modified. atm.withdraw(550); // Returns [0,1,0,0,1]. The machine uses 1 $50 banknote // and 1$ 500 banknote.

Constraints

banknotesCount.length == 5
0 <= banknotesCount[i] <= 109
1 <= amount <= 109
At most 5000 calls in total will be made to withdraw and deposit.
At least one call will be made to each function withdraw and deposit.
Sum of banknotesCount[i] in all deposits doesn't exceed 109

Solution Approach

Greedy Choice for Withdrawal

During a withdrawal, prioritize using larger denominations first. This greedy approach ensures that the machine uses the fewest banknotes possible to fulfill the requested amount.

Invariant Validation

After each withdrawal attempt, validate that the remaining banknotes can still support further withdrawals. If the transaction cannot be completed, reject it and keep the current banknotes unchanged.

Efficient Banknote Management

Track the number of banknotes for each denomination in the machine. Update the counts after deposits and withdrawals to ensure efficient handling of future transactions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach used for withdrawal and deposit operations, especially the complexity of iterating over denominations. Space complexity will be determined by the need to store banknote counts for each denomination and transaction state.

What Interviewers Usually Probe

Can the candidate handle greedy algorithms effectively?
Does the candidate consider edge cases for failed withdrawals?
How efficiently does the candidate track and update the banknotes?

Common Pitfalls or Variants

Common pitfalls

Failing to reject a withdrawal when the exact amount cannot be made with the available banknotes.
Not prioritizing larger denominations, resulting in using more banknotes than necessary.
Incorrectly managing the banknote counts after multiple deposits and withdrawals, leading to errors in future transactions.

Follow-up variants

Modify the ATM to handle additional banknote denominations.
Implement a version where withdrawal requests prioritize minimizing the number of banknotes rather than using larger denominations.
Extend the problem to handle scenarios where multiple users are interacting with the ATM simultaneously.

FAQ

How can I design an ATM machine that handles multiple deposits and withdrawals efficiently?

Focus on greedy choice for withdrawals, ensuring that larger denominations are used first. Update banknote counts after each transaction.

What is the greedy choice pattern in the 'Design an ATM Machine' problem?

The greedy choice involves using the largest possible denominations first during a withdrawal to minimize the number of banknotes used.

What should be done when a withdrawal cannot be completed with the available banknotes?

The transaction should be rejected, and the banknotes in the machine should remain unchanged.

How do I track banknotes in the ATM?

Store the number of each banknote denomination in an array or list. Update the counts during deposit and withdrawal operations.

What edge cases should I consider when solving the 'Design an ATM Machine' problem?

Consider scenarios where withdrawals cannot be completed due to insufficient banknotes, and ensure that the ATM behaves correctly when no withdrawal is possible.

terminal

Solution

Solution 1: Simulation

We use an array $\textit{d}$ to record the denominations of the bills and an array $\textit{cnt}$ to record the number of bills for each denomination.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class ATM:
    def __init__(self):
        self.d = [20, 50, 100, 200, 500]
        self.m = len(self.d)
        self.cnt = [0] * self.m

    def deposit(self, banknotesCount: List[int]) -> None:
        for i, x in enumerate(banknotesCount):
            self.cnt[i] += x

    def withdraw(self, amount: int) -> List[int]:
        ans = [0] * self.m
        for i in reversed(range(self.m)):
            ans[i] = min(amount // self.d[i], self.cnt[i])
            amount -= ans[i] * self.d[i]
        if amount > 0:
            return [-1]
        for i, x in enumerate(ans):
            self.cnt[i] -= x
        return ans


# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)

Continue Practicing

#2244 minimum rounds to complete all tasks #2234 maximum total beauty of the gardens #2233 maximum product after k increments