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.
$300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.$600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote.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 length 5 of 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 <= 1095000 calls in total will be made to withdraw and deposit.withdraw and deposit.banknotesCount[i] in all deposits doesn't exceed 109When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
For designing an ATM, a brute force approach means we try all possible combinations of bills to dispense until we find one that matches the requested amount. It's like rummaging through all your cash until you find the right combination. This approach focuses on direct computation without any smart optimizations.
Here's how the algorithm would work step-by-step:
class ATM:
DENOMINATIONS = (20, 50, 100, 200, 500)
def __init__(self):
# Number of banknotes currently held for each denomination.
self.banknote_counts = [0] * len(self.DENOMINATIONS)
def deposit(self, banknotes_count):
for index, count in enumerate(banknotes_count):
self.banknote_counts[index] += count
def withdraw(self, amount):
banknotes_to_give = [0] * len(self.DENOMINATIONS)
remaining_amount = amount
# Greedily use the largest denominations first.
for index in reversed(range(len(self.DENOMINATIONS))):
denomination = self.DENOMINATIONS[index]
banknotes_to_give[index] = min(
self.banknote_counts[index], remaining_amount // denomination
)
remaining_amount -= banknotes_to_give[index] * denomination
# The greedy choice is exact, so a leftover means the amount cannot be paid.
if remaining_amount != 0:
return [-1]
for index, count in enumerate(banknotes_to_give):
self.banknote_counts[index] -= count
return banknotes_to_give
Designing an ATM involves breaking down the complex process into smaller, manageable actions. We need to think about the ATM's functionalities like dispensing cash, checking balances, and handling transactions, and how they interact with the user and the bank's system.
Here's how the algorithm would work step-by-step:
class ATMMachine:
def __init__(self, initial_balance=0):
self.account_balance = initial_balance
self.transaction_log = []
def check_balance(self, pin_number):
if self._verify_pin(pin_number):
return self.account_balance
else:
return "Incorrect PIN."
def deposit(self, amount, pin_number):
if self._verify_pin(pin_number):
if amount > 0:
self.account_balance += amount
self.transaction_log.append(f"Deposit: +${amount}")
return f"Deposited ${amount}. New balance: ${self.account_balance}"
else:
return "Invalid deposit amount."
else:
return "Incorrect PIN."
def withdraw(self, amount, pin_number):
if self._verify_pin(pin_number):
if amount > 0 and amount <= self.account_balance:
self.account_balance -= amount
self.transaction_log.append(f"Withdrawal: -${amount}")
# Must update transaction log before returning new balance
return f"Withdrew ${amount}. New balance: ${self.account_balance}"
elif amount <= 0:
return "Invalid withdrawal amount."
else:
# Insufficient Funds
return "Insufficient funds."
else:
return "Incorrect PIN."
def _verify_pin(self, entered_pin):
correct_pin = "1234"
return entered_pin == correct_pin
def get_transaction_log(self):
return self.transaction_log
# Example Usage
atm = ATMMachine(100)
print(atm.check_balance("1234"))
print(atm.deposit(50, "1234"))
# Must implement pin verification
print(atm.withdraw(20, "1234"))
print(atm.check_balance("1234"))
print(atm.get_transaction_log())| Case | How to Handle |
|---|---|
| Initial banknotesCounts is null or empty | Initialize the ATM with zero counts for all denominations. |
| Withdraw amount is zero | Return an array of zeros representing no banknotes withdrawn. |
| Withdraw amount is negative | Return [-1] indicating an invalid withdrawal request. |
| Withdraw amount is larger than the total amount in the ATM | Return [-1] indicating insufficient funds. |
| Withdraw amount cannot be formed by any combination of banknotes | Return [-1] indicating no valid withdrawal combination. |
| Large withdraw amount requiring a large number of calculations | The greedy algorithm minimizes banknotes used but could become slow; consider optimizations if performance is critical. |
| Integer overflow when calculating total amount in the ATM or intermediate values during withdraw | Use appropriate data types (e.g., long) to prevent integer overflow. |
| Deposit of a single, very large number of banknotes | The deposit method should correctly handle adding a large number of banknotes to the existing counts. |