During technical and coding interviews, the interviewer might ask the candidate to solve a particular problem in order to get some insight into the skills related to problem solving. One such problem is the Cash Register Problem. In this blog post I’m gonna try to explain it and offer an approach for solving it using Java.

Problem explanation

Your cash register contains an amount of money made up of specific amounts of coins or bills. Given the payment of the customer, you must return the change using the coins or bills you have in the cash register and update its state at the end of the transaction. This means that you can’t simply print or return the change, since you must choose how many specific coins or bills to return.

A practical example

I’m gonna assume that we are using Euros, the currency used in Europe. The sum the customer must pay is 25.56€, but he gives us 30.00€, so the change we must return is 4.44€. Our cash register contains the following coins:

We can give away a change made up of two 2.00€ coins, two 0.20€ coins, two 0.02€ coins and update the cash register accordingly.

What if we don’t have enough money?

I will assume that if we don’t have enough coins or money, we will give away a partial change close to the real one and print the remaining difference.

Let’s get into coding

To solve the problem I’m gonna use an HashMap for modelling our cash register. More specifically the keys are floats represeting the coin value and the values are integers representing how many coins of that size we have.
Here’s how the main and some utility functions would look like:

public static void main(String[] args) {
        float price = 25.56f;
        float customerMoney = 30.0f;

        Map<Float, Integer> cash = new HashMap<>();

        //defining the content of our cash register
        cash.put(2.0f, 5);
        cash.put(1.0f, 0);
        cash.put(0.5f, 1);
        cash.put(0.2f, 3);
        cash.put(0.1f, 3);
        cash.put(0.05f, 10);
        cash.put(0.02f, 10);
        cash.put(0.01f, 10);

        //change we must give away, truncated to two decimal places
        float difference = (float) Math.floor((clienteContanti - prezzo)*100) / 100;
        System.out.println("Difference: " + diffCopy);
        //gives away the change updating the cash register
        updateCash(difference, cash);
        printCash(cash);   
}

//returns the total amount of money we have, truncated to two decimal places
public static float sumCash(Map<Float, Integer> cid) {
    return (float) Math.floor(
            cid.entrySet().stream().map(entry -> entry.getKey() * entry.getValue()).reduce(0.0f, Float::sum) * 100)
            / 100;
}

//simply prints the content of the cash register
public static void printCash(Map<Float, Integer> cid)
{
    for (Float key : cid.keySet()) {
        System.out.println(key + ": " + cid.get(key));
    }
}

The main algorithm

If we want to give away the change by using the minimum number of coins, we must iterate through our HashMap keys in descending order. So for each key in our cash register, while the difference between the change we must give away and the key is greater or equal to zero and if we have sufficient coins of that value in the cash register, we will give that coin away by removing it from the cash register and decrement the change. After finishing executing these loops, we update again the difference by truncating to two decimal places and print it; this should be a useful information to know if we don’t have enough money for returning the change.

Here’s how the code would look like:

//return the change by using first the coins with higher values, then it moves to coins with lower values
public static void updateCash(float difference, Map<Float, Integer> cash) {
    float cashTotal = sumCash(cash);

    if(cashTotal < difference)
        System.out.println("Insufficient funds, we will give away a partial change");
    
    //obtaining the list of coins sizes and ordering it in descending order
    List<Float> keys = new ArrayList<>(cash.keySet());
    keys.sort(Collections.reverseOrder());

    //for each coin size, starting from higher values
    for(Float key : keys)
    {
        //while the difference between the change and the chosen coin size is greater or equal than zero and I have coins of that size
        //return part of the change using that coin size and decrement the change
        while (difference - key >= 0 && cash.get(key) > 0) {
            int prevVal = cash.get(key);
            difference -= key;
            cash.put(key, prevVal - 1);
            System.out.println("Coin size chosen: " + key);
        }
    }

    difference = (float) Math.floor(difference * 100) / 100;
    
    System.out.println("Remaining difference: " + difference);
}

The results of the program execution

Here’s how the previously shown algorithm works in our specific example, showing at the end the updated cash register.

Conclusions

We’ve seen one of the methods to tackle the Cash Register Problem, returning the change starting from coins with higher values and then going with coins with lower values in such a way to select the minimum number of coins.

Further improvements can be made by implementing different strategies to use when the coins are not sufficient.

If you like challenges like this one, you may find plenty of them on LeetCode (useful for preparing for coding interviews) or you might be tempted to try the Advent of Code 2022, which however is less focused on common problems found in coding interviews, but it’s still fun and entertaining.