Making Change (Practice Interview Question)

You only have 3 free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You're in!

Your quirky boss collects rare, old coins...

They found out you're a programmer and asked you to solve something they've been wondering for a long time.

Write a method that, given:

an amount of money
an array of coin denominations

computes the number of ways to make the amount of money with coins of the available denominations.

Example: for amount= $4$ ( $4$ ¢) and denominations= $[1,2,3]$ ( $1$ ¢, $2$ ¢ and $3$ ¢), your program would output $4$ —the number of ways to make $4$ ¢ with those denominations:

1¢, 1¢, 1¢, 1¢
1¢, 1¢, 2¢
1¢, 3¢
2¢, 2¢

Gotchas

What if there's no way to make the amount with the denominations? Does your method have reasonable behavior?

We can do this in $O(n*m)$ time and $O(n)$ space, where $n$ is the amount of money and $m$ is the number of denominations.

A simple recursive approach works, but you'll find that your method gets called more than once with the same inputs. We can do better.

We could avoid the duplicate method calls by memoizing, ↴

Memoization ensures that a method doesn't run for the same inputs more than once by keeping a record of the results for the given inputs (usually in a hash map).

For example, a simple recursive method for computing the $n$ th Fibonacci number:

  public static int fib(int n) {

    if (n < 0) {
        throw new IllegalArgumentException(
            "Index was negative. No such thing as a negative index in a series.");
    }

    // base cases
    if (n == 0 || n == 1) {
        return n;
    }

    System.out.printf("computing fib(%d)\n", n);
    return fib(n - 1) + fib(n - 2);
}

Will run on the same inputs multiple times:

  // output for fib(5)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
5

We can imagine the recursive calls of this method as a tree, where the two children of a node are the two recursive calls it makes. We can see that the tree quickly branches out of control:

A binary tree showing the recursive calls of calling fib of 5. Every fib of n call calls fib of n minus 1 and fib of n minus 2. So calling fib of 5 calls fib of 4 and fib of 3, which keep calling fib of lower numbers until reaching the base cases fib of 1 or fib of 0.

To avoid the duplicate work caused by the branching, we can wrap the method in a class that stores an instance variable, memo, that maps inputs to outputs. Then we simply

check memo to see if we can avoid computing the answer for any given input, and
save the results of any calculations to memo.

  import java.util.Map;
import java.util.HashMap;

class Fibber {

    private Map<Integer, Integer> memo = new HashMap<>();

    public int fib(int n) {

        if (n < 0) {
            throw new IllegalArgumentException(
                "Index was negative. No such thing as a negative index in a series.");

        // base cases
        } else if (n == 0 || n == 1) {
            return n;
        }

        // see if we've already calculated this
        if (memo.containsKey(n)) {
            System.out.printf("grabbing memo[%d]\n", n);
            return memo.get(n);
        }

        System.out.printf("computing fib(%d)\n", n);
        int result = fib(n - 1) + fib(n - 2);

        // memoize
        memo.put(n, result);

        return result;
    }
}

We save a bunch of calls by checking the memo:

  // output of new Fibber().fib(5)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
grabbing memo[2]
grabbing memo[3]
5

Now in our recurrence tree, no node appears more than twice:

A binary tree showing the memos and recursive calls of calling fib of 5. Starting with the calls for fib of n minus 1, fib of 5 calls fib of 4, which calls fib of 3, which calls fib of 2, which calls fib of 1. then, for the fib of n minus 2 calls, fib of 5 gets the memo fib of 3, fib of 4 gets the memo fib of 2, fib of 3 gets the memo fib of 1, and fib of 2 calls fib of 0.

Memoization is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with the Fibonacci problem, above). The other common strategy for dynamic programming problems is going bottom-up, which is usually cleaner and often more efficient.

but there's a cleaner bottom-up ↴

Going bottom-up is a way to avoid recursion, saving the memory cost that recursion incurs when it builds up the call stack.

Put simply, a bottom-up algorithm "starts from the beginning," while a recursive algorithm often "starts from the end and works backwards."

For example, if we wanted to multiply all the numbers in the range $1..n$ , we could use this cute, top-down, recursive one-liner:

  public static int product1ToN(int n) {
    // we assume n >= 1
    return (n > 1) ? (n * product1ToN(n-1)) : 1;
}

This approach has a problem: it builds up a call stack of size $O(n)$ , which makes our total memory cost $O(n)$ . This makes it vulnerable to a stack overflow error, where the call stack gets too big and runs out of space.

To avoid this, we can instead go bottom-up:

  public static int product1ToN(int n) {
    // we assume n >= 1

    int result = 1;
    for (int num = 1; num <= n; num++) {
        result *= num;
    }

    return result;
}

This approach uses $O(1)$ space ( $O(n)$ time).

Some compilers and interpreters will do what's called tail call optimization (TCO), where it can optimize some recursive methods to avoid building up a tall call stack. Python and Java decidedly do not use TCO. Some Ruby implementations do, but most don't. Some C implementations do, and the JavaScript spec recently allowed TCO. Scheme is one of the few languages that guarantee TCO in all implementations. In general, best not to assume your compiler/interpreter will do this work for you.

Going bottom-up is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with multiplying the numbers $1..n$ , above). The other common strategy for dynamic programming problems is memoization.

approach.

Breakdown

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Solution

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Complexity

$O(n*m)$ time and $O(n)$ additional space, where $n$ is the amount of money and $m$ is the number of potential denominations.

What We Learned

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Do you have an answer?

Show answer

I have an answer Tell me more

Ready for more?

Check out our full course

You only have 3 free questions left (including this one).

Gotchas

Breakdown

Start your free trial!

Solution

Start your free trial!

Complexity

What We Learned

Start your free trial!

Ready for more?

Programming interview questions by company:

Programming interview questions by topic: