Design an ATM Machine - Practice Coding Problems

Design an ATM Machine - Problem

Design an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. Users can deposit or withdraw money.

When withdrawing, the machine prioritizes using banknotes of larger values first.

Example: To withdraw $300 with available notes: 2×$50, 1×$100, 1×$200, the machine uses the $100 and $200 notes.

Important: If withdrawal cannot be completed using the greedy approach (largest first), the request is rejected. The machine does NOT try alternative combinations.

Implement the ATM class:

ATM() - Initializes the ATM object
void deposit(int[] banknotesCount) - Deposits new banknotes in order [$20, $50, $100, $200, $500]
int[] withdraw(int amount) - Returns array of length 5 with count of each denomination to withdraw, or [-1] if impossible

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"], params = [[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]

› Output: [[0,0,1,0,1], [-1], [0,1,0,1,1]]

💡 Note: Initialize ATM. Deposit: 1×$100, 2×$200, 1×$500. Withdraw $600: use 1×$100 + 1×$500 = $600. Deposit more notes. Try $600 again: impossible with greedy approach. Withdraw $550: use all remaining notes.

Example 2 — Greedy Limitation

$ Input: operations = ["ATM", "deposit", "withdraw"], params = [[], [[1,1,1,1,1]], [300]]

› Output: [[0,0,1,1,0]]

💡 Note: With 1 note of each denomination, withdraw $300: greedy uses 1×$200 + 1×$100 = $300, ignoring the $50 note.

Example 3 — Impossible Withdrawal

$ Input: operations = ["ATM", "deposit", "withdraw"], params = [[], [[0,0,0,2,1]], [150]]

› Output: [[-1]]

💡 Note: Available: 2×$200, 1×$500. To withdraw $150, greedy cannot use any notes (all too large), so returns [-1].

Constraints

1 ≤ banknotesCount.length ≤ 5
0 ≤ banknotesCount[i] ≤ 10⁹
1 ≤ amount ≤ 10⁹
At most 5000 calls to withdraw and deposit

Visualization

Tap to expand

Understanding the Visualization

Initialize

Empty ATM with 5 denomination slots

Deposit

Add banknotes to appropriate slots

Withdraw

Use largest denominations first, return counts or [-1]

Key Takeaway

🎯 Key Insight: Greedy approach matches real ATM behavior - always use largest denominations first

Asked in

A Amazon 35 M Microsoft 28 G Google 22 🍎 Apple 18

The key insight is that ATM machines use a greedy approach - always dispensing the largest denomination first. This matches real-world ATM behavior but may fail when other combinations exist. Best approach is Greedy Algorithm with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Algorithm	O(1)	O(1)	Always use the largest denomination first, following ATM's constraint
Brute Force - Try All Combinations	O(5^max_count)	O(1)	Try every possible combination of banknotes to make the target amount

Greedy Algorithm — Algorithm Steps

Start from largest denomination ($500)
Use maximum possible count without exceeding remaining amount
Move to next smaller denomination
If exact amount reached, return counts; otherwise return [-1]

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Large

Begin with $500 notes, use maximum possible

Next Size

Move to $200, then $100, etc.

Check Exact

Return result if remaining = 0, else [-1]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int denominations[5];
    int count[5];
} ATM;

ATM* createATM() {
    ATM* atm = malloc(sizeof(ATM));
    int denoms[] = {20, 50, 100, 200, 500};
    memcpy(atm->denominations, denoms, sizeof(denoms));
    memset(atm->count, 0, sizeof(atm->count));
    return atm;
}

void deposit(ATM* atm, int* banknotesCount) {
    for (int i = 0; i < 5; i++) {
        atm->count[i] += banknotesCount[i];
    }
}

int* withdraw(ATM* atm, int amount, int* returnSize) {
    int* result = calloc(5, sizeof(int));
    int remaining = amount;
    
    // Start from largest denomination (index 4 = $500)
    for (int i = 4; i >= 0; i--) {
        if (remaining >= atm->denominations[i] && atm->count[i] > 0) {
            // Use as many notes as possible
            int use = atm->count[i] < remaining / atm->denominations[i] ? 
                     atm->count[i] : remaining / atm->denominations[i];
            result[i] = use;
            remaining -= use * atm->denominations[i];
        }
    }
    
    // Check if we can make exact change
    if (remaining == 0) {
        // Update available count
        for (int i = 0; i < 5; i++) {
            atm->count[i] -= result[i];
        }
        *returnSize = 5;
        return result;
    } else {
        free(result);
        result = malloc(sizeof(int));
        result[0] = -1;
        *returnSize = 1;
        return result;
    }
}

int main() {
    printf("[[0,0,1,0,1],[-1]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Fixed loop of 5 denominations, each denomination processed in constant time

✓ Linear Growth

Space Complexity

O(1)

Only using fixed arrays and variables, no additional space

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler