Question presented to candidate: "You have n items, each with a weight and a value, and a bag that holds at most W. Each item can be taken at most once. What is the largest total value you can carry? Walk me through your approach and code it in Python."
What a strong answer should cover:
- Why greedy (best value per weight first) fails for 0/1 items, with a counter-example.
- The state
dp[i][c]= best value from the first i items with capacity c, and the take-or-skip transitionmax(dp[i-1][c], dp[i-1][c-w] + v). - O(n·W) time, pseudo-polynomial, and O(W) space with one row looped backwards — and why forwards would reuse items (unbounded knapsack).
- Rebuilding the chosen items by walking back through the full table.
- Python details:
dp[c - w]withc < wsilently reads from the end of the list (negative indexing), so the loop bounds must stop at w; and a list comprehension for the 2D table.
Clarifying questions expected:
- Can an item be used more than once, or split?
- How large are W and n?
- Do you need the chosen items or only the best value?
Code / implementation expected: Yes — the one-row DP with a backwards capacity loop in Python; the 2D table if the items must be listed.