Amazon OA Interview Question: Change Counting System

You’re creating a change counting system for a new automated Amazon cash register that Amazon plans to launch internationally.

Your change counting system should take the amount of change needed plus the types of coins available and return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Desired change: 6¢
Coins Available: [5¢, 3¢]
Result: 2

Example 2:

Desired change: 18¢
Coins Available: [5¢, 3¢]
Result: 4

Example 3:

Desired change: 7¢
Coins Available: [5¢, 3¢]
Result: -1

This is a classic minimum-coin change problem: given a target amount and a set of coin denominations, return the fewest coins needed to make that amount, or -1 if it is impossible. A standard dynamic programming solution works well by letting dp[i] represent the minimum number of coins needed for amount i, then relaxing each state using every coin denomination. The examples illustrate both reachable and unreachable amounts, such as 6 = 3 + 3, 18 needing four coins, and 7 being impossible with coins of 5 and 3.