FastPrepZero-One Knapsack
Problems/Zero-One Knapsack

Zero-One Knapsack

Bloomberg LP logoBloomberg LP● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report from a Bloomberg interview for a senior software engineer role names the classic knapsack question, where each item is taken or left, and then a follow-up variant that allows at most three stones and that the report says turns into a 3Sum-like task. We cover only the first question here. The report gives no statement, limits or example, and it describes the process in general without saying which round asked these questions.

Everything else here is our practice choice. The three-stone follow-up is not judged. Each item has a weight and a value and can be taken at most once. The total weight must not go above the capacity, and the answer is the largest total value; taking nothing gives 0. There are 1 to 100 items with weights from 1 to 100 and values from 1 to 1000, and the capacity is 1 to 1000.

The judged task matches the report at about 70%.

You have a bag that can carry a total weight of at most capacity, and a list of items. Item i weighs weights[i] and is worth values[i]. Each item can be put in the bag at most once.

Choose some of the items so that their total weight is at most capacity. Return the largest total value you can get. Choosing no items gives 0.

Function

knapsack(weights: int[], values: int[], capacity: int) → int

Examples

Example 1

weights = [2,3,4,5]values = [3,4,5,6]capacity = 5return = 7

Several choices fit in a bag of capacity 5. Items 0 and 1 weigh 2 + 3 = 5 and are worth 3 + 4 = 7. Item 3 alone weighs 5 and is worth 6. Item 2 alone is worth 5. The best is 7.

Example 2

weights = [3,2,2]values = [5,3,3]capacity = 4return = 6

Item 0 is worth the most per unit of weight (5 for 3), but it leaves only 1 unit of room, so nothing else fits and the total is 5. Items 1 and 2 weigh 2 + 2 = 4 and are worth 3 + 3 = 6. The best is 6.

Example 3

weights = [5,6]values = [10,20]capacity = 4return = 0

Both items are heavier than the capacity 4, so none can be taken. The best is 0.

Example 4

weights = [2]values = [7]capacity = 6return = 7

The only item can be taken once, so the total is 7, even though three copies would fit by weight.

Constraints

  • 1 <= weights.length <= 100
  • values.length == weights.length
  • 1 <= weights[i] <= 100
  • 1 <= values[i] <= 1000
  • 1 <= capacity <= 1000

More Bloomberg LP Phone Screen questions

  • N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Fewest Coins CombinationPHONE SCREEN · Seen Nov 2026
  • Recommend Films from Viewers Who Watched Everything You DidPHONE SCREEN · Seen Nov 2026
  • Track New Values in Sorted OrderPHONE SCREEN · Seen Nov 2026
  • Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Sparse Vector and Matrix OperationsPHONE SCREEN · Seen Oct 2026
  • Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026

Similar questions at other companies

  • Maximum Subarray Sum with One DeletionServiceNow · PHONE SCREENServiceNow interview questions
  • Maximum Product of a Contiguous SubarrayLinkedIn · PHONE SCREENLinkedIn interview questions
  • Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
  • Jump GamePaytm · PHONE SCREENPaytm interview questions
  • Query Words Within K PositionsPalantir · PHONE SCREENPalantir interview questions
  • House RobberVisa · PHONE SCREENVisa interview questions
  • Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
  • Longest Increasing SubsequenceAngel One · PHONE SCREEN
  • Match Shops and BuyersGoogle · PHONE SCREENGoogle interview questions
  • Minimum Cost for a Target WeightPace Stock Broking Services · PHONE SCREEN

Interview reports that mention this question

  • Bloomberg Experienced Design & More: 126 Questions (Part 2 of 2)

Bloomberg LP interview experiences

  • Bloomberg AI-Assisted Coding Round, All Levels: 14 Experiences
  • Bloomberg SWE Intern Interview Questions: 68 Questions
  • Bloomberg Interview Questions, Level Not Reported: 65 Questions
  • Bloomberg Experienced SWE Interviews: 167 Questions (Part 1 of 2)
  • Bloomberg New Grad Coding Questions: 121 Questions (Part 2 of 2)
All Bloomberg LP interview questionsSee Bloomberg LP hiring insights
Saved
class Solution {
    public int knapsack(int[] weights, int[] values, int capacity) {
        // Write your code here.
    }
}
Checking account…