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