Engaged Employer

Interview Question

Interview Mountain View, CA

Given US denomination coins, what is the algorithm to make

change for any amount?
Tags:
algorithm

0

Greedy algorithm will work in this case

Interview Candidate on Feb 29, 2012
3

Code is in JAVA : public class USCoins { public static void main(String args[]) { int[] coinDenominations = {25,10,5,1}; double totalAmountInDollars = 3.46; int[] numberOfEachCoin = getNumber(coinDenominations,totalAmountInDollars); for(int number : numberOfEachCoin) System.out.println(number); } private static int[] getNumber(int[] coinDenominations, double totalAmountInDollars) { int numberOfEachCoin[] = new int[coinDenominations.length]; int totalAmountInCents = (int) (totalAmountInDollars*100); for(int i=0;i<coinDenominations.length;i++) { int denomination = coinDenominations[i]; numberOfEachCoin[i] = totalAmountInCents/denomination; totalAmountInCents = totalAmountInCents%denomination; } return numberOfEachCoin; } }

someguy on Mar 1, 2012
0

Inspired by this problem, I have proposed a solution that print out all possible change combinations per given amount. I demo the problem solving process in this video: http://www.youtube.com/watch?v=3VBjhiKUtmE

Anonymous on Mar 19, 2012