Solve and extend the Knapsack problem
Company: BitGo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given n items, each with an integer weight and value, and a knapsack capacity W. Implement 0/1 Knapsack to return the maximum total value and also reconstruct one optimal set of item indices. Provide an O(nW) time, O(W) space dynamic programming solution and explain how to reconstruct choices from the compressed state. Then outline how to adapt the solution to unbounded and bounded knapsack variants and analyze time and space complexity.
Quick Answer: This question evaluates a candidate's understanding of dynamic programming for optimization problems, specifically the 0/1 knapsack formulation, space-optimized DP and the ability to reconstruct a chosen item set from compressed state.