Design an ATM Machine
MedPrompt
There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.
When withdrawing, the machine prioritizes using banknotes of larger values.
- For example, if you want to withdraw
$300and there are2$50banknotes,1$100banknote, and1$200banknote, then the machine will use the$100and$200banknotes. - However, if you try to withdraw
$600and there are3$200banknotes and1$500banknote, then the withdraw request will be rejected because the machine will first try to use the$500banknote and then be unable to use banknotes to complete the remaining$100. Note that the machine is not allowed to use the$200banknotes instead of the$500banknote.
Implement the ATM class:
ATM()Initializes the ATM object.void deposit(int[] banknotesCount)Deposits new banknotes in the order$20,$50,$100,$200, and$500.int[] withdraw(int amount)Returns an array of length5of the number of banknotes that will be handed to the user in the order$20,$50,$100,$200, and$500, and update the number of banknotes in the ATM after withdrawing. Returns[-1]if it is not possible (do not withdraw any banknotes in this case).
Example 1:
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 == 50 <= banknotesCount[i] <= 1091 <= amount <= 109- At most
5000calls in total will be made towithdrawanddeposit. - At least one call will be made to each function
withdrawanddeposit. - Sum of
banknotesCount[i]in all deposits doesn't exceed109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the ATM operations using a TreeMap to store the banknote counts. The keys of the map are the banknote denominations (e.g., 500, 200), and the values are their respective counts. A TreeMap with a reverse order comparator is used to automatically keep the denominations sorted from largest to smallest, which simplifies the withdrawal logic by allowing direct iteration in the prioritized order.
Algorithm
- In the
ATMclass, initialize adenominationsarray{20, 50, 100, 200, 500}. - Use a
TreeMap<Integer, Long>with a reverse order comparator to store banknote counts, mapping denomination values to their counts. Initialize all counts to 0. deposit(int[] banknotesCount):- Iterate through the input
banknotesCountarray fromi = 0to4. - For each index
i, get the corresponding denominationd = denominations[i]. - Update the count in the
TreeMap:map.put(d, map.get(d) + banknotesCount[i]).
- Iterate through the input
withdraw(int amount):- Create a temporary map or array to store the number of notes to be withdrawn for each denomination.
- Iterate through the
TreeMap's entries. Since we used a reverse order comparator, this will be from the largest denomination to the smallest. - For each denomination
dwith available countc, calculate the number of notes to take:notesToTake = min(amount / d, c). - Record
notesToTakeand update the remainingamountby subtractingnotesToTake * d. - After iterating through all denominations, check if the remaining
amountis zero. - If
amountis 0, the withdrawal is successful. Update the mainTreeMapwith the new counts and return an array representing the withdrawn notes. - If
amountis not 0, the withdrawal is impossible. Return[-1]without modifying the ATM's state.
Walkthrough
The core idea is to use a data structure that naturally handles sorted keys to represent the denominations. A TreeMap is a good fit for this. We store the count of each banknote denomination as a long to prevent overflow, as the number of notes can be large.
Initialization (ATM()):
We initialize a TreeMap<Integer, Long> with a reverse order comparator. This ensures that when we iterate over its keys or entries, they are processed in descending order (500, 200, 100, 50, 20), which is exactly what the withdrawal logic requires.
Deposit (deposit(int[] banknotesCount)):
For a deposit, we iterate through the input banknotesCount array. For each index i, we find the corresponding denomination value and update its count in the TreeMap.
Withdraw (withdraw(int amount)):
For a withdrawal, we follow the specified greedy algorithm. We iterate through the TreeMap's entries (from largest to smallest denomination). For each denomination, we calculate the maximum number of banknotes we can take without exceeding the remaining amount or the available count. We keep track of the notes to be withdrawn. If we can satisfy the entire amount, we finalize the transaction by updating the counts in the TreeMap and returning the result. If any amount is left over after checking all denominations, the transaction is impossible, and we return [-1].
import java.util.Collections;import java.util.HashMap;import java.util.Map;import java.util.TreeMap; class ATM { private TreeMap<Integer, Long> bank; private int[] denominations = {20, 50, 100, 200, 500}; private Map<Integer, Integer> denToIndex; public ATM() { bank = new TreeMap<>(Collections.reverseOrder()); denToIndex = new HashMap<>(); for (int i = 0; i < 5; i++) { bank.put(denominations[i], 0L); denToIndex.put(denominations[i], i); } } public void deposit(int[] banknotesCount) { for (int i = 0; i < 5; i++) { int den = denominations[i]; bank.put(den, bank.get(den) + banknotesCount[i]); } } public int[] withdraw(int amount) { long currentAmount = amount; int[] result = new int[5]; for (Map.Entry<Integer, Long> entry : bank.entrySet()) { int den = entry.getKey(); long count = entry.getValue(); long numNotes = Math.min(currentAmount / den, count); result[denToIndex.get(den)] = (int) numNotes; currentAmount -= numNotes * den; } if (currentAmount > 0) { return new int[]{-1}; } // Update bank counts after a successful withdrawal for (int i = 0; i < 5; i++) { int den = denominations[i]; bank.put(den, bank.get(den) - result[i]); } return result; }}Complexity
Time
O(1) - For each operation, the complexity is technically O(k log k) where k is the number of denominations. Since k is a small constant (5), the overall time complexity is constant, O(1). However, the constant factor is larger than in the array-based approach due to map operations.
Space
O(1) - The space used is constant because the number of denominations (k=5) is fixed. We store a map and an array of size k.
Trade-offs
Pros
The code can be more descriptive as it uses actual denomination values as keys instead of array indices.
This approach is flexible. If the set of denominations were to change, a
TreeMapcould handle it more dynamically than a fixed-size array (though this is not a requirement of the current problem).
Cons
Slightly more complex to implement compared to a simple array-based solution.
Less performant due to the overhead of
TreeMapoperations (logarithmic time complexity for gets and puts) and object creation for map entries.Requires an extra mapping step to convert between the problem's array index format and the map's key-based format for input and output.
This approach uses two simple arrays to manage the ATM's state: a long array for the counts of each banknote and an int array for the corresponding denomination values. The indices of the arrays are implicitly linked. This method is highly efficient because it relies on direct array indexing, which is a constant time operation.
Algorithm
- In the
ATMclass, initialize along[] countsof size 5 to all zeros to store banknote counts. - Also, initialize a final
int[] denominations = {20, 50, 100, 200, 500}to map array indices to banknote values. deposit(int[] banknotesCount):- Iterate from
i = 0to4. - Add the deposited count to the existing count:
counts[i] += banknotesCount[i].
- Iterate from
withdraw(int amount):- Create a result array
int[] result = new int[5]. - Use a
longvariableremainingAmountinitialized withamount. - Iterate backwards from
i = 4down to0(from $500 to $20). - For each index
i, calculate the number of notes to take:notesToTake = min(remainingAmount / denominations[i], counts[i]). - Store this number in
result[i]. - Decrease
remainingAmountbynotesToTake * denominations[i]. - After the loop, if
remainingAmountis 0, the withdrawal is successful.- Update the
countsarray by subtracting theresultarray's values. - Return
result.
- Update the
- If
remainingAmountis greater than 0, the withdrawal is not possible. Return[-1].
- Create a result array
Walkthrough
This is the most straightforward and performant way to solve the problem. We use a long array of size 5, counts, where counts[i] stores the number of banknotes of the i-th denomination. A separate int array, denominations, stores the value of each banknote, so denominations[0] is 20, denominations[1] is 50, and so on.
Initialization (ATM()):
The constructor initializes the counts array to all zeros and sets up the denominations array.
Deposit (deposit(int[] banknotesCount)):
Depositing is a simple loop that adds the values from the input banknotesCount array to our counts array.
Withdraw (withdraw(int amount)):
The withdrawal logic directly implements the required greedy strategy. It iterates backward through the arrays (from index 4 to 0) to process denominations from largest to smallest. In each step, it calculates how many notes of the current denomination can be used. If the total amount can be formed this way, the counts array is updated, and the result is returned. Otherwise, no changes are made, and [-1] is returned.
class ATM { private long[] counts; private int[] denominations; public ATM() { counts = new long[5]; denominations = new int[]{20, 50, 100, 200, 500}; } public void deposit(int[] banknotesCount) { for (int i = 0; i < 5; i++) { counts[i] += banknotesCount[i]; } } public int[] withdraw(int amount) { long remainingAmount = amount; int[] result = new int[5]; for (int i = 4; i >= 0; i--) { int den = denominations[i]; long availableNotes = counts[i]; // Calculate how many notes of the current denomination to take long notesToTake = Math.min(remainingAmount / den, availableNotes); result[i] = (int)notesToTake; remainingAmount -= notesToTake * den; } // If we couldn't make the exact amount, the withdrawal is invalid if (remainingAmount > 0) { return new int[]{-1}; } // If successful, update the ATM's banknote counts for (int i = 0; i < 5; i++) { counts[i] -= result[i]; } return result; }}Complexity
Time
O(1) - All operations (`deposit` and `withdraw`) involve a loop that runs a fixed number of times (5), making their time complexity constant.
Space
O(1) - The space complexity is constant as we only use two fixed-size arrays (size 5) regardless of the number of operations.
Trade-offs
Pros
Highly efficient due to the use of arrays and direct indexing, resulting in O(1) time complexity for all operations.
Simple, clean, and easy to implement and understand.
Minimal memory overhead.
The array-based structure naturally aligns with the input and output format specified in the problem.
Cons
The code is slightly less descriptive as it relies on indices (0-4) to represent denominations.
It's less flexible if the set of denominations were dynamic, as it's hardcoded for 5 specific denominations.
Solutions
Solution
class ATM { private long [] cnt = new long [ 5 ]; private int [] d = { 20 , 50 , 100 , 200 , 500 }; public ATM () { } public void deposit ( int [] banknotesCount ) { for ( int i = 0 ; i < banknotesCount . length ; ++ i ) { cnt [ i ] += banknotesCount [ i ]; } } public int [] withdraw ( int amount ) { int [] ans = new int [ 5 ]; for ( int i = 4 ; i >= 0 ; -- i ) { ans [ i ] = ( int ) Math . min ( amount / d [ i ], cnt [ i ]); amount -= ans [ i ] * d [ i ]; } if ( amount > 0 ) { return new int [] {- 1 }; } for ( int i = 0 ; i < 5 ; ++ i ) { cnt [ i ] -= ans [ i ]; } return ans ; } } /** * Your ATM object will be instantiated and called as such: * ATM obj = new ATM(); * obj.deposit(banknotesCount); * int[] param_2 = obj.withdraw(amount); */class ATM { public: ATM () { } void deposit ( vector < int > banknotesCount ) { for ( int i = 0 ; i < banknotesCount . size (); ++ i ) { cnt [ i ] += banknotesCount [ i ]; } } vector < int > withdraw ( int amount ) { vector < int > ans ( 5 ); for ( int i = 4 ; ~ i ; -- i ) { ans [ i ] = min ( 1ll * amount / d [ i ], cnt [ i ]); amount -= ans [ i ] * d [ i ]; } if ( amount > 0 ) { return { - 1 }; } for ( int i = 0 ; i < 5 ; ++ i ) { cnt [ i ] -= ans [ i ]; } return ans ; } private: long long cnt [ 5 ] = { 0 }; int d [ 5 ] = { 20 , 50 , 100 , 200 , 500 }; }; /** * Your ATM object will be instantiated and called as such: * ATM* obj = new ATM(); * obj->deposit(banknotesCount); * vector<int> param_2 = obj->withdraw(amount); */class ATM : def __init__ ( self ): self . cnt = [ 0 ] * 5 self . d = [ 20 , 50 , 100 , 200 , 500 ] def deposit ( self , banknotesCount : List [ int ]) -> None : for i , v in enumerate ( banknotesCount ): self . cnt [ i ] += v def withdraw ( self , amount : int ) -> List [ int ]: ans = [ 0 ] * 5 for i in range ( 4 , - 1 , - 1 ): ans [ i ] = min ( amount // self . d [ i ], self . cnt [ i ]) amount -= ans [ i ] * self . d [ i ] if amount > 0 : return [ - 1 ] for i , v in enumerate ( ans ): self . cnt [ i ] -= v return ans # Your ATM object will be instantiated and called as such: # obj = ATM() # obj.deposit(banknotesCount) # param_2 = obj.withdraw(amount)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.