Supposedly Trivial math question.
S. Dale Morrey
sdalemorrey at gmail.com
Tue Oct 1 07:27:32 MDT 2013
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
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
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
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.
More information about the PLUG