Kearney Taaffe - 26 days ago 11

Python Question

I had an interesting interview question that I'm having a hard time solving (I have 7 of the 10 permutations)

The question was

Find all possible permutations to make change given the following coins, 25¢, 10¢, 5¢. The answer MUST BE saved in a list, and MUST BE returned as a JSON string when the method is called

Furthermore, the requirements were that when printed, the solution MUST look like this

For instance, given an amount of 50¢, the solution should look like

the following when printed out

`25: 2, 10: 0, 5: 0`

25: 1, 10: 1, 5: 3

25: 1, 10: 2, 5: 1

25: 1, 10: 0, 5: 5

25: 0, 10: 5, 5: 0

25: 0, 10: 4, 5: 2

25: 0, 10: 3, 5: 4

25: 0, 10: 2, 5: 6

25: 0, 10: 1, 5: 8

25: 0, 10: 0, 5: 10

Needless to say, after 2 hours (the time limit to the test) I was unable to finish. But, it got me wandering, if I could solve the problem. I've tried for the past 6 hours to get the result, but the best I can come up with is

`1 => {25: 2, 10: 0, 5: 0}`

2 => {25: 1, 10: 1, 5: 3}

3 => {25: 1, 10: 2, 5: 1}

4 => {25: 1, 10: 0, 5: 5}

5 => {25: 0, 10: 5, 5: 0}

6 => {25: 0, 10: 1, 5: 8}

7 => {25: 0, 10: 0, 5: 10}

Using this code

`class ChangeMachine(object):`

def __init__(self, amount, coins=[25, 10, 5]):

self.amount = amount

self.coins = coins

self.result = []

self.initial_way = {}

for coin in coins:

self.initial_way[coin] = 0

def getAllPermutations(self):

for index in xrange(0, len(self.coins)):

coin = self.coins[index]

self.changeFromSameCoin(self.amount, coin)

self.changeUsingOneCoin(self.amount, coin, self.coins[index + 1:])

def changeFromSameCoin(self, amount, coin):

"""loops through all the coins, finding the ones which can be divided

into the amount evenly

Args:

amount: int

coin: int

Returns:

None

"""

way = dict(self.initial_way)

if amount % coin == 0:

way[coin] = amount / coin

self.result.append(dict(way))

def changeUsingOneCoin(self, amount, initial_coin, coin_list):

"""Makes change using 1 large coin and the rest small coins

Args:

amount: int

initial_coin: int - the "large" denomination that is to be used once

coin_list: list - contains the remainder of the coins

"""

if amount <= initial_coin:

return

remainder = amount - initial_coin

init_way = dict(self.initial_way)

num_coins = len(coin_list)

coin_used = 0

outer_counter = 0

# keep track of the number of times the outer coins are used

# make it 1 because the outer coin has to be used at least once

# even if outer coin is > remainder, we are still trying to use

# it once

outer_coin_used = 1

# since the initial coin MUST BE used at least once, go ahead and

# create an initial dictionary that has the initial coin used

# once

init_way[initial_coin] = 1

while outer_counter < num_coins:

outer_coin = coin_list[outer_counter]

# initialize way on every loop

way = dict(init_way)

# subtract the current outer coin from the remainder. We do this

# because if the remainder is 0, then it means that only 1 of this

# coin and the initial coin are needed to make change

# If the remainder is negative, then, one of the larger coin and

# one of this coin, cannot make change

# The final reason is because if we make change with the other

# coins, we need to check if we double, triple, etc this coin

# that we can still make change.

# This helps us find all permutations

remainder -= (outer_coin * outer_coin_used)

if remainder < 0:

# move to next coin using the outer_counter

outer_counter += 1

# reset the remainder to initial - large coin

remainder = amount - initial_coin

# rest the times the coin was used to 1

outer_coin_used = 1

continue

way[outer_coin] += outer_coin_used

if remainder == 0:

# add the way we just found to our result list

self.result.append(dict(way))

# move to the next element in the list

outer_counter += 1

# reset the remainder, our way result set, and times the

# outer coin was used

remainder = amount - initial_coin

way = dict(init_way)

outer_coin_used = 0

continue

# so, if we got here, the outer coin reduced the remainder, but

# didn't get it to 0

for index in range(outer_counter + 1, num_coins):

# our goal here is to make change with as few of coins as

# possible

inner_coin = coin_list[index]

if remainder % inner_coin == 0:

way[inner_coin] = remainder / inner_coin

remainder = 0

break

if remainder - inner_coin < 0:

# this coin is too large, move onto the next coin

continue

# this coin goes into the remainder some odd number of times

# subtract it from our remainder and move onto the next coin

remainder /= inner_coin

way[inner_coin] += remainder

# end for index in range()

if remainder == 0:

# we found a way to make change, save it

self.result.append(dict(way))

# reset the remainder to initial - large coin

remainder = amount - initial_coin

# increment the outer coin used by 1, because we will try

# to decrement remainder by more than 1 outer coin

outer_coin_used += 1

# end while loop

return

# end def changeUsingOneCoin()

# end class

from pprint import pprint

def main(amount, coins=[25, 10, 5]):

result = []

amount = 50

coins = [25, 10, 5]

cm = ChangeMachine(amount, coins)

# cm.changeUsingOneCoin(amount, coins[0], coins[1:])

cm.getAllPermutations()

counter = 1

for record in cm.result:

print "{} => {}".format(counter, record)

counter += 1

return result

if __name__ == '__main__':

"""

Result MUST BE a list of dictionaries containing all possible answers

For Example: if main(50, [25, 10, 5]) should return

[

{25: 2},

{25: 1, 10: 2, 5: 1},

{25: 1, 10: 1, 5: 3},

{25: 1, 10: 0, 5: 5},

{25: 0, 10: 5, 5: 0},

{25: 0, 10: 4, 5: 2},

{25: 0, 10: 3, 5: 4},

{25: 0, 10: 2, 5: 6},

{25: 0, 10: 1, 5: 8},

{25: 0, 10: 0, 5: 10},

]

"""

result = main(50)

I know I'm not going to get the job. But, I really want to know the solution

Answer Source

This simpler code does it, except that it doesn't write the output as JSON.

I would be suspicious of an employer that calls these 'permutations'. :)

```
TOTAL = 50
for q in range(0, 1+50//25):
remainder_q = TOTAL - 25*q
for d in range(0, 1+remainder_q//10):
remainder_d = remainder_q - 10*d
for n in range(0, 1+remainder_d//5):
remainder_n = remainder_d - 5*d
if 25*q+10*d+5*n == 50:
print (q, d, n)
break
if 25*q+10*d+5*n > 50:
break
0 0 10
0 1 8
0 2 6
0 3 4
0 4 2
0 5 0
1 0 5
1 1 3
1 2 1
2 0 0
```