Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleMicrosoftGoldman_Sachs

0/1 Knapsack Problem

Choose your preparation mode4 modes available
</>
IDE
def knapsack_recursive(i: int, w: int, weights: list[int], values: list[int]) -> int:public int knapsackRecursive(int i, int w, int[] weights, int[] values)int knapsack_recursive(int i, int w, vector<int>& weights, vector<int>& values)function knapsackRecursive(i, w, weights, values)
def knapsack_recursive(i, w, weights, values):
    # Write your solution here
    pass
class Solution {
    public int knapsackRecursive(int i, int w, int[] weights, int[] values) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int knapsack_recursive(int i, int w, vector<int>& weights, vector<int>& values) {
    // Write your solution here
    return 0;
}
function knapsackRecursive(i, w, weights, values) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: 0Always returning 0 due to missing base case or incorrect initialization.✅ Add base case: if i == 0 or w == 0, return 0.
Wrong: Sum of all values regardless of weightIgnoring weight constraints and including all items.✅ Check if weights[i-1] <= w before including item in dp recurrence.
Wrong: Value greater than correct max (e.g., 120 in t3_02)Using unbounded knapsack logic allowing multiple picks of same item.✅ Ensure DP state includes item index and only considers each item once.
Wrong: Value less than max due to greedy approach (e.g., 80 instead of 90 in t3_01)Greedy selection by value or ratio instead of DP.✅ Implement full DP considering all subsets, not greedy picks.
Wrong: Timeout or no outputExponential brute force solution without memoization or DP.✅ Use bottom-up or top-down DP with memoization to achieve O(n*W) time.
✓
Test Cases
t1_01basic
Input{"n":3,"W":50,"weights":[10,20,30],"values":[60,100,120]}
Expected220

Choose items with weights 20 and 30 for total value 100 + 120 = 220 without exceeding capacity 50.

t1_02basic
Input{"n":4,"W":10,"weights":[1,3,4,5],"values":[1,4,5,7]}
Expected12

Choose items with weights 4 and 5 for total value 5 + 7 = 12 without exceeding capacity 10.

t2_01edge
Input{"n":0,"W":50,"weights":[],"values":[]}
Expected0

No items to choose from, so max value is 0.

t2_02edge
Input{"n":1,"W":10,"weights":[10],"values":[100]}
Expected100

Single item fits exactly into knapsack, so max value is 100.

t2_03edge
Input{"n":3,"W":5,"weights":[6,7,8],"values":[10,20,30]}
Expected0

All items heavier than capacity, so no items can be included, max value 0.

t2_04edge
Input{"n":3,"W":100,"weights":[10,20,30],"values":[60,100,120]}
Expected280

All items fit into knapsack capacity, so max value is sum of all values 60+100+120=280.

t3_01corner
Input{"n":4,"W":8,"weights":[3,4,5,6],"values":[30,50,60,90]}
Expected90

Greedy approach picking highest value first fails; best is item with weight 6 and value 90.

t3_02corner
Input{"n":3,"W":10,"weights":[2,3,5],"values":[20,30,50]}
Expected100

0/1 knapsack: each item can be chosen once; total max value is 100 by choosing items 2 and 3 (30+50) plus item 1 (20).

t3_03corner
Input{"n":5,"W":15,"weights":[1,2,3,4,5],"values":[10,20,30,40,50]}
Expected150

All items fit exactly into capacity 15, total value sum is 150.

t4_01performance
Input{"n":100,"W":1000,"weights":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],"values":[50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]}
⏱ Performance - must finish in 2000ms

n=100, W=1000, O(n*W) DP must complete within 2 seconds.

Practice

(1/5)
1. Consider the following code snippet for the coin change problem. What is the value of dp[5] after the outer loop iteration i=5 completes when coins = [1, 2, 5] and amount = 5?
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount]

print(coinChange([1,2,5], 5))
easy
A. 5
B. 2
C. 3
D. 1

Solution

  1. Step 1: Trace dp array updates up to i=5

    dp[0]=0; For i=1: dp[1]=min(inf,1+dp[0])=1; i=2: dp[2]=min(inf,1+dp[1],1+dp[0])=1; i=3: dp[3]=min(inf,1+dp[2],1+dp[1])=2; i=4: dp[4]=min(inf,1+dp[3],1+dp[2])=2; i=5: dp[5]=min(inf,1+dp[4],1+dp[3],1+dp[0])=min(inf,3,3,1)=1
  2. Step 2: Confirm dp[5] value

    Using coin 5 directly gives dp[5]=1, which is minimal.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    dp[5] = 1 coin (coin 5) [OK]
Hint: Direct coin equal to amount sets dp[amount] to 1 [OK]
Common Mistakes:
  • Off-by-one errors in indexing dp
  • Ignoring direct coin match
2. You need to split a positive integer n into at least two positive integers such that the product of these integers is maximized. Which algorithmic approach guarantees finding the optimal solution efficiently?
easy
A. Pure brute force recursion exploring all partitions without memoization
B. A greedy approach that always cuts the integer into 3s and 2s
C. Dynamic programming using bottom-up tabulation with state representing maximum product for each integer up to n
D. Divide and conquer by splitting the integer into two halves recursively without caching results

Solution

  1. Step 1: Understand problem structure

    The problem requires maximizing product by splitting an integer into parts, which naturally fits a DP approach where subproblems represent maximum product for smaller integers.
  2. Step 2: Evaluate options

    Greedy (always cutting 3s) fails on some inputs; brute force recursion is correct but inefficient; divide and conquer without memoization repeats work. Bottom-up DP tabulation efficiently computes all subproblems and combines results.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    DP tabulation ensures optimal substructure and overlapping subproblems [OK]
Hint: DP tabulation handles overlapping subproblems optimally [OK]
Common Mistakes:
  • Believing greedy always works for integer break
  • Ignoring memoization in recursion
3. You are given a set of positive integers and need to partition it into two subsets such that the absolute difference of their sums is minimized. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Greedy algorithm that sorts and assigns elements alternately to subsets
B. Dynamic programming using a subset-sum style approach to find achievable sums
C. Divide and conquer by recursively splitting the array into halves
D. Sorting and then pairing elements from opposite ends to balance sums

Solution

  1. Step 1: Understand problem constraints

    The problem requires minimizing the difference between sums of two subsets, which is a classic partition problem variant.
  2. Step 2: Identify algorithmic pattern

    Greedy or divide-and-conquer approaches do not guarantee minimal difference. Dynamic programming, specifically subset-sum style DP, can find all achievable sums up to total_sum, enabling minimal difference calculation.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP subset-sum approach guarantees optimal partition [OK]
Hint: Minimal difference requires subset-sum DP, not greedy [OK]
Common Mistakes:
  • Assuming greedy or sorting suffices for minimal difference
4. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?
medium
A. Line 5: inner loop iterating backwards over amounts
B. Line 4: outer loop over coins
C. Line 2: dp initialization
D. Line 6: updating dp[w] with dp[w - coin]

Solution

  1. Step 1: Understand iteration order effect

    Iterating amounts backwards causes dp to count permutations, not combinations.
  2. Step 2: Identify bug line

    Line 5 iterates w from amount down to coin, which breaks combination counting logic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Forward iteration over amounts is required to count combinations correctly [OK]
Hint: Check direction of inner loop iteration [OK]
Common Mistakes:
  • Using backward iteration in 1D dp
  • Misplacing dp[0] initialization
5. What is the time complexity of the space-optimized bottom-up DP solution for the Target Sum problem with input array length n and total sum S = sum(nums)?
medium
A. O(2^n) because all sign combinations are explored
B. O(n * S) because the DP iterates over n elements and sums from -S to S
C. O(n^2) because of nested loops over elements
D. O(n * log S) due to binary search on sums

Solution

  1. Step 1: Identify loops in the DP

    The outer loop runs n times, the inner loop runs over sums from -S to S, total 2S+1 states.
  2. Step 2: Calculate total operations

    Each iteration updates dp for each sum, so total time is O(n * S). Exponential 2^n is brute force, not DP.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP complexity depends on n and sum range, not exponential [OK]
Hint: DP iterates over n and sum range, not all subsets [OK]
Common Mistakes:
  • Confusing brute force 2^n with DP complexity
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard