0

As a graduate I went for an interview for a java development role and was doing pretty well in the technical examinations until i came up against this question.

If i was setting up a vending machine which (for simplicity) returned £2 change. How would i produce an implemtation that would list all the possible combinations of £2.

For e.g £1 + £1 , £1 + 50p + 50p, 50p + 50p + 50p + 50p and so on..

How could i list all the different combinations of £2.00 change possible by the vending machine.

I began to write something and this is what ive came up with so far.

Its almost working except can someone help me find out why its not expanding fully. A second pair of eyes will be grateful. And also any ways it can be optimised.

Thanks guys.

 private static void printCoins(int[] tempArray) {

    for (int i = 0; i < tempArray.length - 1; i++){

// to stop my array from printing out any non-denominator coins e.g  
    if (tempArray[i] > 0){
 System.out.print(tempArray[i] + ": ");
    }
    System.out.println("\n");
  }
}


public static void vendingMachine() {
    int[] denominations = {200,100, 50, 20, 10, 5, 2, 1};
    int[] tempArray = new int[50]; //combination of coins made
    int total = 200;
    int coinCombiIndex = 0, denomCoinIndex = 0;

    // whilst all denominations havent been visited
 while (denomCoinIndex < denominations.length)

     // if i have the correct change
    if (total - denominations[denomCoinIndex] == 0){
        tempArray[coinCombiIndex] = denominations[denomCoinIndex];

        denomCoinIndex++;  //increment so that next iteration starts with lower denom
        printCoins(tempArray); // return coins
    }

 // checks to see whether new total minus coin (denominator) is still >= 0
      else if (total - denominations[denomCoinIndex] >= 0) {

            // if so SUBTRACT from total and ADD coin to coin-combination-array
            total = total - denominations[denomCoinIndex];
            tempArray[coinCombiIndex] = denominations[denomCoinIndex];
            coinCombiIndex++;

            }
        else {
        denomCoinIndex++;

    }

    //  printCoins(tempArray);

}

my output

200: 

100: 100: 

100: 50: 50: 

100: 50: 20: 20: 10: 

100: 50: 20: 20: 5: 5: 

100: 50: 20: 20: 5: 2: 2: 1:
L-Samuels
  • 2,712
  • 9
  • 34
  • 42
  • 1
    duplicate of http://stackoverflow.com/questions/1106929/find-all-combinations-of-coins-when-given-some-dollar-value – toto2 Aug 15 '11 at 15:48
  • 1
    The link above is so popular that it's been made a community wiki. I guess it's a common interview question. – toto2 Aug 15 '11 at 16:23
  • The question is very popular, if you do a little bit of research about dynamic programming you will find it discussed at length. – Savino Sguera Aug 15 '11 at 18:05
  • Consider moving to (http://codereview.stackexchange.com/)... – maerics Aug 17 '11 at 13:21

6 Answers6

1

Probably get started on looking at Dynamic programming. However you could any approach problem for that matter trivially. How would you do that manually ??. Jot down the steps. Convert it into an algorithm yourself. Probably studying Permutations & Combinations would help for better understanding of the problem you have stated.

Hope it helps.

panzerschreck
  • 3,582
  • 2
  • 20
  • 29
1

Let say your possible coins are x1 ...xn :

if you're asked to print all the possiblities for $2 then you could print recursively all the possibilities for :

2-x1
2-x2
..
2-xn

Yoou will eventually get all the solutions

You can initialise this recursive process with amount-xi = 0 then print

Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63
  • could you take a look at my code and tell me why the coin combinations is stopping where it is. Ive edited the original question to include what ive coded so far. Thanks – L-Samuels Aug 16 '11 at 11:26
  • @Lawrence88, ok I will try to have a look at it today – Ricky Bobby Aug 16 '11 at 12:12
  • 1
    @Lawrence88, it's because you when you find one result you then try with the first lower that works, not all the possible lower element. That's why you always have in your solutions 200 then 100 then 50 etc you never have 100 then 2 then . – Ricky Bobby Aug 16 '11 at 12:29
  • im not quite sure i get what you mean Ricky could you elaborate a lil more for me please. – L-Samuels Aug 17 '11 at 12:04
  • @Lawrence88 I added an answer to answer your second question – Ricky Bobby Aug 17 '11 at 13:12
1

To answer your second question:

Try with only {20,10} you will see that your program is really not right .

You tried to transform my recurence into a loop, and I guess it's the best solution. But it's very difficult to do that in one loop (you're missing a lot of possibilities).

You can try to reinialise the while loop with different constraint at each step for example adding a new while loop around your loop like this one 

while (i<denominations.length){
             total=200;
             denomCoinIndex=i;
             tempArray = new int[1000]; 
             i++;

but it's still not enough ... so you will need to add some loop again until you treat all the cases.

I don't think your approach with a while loop is the good one here.

The easiest way would be to use for loop like this to treat all the possible solutions (from the similar question to your question):

 int total = 200;

               System.out. printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);

                int combos = 0;

                for (int q = 0; q <= total / 25; q++)
                {
                    int total_less_q = total - q * 25;
                    for (int d = 0; d <= total_less_q / 10; d++)
                    {
                        int total_less_q_d = total_less_q - d * 10;
                        for (int n = 0; n <= total_less_q_d / 5; n++)
                        {
                            int p = total_less_q_d - n * 5;
                            System.out.printf("%d\t%d\t%d\t%d\n", q, d, n, p);
                            combos++;
                        }
                    }
                }

                System.out.printf("%d combinations\n", combos);

Hope it helps

Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63
0
public class VendeningMachine
{
    public static final int[] coins = {1, 5, 10, 25};
    public static final int[] coinMax = {200, 40, 20, 8};
    public static final int[] coinsString = { "Penny", "Nickle", "Dime", "Quarter"};

    public static void main(String[] args)
    {

    }


    public static void vendingMachine()
    {
        for ( int a = 0; a <= coinMax[0]; a++ ) {
            for ( int b = 0; b <= coinMax[1]; b++ ) {
                for ( int c = 0; c < coinMax[2]; c++ ) {
                    for ( int d = 0; d < coinMax[3]; d++ ) {
                        checkCoins(a, b, c, d);
                    }
                }
            }
        }
    }

    public static void checkCoins(int penny, int nickle, int dime, int quarter)
    {
        int total = coins[0] * penny + coins[1] * nickle + coins[2] * dime + coins[3] * quarter;

        if ( total == 200 )
            printCoins(penny, nickle, dime, quarter);

    }

    public static void printCoins(int penny, int nickle, int dime, int quarter)
    {
        System.out.println("Penney : " + penny + " Nickle: " + nickle + " Dime: " + dime + " Quarter: " + quarter);
    }

}enter code here
user3499861
  • 1
0

Reframe the problem as follows: Given a standard (modern) car odometer that registers 6 digits with no fractions, find all possible values where the sum of the digits is some value, say 15. If you can solve that, you can solve the given problem.

Jim Garrison
  • 85,615
  • 20
  • 155
  • 190
0

Algorithm F on (in-text) page 7 is exactly what you're looking for. :)

http://www-cs-staff.stanford.edu/~uno/fasc3a.ps.gz

Rag
  • 6,405
  • 2
  • 31
  • 38