What is the efficient way to implement universal ATM algorithm?

Question

Last week I attended interview where I was asked to write code for universal ATM algorithm.

So I had to implement function ATM that takes all available banknotes with their limits and desired amount of money and returns any possible way to combine this amount of money from given banknotes and their limits.

The 1st iteration of ATM function implementation was quite simple, because limits looked like

{
    1000: 20,
    500: 430,
    100: 300,
    50: 23,
    10: 23
}

But in the last iteration of task limits looked like

{
    1000: 20,
    500: 430,
    100: 300,
    50: 23,
    30: 23
}

I suppose, I succeed to implement working version of this algorithm, but I am unhappy with its final complexity and I feel there should be something much more efficient.

My decision is following:

1. Creating all possible subsets for given currencies, so [100, 50, 30] set will be converted into 7 subsets: [[100], [50], [30], [100, 50], [100, 30], [50, 30], [100, 50, 30]].

2. Try to form needed amount within each subset, so if I have to deal with 180 amount I'll try to form this amount

   • only with 100 banknotes, this attempt fails
   • only with 50 banknotes, this attempt fails
   • only with 30 banknotes, this attempt succeeds with result like {30: 6}
   • with 50 and 30 banknotes, this attempt succeeds with result like {50: 3, 30: 1}
   • with 100 and 50 banknotes, this attempt fails
   • with 100 and 30 banknotes, this attempt fails
   • with 100, 50 and 30 banknotes, this attempt succeeds with result like {100: 1, 50: 1, 30: 1}

3. Select from successful variants any I like and return it as a result.

The working code for my decision in JavaScript is below:

function getAllSubsetsInSet(set) {
    const result = [];
    let mask = 1;

    do {
        let maskString = mask.toString(2).padStart(set.length, '0');
        result.push(set.filter((item, index) => maskString[index] === '1'));
        mask++;
    }while (mask < (2 ** set.length));

    return result;
}

function getMoney(currencies, limits, amount) {
    const sorted = currencies.sort((a, b) => b - a);

    let workingLimits = {
        ...limits
    };
    let workingAmount = amount;
    let result = {};

    for (let i = 0; i < sorted.length; i++) {
        let currentCurrency = sorted[i];
        let desiredBanknotes = Math.floor(workingAmount / currentCurrency);
        let availableBanknotes = workingLimits[currentCurrency];
        let banknotesToBeUsed = (availableBanknotes < desiredBanknotes) ? availableBanknotes : desiredBanknotes;

        workingAmount = (workingAmount - (banknotesToBeUsed * currentCurrency));
        workingLimits[currentCurrency] = availableBanknotes - banknotesToBeUsed;
        result[currentCurrency] = banknotesToBeUsed;
    }

    if (workingAmount > 0) {
        return {
            result: {},
            limits,
            error: true
        }
    }

    return {
        result: result,
        limits: workingLimits,
        error: false
    }
}

function ATM(limits, amount) {
    let currencies = Object.keys(limits).map(item => Number(item));
    let allCurrencyCombinations = getAllSubsetsInSet(currencies);
    let resultsForEachCombination = allCurrencyCombinations.map(combination => {
        return getMoney(combination, limits, amount);
    });

    const succeedResults = resultsForEachCombination.filter(variant => !variant.error);
    if (succeedResults.length) {
        return succeedResults;
    }

    return {
        result: 'No possible ways',
        limits
    }
}

console.log(ATM(
    {
        1000: 20,
        500: 430,
        100: 300,
        50: 23,
        30: 90
    },
    180
));

But please, could anyone help me with the right and eficient way to implement this logic? Any programing language and pseudocode would be OK.

Thank you!

Answer 1

There is something much more efficient. Just write a recursive algorithm that tries the greedy thing of as many large bank notes as you can first. If there is an answer, it will normally be found very fast. But failure will be slow.

In an interview I'd just give that answer with the performance note and indicate that I know how to speed it up if need be.

If they ask how to speed it up, you first look for any opportunity to be able to treat large bank notes as small ones because there are enough small ones that divide the large ones to be able to make any multiple of the small. Once you solve the version with fewer denominations, then you can reverse the process in a greedy way to figure out which bills you actually hand out.

In your first case that reduces you to a stack of 10s, and the answer is immediate. No recursion needed.

The second case is more interesting. When you start there are 21 * 431 * 301 * 24 * 24 = 1_569_226_176 possible combinations of notes that you could have to consider. (Note that there is a +1 in each factor because you can have 0 through n. Also note that you can prune the search space to avoid considering a lot of them. But the number will be huge.)

But you can mentally replace 1000 notes with 2 500 notes because you have a 500 note. Then replace 500 notes with 100 notes because you have 4 100 notes. (Note, the divisible -1 is because you don't need to be able to make 500 with 100 notes. Just the values 0, 100, 200, 300 and 400.) And again 100 notes with 50 notes. But then we stop because 30 notes don't divide 50 notes. This turns

{
    1000: 20,
    500: 430,
    100: 300,
    50: 23,
    30: 23
}

into making change out of:

{
    50: 5323,
    30: 23
}

Which is going to be a lot faster because there are fewer combinations to think about. Worst case only 5324 * 24 = 127_776 But it is still not as fast as we can get.

The final performance enhancement is to replace stacks of small bills with a few small bills and stacks of bigger bills. In this case the least common multiple of 30 and 50 is 150. So we can actually treat this as a few stray notes to make the final change, and a whole stack of 150 notes.

{
    150: 178, // 174 from 50s, 4 from 30s
    50: 1,
    30: 3
}

And now we have to do very little work indeed to figure out if we can make change. (The raw possibilities for a simple brute force are down to 179 * 2 * 4 = 1432. If you're slightly clever at this point though, you only have to look at 8 of those.) And once we have change, we just reverse the process to get back to the actual denominations that we had.

And that optimized version of the denominations will always find an answer quickly, from which we can work backwards to find actual bills.