The task of the cashier-developer

This task was given during the interviews at Apple. Imagine you got a job as a cashier in a store. Your boss accidentally found out that you have the development skills, and wanted you to help him create an application.

Input data:

• A specified amount of money.

• An array with all available coins’ denominations.

You need to create a function that, at the output, will give the number of all possible ways to get the specified amount of money using the various available coin values. For example, if you need to get 4 cents from coins of nominals of 1, 2 and 3 cents, then the function will return 4 – just as many possible combinations of the numbers 1, 2 and 3 to get in the amount of 4:

1, 1, 1, 1.

1, 1, 2.

1, 3.

2, 2.

Solution

We use dynamic programming to create an ways_of_doing_n_cents array in such a way that ways_of_doing_n_cents[k] contains the number of ways to collect the sum k using the available nominals. To begin with, let’s start with the lack of nominals, having only one option – collect the amount 0. Then, we will add one nominal in ascending order and simultaneously edit our array considering our new nominals.

The number of new options that we can make the higher_amount from with the new coin nominal can be calculated as the existing ways_of_doing_n_cents [higher_amount – coin] value. At this stage, we know all the combinations with the previous nominals, so we use this information when adding a new nominal. When adding the first nominal, we consider that the previous nominal is equal to 0.

Python solution code:

def change_possibilities_bottom_up(amount, denominations):

    ways_of_doing_n_cents = [0] * (amount + 1)

    ways_of_doing_n_cents[0] = 1

    for coin in denominations:

        for higher_amount in xrange(coin, amount + 1):

            higher_amount_remainder = higher_amount – coin

            ways_of_doing_n_cents[higher_amount] += ways_of_doing_n_cents[higher_amount_remainder]

    return ways_of_doing_n_cents[amount]

In order to make it more clear, here is the content of ways_of_doing_n_cents as iterations are performed, the sum is 5 and the nominals are 1, 3 and 5:

===========

key:

a = higher_amount

r = higher_amount_remainder

===========

============

for coin = 1:

============

[1, 1, 0, 0, 0, 0]

 r  a

[1, 1, 1, 0, 0, 0]

    r  a

[1, 1, 1, 1, 0, 0]

       r  a

[1, 1, 1, 1, 1, 0]

          r  a

[1, 1, 1, 1, 1, 1]

             r  a

============

for coin = 3:

=============

[1, 1, 1, 2, 1, 1]

 r        a

[1, 1, 1, 2, 2, 1]

    r        a

[1, 1, 1, 2, 2, 2]

       r        a

============

for coin = 5:

=============

[1, 1, 1, 2, 2, 3]

 r              a

final answer: 3

The algorithm complexity is O(n*m) by time and O(n) by memory, where n is a sum, and m  is the number of different nominals.