How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Optimize 0/1 to bounded knapsack DP | Google Coding Question

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.

0/1 Knapsack with Solution Reconstruction

You are given arrays `weight[i]` and `value[i]` for items `i = 0..n-1`, and a knapsack capacity `W`. Each item may be taken at most once. Return a pair `(max_value, chosen_indices)` where `max_value` is the maximum total value achievable without exceeding capacity `W`, and `chosen_indices` is one optimal set of selected item indices in ascending order. Provide the classic O(nW) time / O(nW) space dynamic program. The 2D table `dp[i][w]` (max value using the first `i` items at capacity `w`) is also what enables reconstruction: walk back from `dp[n][W]`, and whenever `dp[i][w] != dp[i-1][w]` item `i-1` was taken. A space-optimized O(W) variant exists for the value alone, but reconstructing the chosen set requires either the full 2D table or storing per-item decision bits. Dry run on `weight=[2,3,4]`, `value=[4,5,10]`, `W=7`: the optimum is value `15` taking items `{1, 2}` (weights 3+4=7).

Constraints

0 <= n <= 1000
0 <= W <= 10000
0 <= weight[i], value[i]
len(weight) == len(value) == n
Each item may be selected at most once (0/1).

Examples

Input: ([2,3,4], [4,5,10], 7)

Expected Output: (15, [1, 2])

Explanation: Take items 1 (w3,v5) and 2 (w4,v10): total weight 7, value 15 — the headline dry-run case.

Input: ([1,2,3], [6,10,12], 5)

Expected Output: (22, [1, 2])

Explanation: Items 1 (w2,v10) + 2 (w3,v12) fill capacity 5 for value 22, beating item 0.

Input: ([], [], 10)

Expected Output: (0, [])

Explanation: No items: value 0, empty selection.

Input: ([5], [10], 4)

Expected Output: (0, [])

Explanation: The only item (weight 5) does not fit in capacity 4.

Input: ([5], [10], 5)

Expected Output: (10, [0])

Explanation: The single item exactly fills capacity 5.

Input: ([1,1,1], [1,1,1], 2)

Expected Output: (2, [0, 1])

Explanation: Three identical unit items, capacity 2: take any two; the DP's strict-improvement tie-break yields indices [0, 1].

Hints

Define dp[i][w] = best value using the first i items at capacity w. Transition: skip item i-1 (dp[i-1][w]) or take it if it fits (dp[i-1][w-weight[i-1]] + value[i-1]).
To reconstruct, walk i from n down to 1: if dp[i][w] differs from dp[i-1][w], item i-1 was taken — subtract its weight from w and record the index.
For O(W) space you can collapse to one row iterated w from W down to weight[i-1], but you lose the per-step history needed to reconstruct unless you save decision bits.

Bounded Knapsack via Binary Decomposition

Extend 0/1 knapsack to the bounded variant: item `i` has weight `weight[i]`, value `value[i]`, and may be taken at most `count[i]` times. Given capacity `W`, return the maximum total value. The efficient trick is binary decomposition of each item's count. Split `count[i]` into powers of two `1, 2, 4, ..., remainder`; each chunk becomes a single virtual 0/1 item with weight `weight[i]*chunk` and value `value[i]*chunk`. Any quantity from 0 to count[i] is representable by choosing a subset of these chunks, so the problem reduces to ordinary 0/1 knapsack over O(sum log count[i]) virtual items — solved with the standard O(W) rolling-array DP. Dry run on `weight=[2,3,4]`, `value=[4,5,10]`, `count=[3,1,2]`, `W=7`: the optimum is value `15` (one item 1 of weight 3 plus one item 2 of weight 4 = weight 7).

Constraints

0 <= n <= 1000
0 <= W <= 10000
0 <= weight[i], value[i]
0 <= count[i]
len(weight) == len(value) == len(count) == n

Examples

Input: ([2,3,4], [4,5,10], [3,1,2], 7)

Expected Output: 15

Explanation: Headline dry run: take one item 1 (w3,v5) + one item 2 (w4,v10) = weight 7, value 15. Using more copies of cheaper items can't beat it within capacity 7.

Input: ([2,3,4], [4,5,10], [1,1,1], 7)

Expected Output: 15

Explanation: All counts 1 — reduces to the 0/1 case, same optimum 15.

Input: ([1], [5], [10], 4)

Expected Output: 20

Explanation: Single item weight 1, value 5, up to 10 copies; capacity 4 fits 4 copies = value 20.

Input: ([], [], [], 5)

Expected Output: 0

Explanation: No items: value 0.

Input: ([3], [7], [2], 2)

Expected Output: 0

Explanation: Item weight 3 cannot fit in capacity 2 even though 2 copies are allowed.

Input: ([2,2], [3,4], [2,2], 6)

Expected Output: 11

Explanation: Capacity 6: two copies of item 1 (w2,v4 each = w4,v8) + one copy of item 0 (w2,v3) = weight 6, value 11.

Hints

Naively turning each item into count[i] separate 0/1 items works but is O(W * sum count[i]) — too slow when counts are large.
Binary decomposition: 1 + 2 + 4 + ... + 2^(k-1) + r = count[i], and any 0..count[i] copies are reachable by picking a subset of these chunks. This drops the factor to sum log(count[i]).
After decomposition it's plain 0/1 knapsack: one rolling array dp[w], iterate w from W down to chunk_weight so each chunk is used at most once.

Quick Overview

This question evaluates mastery of dynamic programming for knapsack problems, focusing on state formulation, space-time optimization, and reconstructing optimal item sets.