This was posed to me at an interview and stupidly I got nervous and I choked on it. Now it's been burning in my mind and I'm trying to solve it. It seems simple enough, but for some reason I'm hitting a mental block here.
Imagine you're writing a program for a clerk making change. The currency is purely a single base, i.e. base 10, base 2 etc, but the base is arbitrary. The clerk has to give a customer the exact change to the penny. give change in the following scenario Customer owes $123.45 Customer pays with $1,300. (not a typo and I have no idea why they're overpaying by so much). You must return a single string telling the clerk how many of each denomination to give in any arbitrary integer base. You can assume that the smallest fractional component is a whole unit i.e. 123.45 would be 5 ones, 4 tens, 3 hundreds, 2 thousands and 1 ten thousand. You should not assume any upper limit on individual bill size (ala Zimbabwe dollars). You can assume that the clerk has an infinite supply of each bill, but there are bonus points if the function can cope (i.e. find an alternate output), if there is an insufficient quantity on hand of any particular bill or bills. You do not need to wordize the bills, that is the string can look like... 5-1's, 4-10s, 3-100s etc. instead of 5 ones, 4 tens, 3 hundreds. For expediency you may return the string in high order or low order notation i.e. 3-100s, 4-10s, 5-1s is also acceptable. As a lifeline, you are allowed to simply pick any arbitrary base and restrict your answer to only that base. You can also do it in any language you feel would work best but you may not use any library which is not generally accepted as core to the language you pick. My solution turned into a mess on the whiteboard, long division by hand was never was my strong suit I guess. Looks like in my old age, place value has begun to fall out of my head as well. I believe the correct solution involves finding the high bit and dividing recursively, but something tells me there is a better way. Have Fun! /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
