Minimum Reward Points to Cover a Payment
Updated
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[]) → longExamples
Example 1
targetMicrodollars = 168000000balances = [36000,12000,25000]valueMicrodollarsPerPoint = [12000,9000,8500]return = 14000The 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 = 3Use 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 = -1Both 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^6microdollars.
More Amazon Onsite Interview questions
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dungeon GameONSITE INTERVIEW · Seen Nov 2026
- Integer BreakONSITE INTERVIEW · Seen Nov 2026
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
- First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Minimum Station Tracks for a Train ScheduleBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Unit-Weight Knapsack with Limited QuantitiesGoogle · ONSITE INTERVIEWGoogle interview questions
- Reduce Array Size to At Most HalfMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Maximize Monsters DefeatedSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions
- Minimum Removals for Non-Overlapping IntervalsByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Maximize Element FrequencyGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Fair Capped Money DistributionGusto · ONSITE INTERVIEWGusto interview questions
- Minimum Workers with Job AssignmentsLyft · ONSITE INTERVIEWLyft interview questions