Minimize Points Used Across Multiple Reward Programs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
A customer has several reward programs. Program `i` has at most `balance[i]`
points, and each point is worth `value[i]` integer microdollars. Given a target in
microdollars, return the minimum total number of points whose combined value is at
least the target, or `-1` if the available points cannot cover it.
### Constraints & Assumptions
- There are between 1 and 100 reward programs.
- Balances are nonnegative integers and values are positive integers.
- All inputs and intermediate products stay within 2^53.
- Points are indivisible and each program's balance is a hard upper bound.
### Clarifications
- Overpaying the target is allowed; the primary objective is fewest points.
- Any combination with the minimum point count is acceptable, so return only that count.
- Exchange values are already fixed for the transaction date.
### Examples
```text
target = 168_000_000
balance = [36_000, 12_000, 25_000]
value = [12_000, 9_000, 8_500]
output = 14_000
explanation: 14,000 points at 12,000 microdollars each reach the target.
```
### Hints
```hint Compare point values
Every point has the same objective cost of one, so consider whether using higher-value points first can ever hurt the minimum count.
```
```hint Respect finite balances
Consume the most valuable available points in bounded groups and detect any remaining uncovered target.
```
Overview: Minimize the number of indivisible reward points needed to meet or exceed a microdollar target across programs with different values and finite balances, returning failure when coverage is impossible.
Read the full Amazon Software Engineer interview experience this question came from
A customer has several reward programs. Program i supplies at most balance[i] indivisible points, and each of those points is worth value[i] integer microdollars. Given a nonnegative target in microdollars, return the minimum total number of points whose combined value is at least the target, or -1 if all available points together cannot cover it. Overpaying is allowed, exchange values are fixed, and return only the minimum count.
Constraints
- 1 <= len(balance) = len(value) <= 100.
- The target and balances are nonnegative integers, and point values are positive integers.
- Each program's balance is a hard upper bound and points are indivisible.
- All inputs, products, totals, and answers stay within 2^53; use signed 64-bit integers in Java and C++.
Examples
Input: (168000000, [36000, 12000, 25000], [12000, 9000, 8500])
Expected Output: 14000
Explanation: This is the source example; 14,000 points at the highest value exactly reach the target.
Input: (0, [5, 10], [7, 3])
Expected Output: 0
Explanation: A zero target needs no points.
Hints
- Since every selected point costs one in the objective, compare programs by value per point.
- Consume higher-value points in bounded groups and report -1 if value remains uncovered after all groups.