# ATM problem using collections

Problem statement:

Write a CashWithDrawal function from an ATM which, based on user specified amount, dispenses bank notes. Ensure that the following is taken care of:

• Minimum number of bank notes are dispensed
• Availability of various denominations in the ATM is maintained

Code should support parallel withdrawals (i.e two or more customers can withdraw money simultaneously). Take care of exceptional situations.

public class ATMMachine {
private Map<Integer, Integer> notes;

public ATMMachine(Map<Integer, Integer> notesMap){
notes = notesMap;
}

private boolean isCorrectAmt(int amt){
return amt%10==0 ? true : false;
}

private synchronized void reduceBalance(int denomination, int noToReduce){
int amt = notes.get(denomination);
notes.remove(denomination);
notes.put(denomination, amt-noToReduce);
}

public synchronized Integer getATMBalance(){
int balance = 0;
for(Integer denominator: notes.keySet()){
balance = balance + (denominator * notes.get(denominator));
}
return balance;
}

public synchronized Map<Integer, Integer> withdrawAmt(int amt){
Map<Integer, Integer> returnedMap = new HashMap<Integer, Integer>();

if(!isCorrectAmt(amt)){
System.out.println("Please enter amount in multiple of 10");
return returnedMap;
}

//get sorted denominations
TreeSet<Integer> denominations = new TreeSet<Integer>(notes.keySet());
Iterator<Integer> iter = denominations.descendingIterator();

while(amt > 0 ){
int denomination = iter.next();
int noOfNotes = amt< denomination ? 0 : amt/denomination;
returnedMap.put(denomination, noOfNotes);
amt = amt - (denomination * noOfNotes);
reduceBalance(denomination, noOfNotes);
}
return returnedMap;
}

public static void main(String agrs[]){
Map<Integer, Integer> notesMap = new HashMap<Integer, Integer>();
notesMap.put(500, 10);
notesMap.put(100, 20);
notesMap.put(50, 50);
notesMap.put(10, 30);

ATMMachine atm = new ATMMachine(notesMap);

System.out.println("Current balance is : " + atm.getATMBalance());
System.out.println("withdraw amt 200" + atm.withdrawAmt(800));
System.out.println("balance after withdrawing " + atm.getATMBalance());

ATMUser user = new ATMUser(atm, 4000);
}
}

public class ATMUser implements Runnable {

ATMMachine atm;
int amtToWithdraw;

public ATMUser(ATMMachine atm, int amtToWithdraw){
this.atm = atm;
this.amtToWithdraw = amtToWithdraw;
}

@Override
public void run() {
System.out.println("Balance in ATM is " + atm.getATMBalance());
System.out.println("withdrawin  amt : " + amtToWithdraw);
System.out.println("withdrawn : " + atm.withdrawAmt(amtToWithdraw));
System.out.println("Balance after withdraw is : " + atm.getATMBalance());
}
}

• ATM stands for Automatic Teller Machine, so your class is called Automatic Teller Machine Machine? – Adam Sep 23 '12 at 6:52

First of all, it's considered better practice to implement isCorrectAmount as follows:

private boolean isCorrectAmt(int amt){
return amt%10 == 0;
}


Next, if you want to update the value of an existing key in a Map, it's not necessary to remove the mapping for the key and then reinsert it. You can just call put, and if the map already contains a mapping for the key it will simply update the key's value. So with that in mind, I would suggest changing the body of reduceBalance as follows:

private synchronized void reduceBalance(int denomination, int noToReduce){
int amt = notes.get(denomination);
notes.put(denomination, amt-noToReduce);
}


The next thing I thought about questioning was your choice of a TreeSet for maintaining an order collection of denominations. Normally you should collect items in a List if you are interested in keeping them in order, and use a Set if you want to stop your collection from containing duplicates. TreeSet just happens to be a collection implementation that offers both features. Overall however I think using TreeSet here allows you to achieve your goal in as little code as possible, so in the end this is fine by me.

By using a TreeSet, one thing you could do is use the advanced methods on its API to fast-forward through the denominations that are greater than your amount. This is probably not really worth doing as the gains are minimal, and I must stress that I haven't tested this out, but you could conceivably do this:

//get sorted denominations
TreeSet<Integer> denominations = new TreeSet<Integer>(notes.keySet());
Integer start = denominations.floor(amt);
Iterator<Integer> iter = denominations.descendingIterator();


Your main issues in terms of the functional correctness of your code are:

• withdrawAmt needs to perform more validation on its input. As well as checking that the input is a multiple of 10, it needs to check that it is non-negative and also less than or equal to the total amount in the machine.
• Your while loop in withdrawAmt needs to account for the situation where there are not enough notes in the machine to pay out the requested amount. What if somebody wants to withdraw $30 but there are only 2$10 notes left? Think about what your code currently does in this situation.

Finally, by making the main entry point into the ATMMachine class synchronized (as well as most of the other methods), concurrent requests to withdraw money will pretty much proceed in series, one after the other. In all fairness this may have to be the case. One of the first things that the machine needs to check is that it has enough cash to service the current user, and it can't establish this for sure if there's another user currently in the middle of a withdrawal.

Nevertheless, given that your focus is on Java's collections, it may be worth looking at the concurrent collection classes and seeing if making notes a ConcurrentHashMap might allow you to perform some actions in parallel. I'll have a look myself and update this answer if I can propose some code that would result in less blocking.

• Thanks Avik for the review comments. I will try to rework on the problem using concurrent classes. – mehta Oct 8 '12 at 5:41

I'm going to mention some nitpicks, as they leap out at me as I read the code:

• isCorrectAmt() does not check if the amount is correct. It checks if it is a valid amount. There's only one correct amount but many possible valid amounts.

• isCorrectAmt() hardcodes a rule as to what is valid. This will make localization harder. It's generally better to get this from configuration. Note that in this case, the 10 is also the smallest denomination. So you might consider having the function check against the smallest denomination rather than a separate value. Of course, that would fail if the smallest denomination were a 2 and the next smallest a 5. But your code doesn't really work in that situation anyway. There's an implicit assumption that you can always grab as much of the largest denomination as you can. I.e. that large denominations are multiples of smaller denominations.

• In my opinion, you use abbreviations more than is necessary. For example, amt rather than amount. This is especially bad here because you have both amt and atm.

• In reduceBalance(), you use amt to refer to a quantity of notes. Elsewhere you use it to represent a currency amount. It's often better to stick with a single definition of a variable name.

• In getATMBalance(), you use denominator where elsewhere you use denomination. I found this distracting, as denominator is also the bottom part of a fraction. Using denomination here would make it more obvious that you are iterating over the same set as elsewhere.

• withdrawAmt() returns a Map of denominations and quantities. Why? You don't seem to use it for anything.

• In withdrawAmt(), you name a variable returnedMap, but that doesn't seem to describe what it is. It is the map that you will return, not the one that has been returned. It's also not descriptive. I might go with withdrawalDenominationQuantities or just quantitiesOfDenominations or even just quantitiesOf.

• withdrawAmt() should probably throw exceptions when there's a problem. For example, if there isn't enough money to support a particular withdrawal.

• In withdrawAmt(), you name an Iterator as iter. Generally it is better to use a descriptive name if possible. In this case, I would suggest nextDenomination.

• In withdrawAmt(), do you need to put denominations with quantities of 0 in the map to return? Currently it puts a 0 only for large denominations. Once the withdrawal amount is reached, it stops adding them. This gives two ways to get a zero quantity: an explicit value of 0 or a missing entry. Why not pick one? You could iterate over all the denominations if you want 0s, or you could continue when you encounter a denomination that doesn't fit.

That is:

if ( amt < denomination ) {
continue;
}

• The map that you return would make more sense if you were generating the denominations to withdraw in one function and then actually withdrawing them in a different function. That would also allow you to handle problems more cleanly. In particular, you could reject a withdrawal that can't be fulfilled in total. Currently, you do a partial withdrawal, which is not the normal behavior.

This would allow you to have a processWithdrawalRequest() which would call other functions to check if the withdrawal amount is valid, generate a list of denomination quantities to withdraw, actually do the withdrawal, and give the money to the user. Currently your withdrawAmt() function tries to do some of these itself. It would be better if the function that tried to do multiple things would delegate while the acting functions would each do only one thing. This will also make it easier to unit test, as the acting functions are only doing single units of work.

• In System.out.println("withdraw amt 200" + atm.withdrawAmt(800)); you have two different numbers. If you write this as something like

System.out.println("withdraw amt " + withdrawalAmount + ":  " + atm.withdrawAmt(withdrawalAmount));


you might find it easier to keep these consistent.

• In general, you could use a test class that you could initialize with the appropriate balances, withdrawal amounts, etc. You're currently doing this directly in main(), which leads to having to edit code in several places when you want to change your test.