Get Changed for that Interview!

And by “Get Changed”, I mean: “Try to solve these coding challenges that relate to currency and change”. So, open your favorite editor and let’s get started!

Part 1: Make Change

First, let’s assume that we’ve defined our currency as follows:

Coin Value
Quarter 25
Dime 10
Nickel 5
Penny 1

Now, write a function that accepts a non-negative amount of money as an input. This function should tell us a way to make change for that amount of money. Some examples:

Part 2: Make change for real

Did you solve the previous step by just returning a pile of pennies? Shame on you! Go back and rewrite your function so that it returns change using large coins whenever possible!

If your output already looks like mine, then High Five!

High five!

Part 3: Change Everything!

As in: rewrite the function so that it returns all possible ways to create change for a non-negative amount of money. For example:

Part 4: Just change the currency

Phew — part 3 was a bit rough! Let’s do something a bit easier this time…

Revise your function so that it can handle any form of currency. For example, let’s define “Canadian Currency” as the following:

Coin Value
Acorn 7
Bottle Cap 2

With this currency definition, your function should be able to produce outputs such as the following:

Part 5: Short changed

You probably thought that I was going to add more steps to the challenge problem. Well, you’ve been short changed! BOOM!

Okay, fine. Here’s something for you to ponder:

Typically, we try to give people change using as few coins as possible. Obviously, this means that we should prioritize the larger coins over the smaller coins. Why give someone 25 pennies when you could just give them 1 quarter?

But wait — does this greedy algorithm always work? Are there cases where we would end up using fewer coins if we started with a smaller coin first?

Write a function that will always return change using the fewest coins possible. Then, write a function that will return change using the greedy algorithm. Do these functions always return the same result? If not, then why?

Leave a Reply

Your email address will not be published. Required fields are marked *