ATM problem using collections
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&lt;Integer&gt; denominations = new TreeSet&lt;Integer&gt;(notes.keySet());
Integer start = denominations.floor(amt);
denominations = denominations.headSet(start, true);
Iterator&lt;Integer&gt; 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.