Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

Interview Cake

You only have 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.

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:

  1. an amount of money
  2. 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¢
  2. 1¢, 1¢, 2¢
  3. 1¢, 3¢
  4. 2¢, 2¢

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

We can do this in time and 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, but there's a cleaner bottom-up approach.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

time and additional space, where n is the amount of money and m is the number of potential denominations.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Reset editor

Powered by qualified.io

. . .