Solve the 0/1 knapsack problem with dynamic programming
Reported in HelloFresh European engineering loops. Classic DP testing tabulation, space optimization, and item selection reconstruction.
Interview scenario
Context for HelloFresh candidates:
Each item can be taken at most once. Maximize total value without exceeding capacity W.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at HelloFresh: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Define dp[i][w] = max value using first i items with capacity w. Transition: skip item i (dp[i-1][w]) or take it if weight fits (value[i] + dp[i-1][w-weight[i]]).
Tabulation fills a 2D table in O(n·W) time. Space-optimize to 1D array iterating w backwards to avoid reusing item i twice:
for item in items:
for w in range(W, weight[item] - 1, -1):
dp[w] = max(dp[w], value[item] + dp[w - weight[item]])Discuss pseudo-polynomial complexity vs true polynomial. Follow-ups: unbounded knapsack (unlimited copies), subset sum variant, and reconstruct chosen items by backtracking from full table.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.