How should I practice Minimum Reward Points to Cover a Payment?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Minimum Reward Points to Cover a Payment associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Minimum Reward Points to Cover a Payment

Learn this problem

● Medium

AmazonNEW GRADONSITE INTERVIEW

See Amazon hiring insights

Problem statement

You have balances in several reward programs. Program i contains balances[i] whole points, and each of its points is worth valueMicrodollarsPerPoint[i] microdollars.

Given a payment amount targetMicrodollars, return the minimum total number of points whose combined value is at least the target. You may redeem any nonnegative whole number of points from each program, but you may not exceed its balance.

Return -1 when all available points together cannot cover the payment. Overshooting the target is allowed, and only the number of redeemed points is minimized.

Function

minimumRewardPoints(targetMicrodollars: long, balances: int[], valueMicrodollarsPerPoint: long[]) → long

Examples

Example 1

targetMicrodollars = 168000000balances = [36000,12000,25000]valueMicrodollarsPerPoint = [12000,9000,8500]return = 14000

The airline program has the highest value per point. Redeeming 14000 airline points covers exactly 168000000 microdollars, and no set of fewer points can have that much value.

Example 2

targetMicrodollars = 100balances = [1,3]valueMicrodollarsPerPoint = [60,25]return = 3

Use the one point worth 60 and two points worth 25. Their value is 110, so three points cover the target. Two points can be worth at most 85.

Example 3

targetMicrodollars = 101balances = [2]valueMicrodollarsPerPoint = [50]return = -1

Both available points are worth only 100 microdollars in total, so the payment cannot be covered.

Constraints

1 <= balances.length == valueMicrodollarsPerPoint.length <= 2 * 10^5.
1 <= targetMicrodollars <= 10^15.
0 <= balances[i] <= 10^9.
1 <= valueMicrodollarsPerPoint[i] <= 10^9.
All monetary inputs use exact integer microdollars; one dollar equals 10^6 microdollars.