Here's my attempt w/o any real fancy base2 stuff. http://pastebin.com/nSd3h5qH
On Tue, Oct 1, 2013 at 7:27 AM, S. Dale Morrey <[email protected]> wrote: > 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. > */ /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
