Interview Question

Anonymous Interview Mountain View, CA

Given US

denomination coins, what is the algorithm to make change for any amount?
Tags:
algorithm
Answer

Interview Answer

3 Answers

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

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up