Optimize 0/1 to bounded knapsack DP
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Solve the 0/1 knapsack problem: given arrays weight[i], value[i] for i=0..n-1 and capacity W, return the maximum value and reconstruct one optimal set of item indices. Provide both O(nW) time/O(nW) space and O(nW) time/O(W) space solutions. Next, extend your solution to the bounded knapsack variant where each item i has a limited count count[i]. Implement an O(nW) approach using binary decomposition of counts (or another efficient method), and explain the complexity and memory trade-offs. Dry-run both variants on: weight=[2,3,4], value=[4,5,10], W=7 (0/1 case), then count=[3,1,2] (bounded case).
Quick Answer: This question evaluates mastery of dynamic programming for knapsack problems, focusing on state formulation, space-time optimization, and reconstructing optimal item sets.