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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design an ATM Machine

Number: 2352

Difficulty: Medium

Paid? No

Companies: Yandex, Google

Problem Description

Design and implement an ATM machine that supports depositing and withdrawing money using five banknote denominations ($20, $50, $100, $200, and $500). The ATM begins empty and allows deposits of banknotes in the fixed order. For withdrawals, the ATM follows a greedy strategy: it always attempts to use as many larger denomination banknotes as possible (in the strict ordering from highest to lowest) before attempting smaller ones. If the requested withdrawal amount cannot be exactly provided by following this strict greedy ordering, the request is rejected (no banknotes are dispensed).

Key Insights

  • The ATM only holds banknotes in 5 fixed denominations.
  • Depositing updates the count of banknotes directly.
  • Withdrawing uses a greedy approach by iterating over the banknotes in descending order.
  • If after using as many as possible from each denomination the requested amount is not met exactly, the transaction is canceled.
  • The strict ordering for withdrawal means that even if an alternative combination exists, it must follow the descent order (largest first).

Space and Time Complexity

Time Complexity: O(1) per deposit/withdraw operation (constant number of denominations to process)
Space Complexity: O(1) (only fixed arrays for denominations and counts are used)

Solution

We maintain an internal array to store the count of banknotes for denominations $20, $50, $100, $200, and $500. For deposits, we simply update these counts. For withdrawals, we simulate the withdrawal process using a greedy approach: starting from $500 and moving downwards to $20, we determine the maximum number of banknotes we can use for each denomination without exceeding both the needed amount and what is available. If the entire amount is matched exactly, we update the internal state by deducting the used banknotes; otherwise, we leave the internal state unchanged and return [-1]. This ensures that no withdrawal is partially processed.

Code Solutions

class ATM:
    # Define the banknote denominations in fixed order.
    def __init__(self):
        # counts for [20, 50, 100, 200, 500]
        self.counts = [0] * 5
        self.denominations = [20, 50, 100, 200, 500]

    def deposit(self, banknotesCount):
        # Add deposited banknotes to ATM's counts.
        for i in range(5):
            self.counts[i] += banknotesCount[i]

    def withdraw(self, amount):
        # Create a temporary array to store the number of banknotes used for each denomination.
        used = [0] * 5
        remaining = amount
        
        # Process in descending order of denominations (largest first).
        for i in range(4, -1, -1):
            if remaining <= 0:
                break
            # Maximum banknotes we can use for this denomination.
            needed = remaining // self.denominations[i]
            # Use only the number available in the ATM.
            use = min(needed, self.counts[i])
            used[i] = use
            remaining -= use * self.denominations[i]
        
        # If we couldn't match the exact withdrawal amount, return [-1]
        if remaining != 0:
            return [-1]
        
        # Otherwise, update the ATM counts by deducting the used banknotes.
        for i in range(5):
            self.counts[i] -= used[i]
        
        return used

# Example usage:
# atm = ATM()
# atm.deposit([0,0,1,2,1])
# print(atm.withdraw(600))  # Expected output [0,0,1,0,1]
← Back to All Questions