We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design an ATM Machine

Difficulty: Medium

Problem Description

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. The machine prioritizes using banknotes of larger values when withdrawing. If the machine cannot fulfill a withdrawal request with the available banknotes, it should return [-1].

Key Insights

  • The ATM should prioritize larger denominations for withdrawals.
  • The machine must ensure that it does not partially fulfill a withdrawal request (i.e., if it can't fulfill the entire amount, it shouldn't withdraw anything).
  • The operations must be efficient given the constraints on the number of calls and the range of values.

Space and Time Complexity

Time Complexity: O(1) for both deposit and withdraw operations since they involve a fixed number of banknote types (5). Space Complexity: O(1) as we are only storing a fixed number of banknote counts.

Solution

To solve this problem, we will use an array to represent the count of each banknote denomination. The deposit method will update this array according to the number of banknotes deposited. The withdraw method will attempt to fulfill the withdrawal request starting from the highest denomination down to the lowest. If it cannot fulfill the request in entirety, it will return [-1]. This greedy approach ensures that we always try to use the largest possible banknotes first.

Code Solutions

class ATM:

    def __init__(self):
        # Initialize an array to store the counts of each denomination
        self.banknotes = [0] * 5  # [20, 50, 100, 200, 500]

    def deposit(self, banknotesCount):
        # Update the banknotes based on the deposited counts
        for i in range(5):
            self.banknotes[i] += banknotesCount[i]

    def withdraw(self, amount):
        # Create an array to hold the number of banknotes to withdraw
        withdrawCount = [0] * 5
        
        # Iterate over the banknotes from the largest to the smallest
        for i in range(4, -1, -1):
            # Calculate how many of this denomination we can use
            if amount >= (i + 1) * 20:  # denomination value
                num_notes = min(amount // (i + 1) * 20, self.banknotes[i])
                withdrawCount[i] = num_notes
                amount -= num_notes * (i + 1) * 20
        
        # If there's any amount left, the withdrawal cannot be completed
        if amount > 0:
            return [-1]
        
        # Update the banknotes in the ATM
        for i in range(5):
            self.banknotes[i] -= withdrawCount[i]
        
        return withdrawCount
← Back to All Questions