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 Technical Screen rounds at BitGo.

What role is this question designed for?

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

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.

You are given `n` items, where item `i` has integer `weights[i]` and `values[i]`, and a knapsack capacity `W`. Each item may be taken at most once (0/1 knapsack). Return a tuple `(max_value, chosen)` where: - `max_value` is the maximum total value of any subset of items whose total weight does not exceed `W`. - `chosen` is a list of the selected item indices (the reconstructed optimal set), sorted in ascending order. If several optimal sets exist, return the one produced by the standard backward reconstruction described below. **Core idea (O(nW) time, O(W) space).** Maintain a 1D DP array `dp` of length `W + 1`, where `dp[c]` is the best achievable value using a capacity of `c`. Process items one at a time; for each item iterate the capacity from `W` down to `weights[i]` (descending so each item is used at most once) and apply `dp[c] = max(dp[c], dp[c - weights[i]] + values[i])`. The answer value is `dp[W]`. **Reconstructing choices from compressed state.** The rolling 1D `dp` alone forgets which items were taken. To recover one optimal set, record, for each item `i` and capacity `c`, whether taking item `i` strictly improved `dp[c]` at the moment it was processed (a `keep[i][c]` flag). After filling the table, walk items from last to first: at the current remaining capacity `c`, if `keep[i][c]` is set, add `i` to the chosen set and subtract `weights[i]` from `c`. Finally sort the chosen indices. (Recording `keep` is O(nW) extra space; an alternative that preserves O(W) working space is to store only the rolling `dp` and re-derive choices via a second pass or by keeping `dp` snapshots — both are acceptable, the `keep` table is shown here for clarity.) **Variants (discussion).** - *Unbounded knapsack* (each item usable unlimited times): iterate the inner capacity loop *ascending* (`weights[i]..W`) instead of descending, so the same item can be reused within one pass. Time O(nW), space O(W). - *Bounded knapsack* (item `i` usable up to `c_i` times): the naive approach loops each copy (O(W * sum(c_i))). The efficient approach uses binary (power-of-two) decomposition of each multiplicity into log2(c_i) virtual items and then runs 0/1 knapsack, giving O(W * sum(log c_i)) time; a monotonic-deque optimization achieves O(nW). Return the tuple for the 0/1 case.

Constraints

0 <= n <= 1000 (n == len(weights) == len(values))
0 <= W <= 10000
1 <= weights[i] <= W (when n > 0); 0 <= values[i] <= 10^6
Each item may be used at most once (0/1 knapsack)
If multiple optimal subsets exist, return the one from the standard backward reconstruction (indices sorted ascending)

Examples

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

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

Explanation: Items 1 (w=3,v=4) and 2 (w=4,v=5) fill weight 7 exactly for value 9 — better than item 3 alone (v=7) or items 0+3 (w=6,v=8).

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

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

Explanation: Items 0 (w=2,v=3) and 1 (w=3,v=4) use weight 5 for value 7, beating any single item that fits (max single value at w<=5 is 6).

Input: ([], [], 10)

Expected Output: (0, [])

Explanation: No items: max value is 0 and the chosen set is empty regardless of capacity.

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

Expected Output: (0, [])

Explanation: The only item weighs 5 but capacity is 4, so it cannot be taken; value 0, empty set.

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

Expected Output: (10, [0])

Explanation: The single item exactly fits the capacity, so it is taken for value 10.

Input: ([1, 1, 1], [10, 20, 30], 2)

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

Explanation: Capacity 2 holds two unit-weight items; the two highest-value ones are indices 1 (20) and 2 (30) for total 50.

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

Expected Output: (0, [])

Explanation: Capacity 0 means nothing can be taken; value 0, empty set.

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

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

Explanation: All three items fit exactly within capacity 6 for total value 9.

Hints

Use a 1D dp array of size W+1 and iterate the capacity from W down to weights[i] so each item is counted at most once. Iterating ascending instead would turn it into the unbounded variant.
The rolling 1D dp forgets *which* items were taken. Record a keep[i][c] flag whenever taking item i strictly improves dp[c], then reconstruct by walking items backward from capacity W.
Edge cases: empty item list, an item heavier than W (never fits), and W == 0 should all return value 0 and an empty chosen set.

Quick Overview

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.