FastPrepUnit-Weight Knapsack with Limited Quantities
Problems/Unit-Weight Knapsack with Limited Quantities

Unit-Weight Knapsack with Limited Quantities

Google logoGoogle● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report describes a knapsack where every item has weight one but quantities vary, a greedy solution, and a Quickselect follow-up. Our version uses a limited number of item types and returns their maximum total value. The exact inputs, edge rules, and limits were not shared. Our version is about 70% the same as the reported question.

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) → long

Examples

Example 1

values = [6,10,8]quantities = [3,2,1]capacity = 4return = 34

Choose 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 = 14

Only 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 = 999999998000000001

Take 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

Interview reports that mention this question

  • Google Intern Knapsack and Trees: 17 Experiences (Part 6 of 8)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public long maxValue(int[] values, int[] quantities, int capacity) {
        // Write your code here.
    }
}
Checking account…