the world of coin change problems

Amazon
sde2

Go to company page Amazon

sde2
Nov 11, 2017 4 Comments

a very popular interview question in fb and others with many variations
given a set of denominations (infinite supply) and total amount in cents
1.is it possible to make change
2. number of ways to make change
3. minimum number of coins to make change
4. ways to make change order does not matter
5. ways to make change order matters

repeat above where supply for each denomination is provided.

extension is to do memoization

is there one skeleton that is optimal for one or more of these, any that should be avoided? while I know how to solve each of them I end up choosing the not optimal/suitable approach at times and especially when I get to memoization for 4 and 5..

popular skeletons

1. sort denominations descending and use 0/1 coin per recursion ( no loop in method)
2. sort descending use 1 to as many you can of denomination per recursion (loop in method)
3. recursion returns solution for sub problem ( create a new set of results by cloning sub result and add the current level selection)
4 solution Witten out to passed in object at end of recursion (leaf node).. can you even do memoization here?
5 don't sort

what if given actual pieces of coins, do you convert to denominations and quantities or deal with dups later?

FML...

comments

Want to comment? LOG IN or SIGN UP
TOP 4 Comments
  • Tableau
    tabloid

    Go to company page Tableau

    tabloid
    There's provably no single best algorithm for making change, since some sets of denominations allow a fast greedy algorithm and others don't. Jeffrey Shallit has a few papers on this topic which are approachable.
    Nov 11, 2017 2
  • Amazon / Eng
    CygnusX1

    Go to company page Amazon Eng

    CygnusX1
    The skeletons all sound like implementations of the nature of DP problems, that there is optimal substructure and recurring subproblems. You don't need to sort to perform method 1 and 2 if I understood them correctly, for example. But really the point is identifying the structure of the problem. Also problems 4 and 5 are not optimization problems, just allocations which means simple recursion works.
    Nov 12, 2017 0