Unit-Weight Knapsack with Limited Quantities
Updated
Problem statement
You are given two arrays, values and quantities, and an integer capacity. Each index describes an item type. Type i has quantities[i] available items, each worth values[i] and weighing exactly one unit.
Choose at most capacity items to maximize their total value. You may choose any whole number of items from each type, from zero through its available quantity. You do not have to fill the knapsack.
Return the maximum total value as a 64-bit integer.
Function
maxValue(values: int[], quantities: int[], capacity: int) → longExamples
Example 1
values = [6,10,8]quantities = [3,2,1]capacity = 4return = 34Choose both items worth 10, the one item worth 8, and one item worth 6. These four items have total value 2 * 10 + 8 + 6 = 34. They are the four most valuable available items.
Example 2
values = [4,7]quantities = [0,2]capacity = 5return = 14Only two items are available, and both are worth 7. Choose both for a total of 2 * 7 = 14. The remaining three units of capacity stay unused.
Example 3
values = [999999999]quantities = [999999999]capacity = 999999999return = 999999998000000001Take all 999999999 available items. Their total value is 999999999 * 999999999 = 999999998000000001, which requires 64-bit arithmetic.
Constraints
0 <= values.length <= 10^5.quantities.length == values.length.0 <= values[i] <= 10^9.0 <= quantities[i] <= 10^9.0 <= capacity <= 10^9.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · 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
- Reduce Array Size to At Most HalfMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Maximize Monsters DefeatedSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Select K Paired Indices for Maximum ScoreAmazon · ONSITE INTERVIEW
- 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