Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleFacebook

Ones and Zeroes (2D Knapsack)

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize DP Table

Create a 2D dp array of size (m+1) x (n+1) filled with zeros, representing no strings chosen yet.

💡 Initialization sets the base case: with zero strings, the maximum subset size is zero regardless of zeros and ones available.
Line:dp = [[0] * (n + 1) for _ in range(m + 1)]
💡 The dp table starts empty, ready to be filled as strings are processed.
📊
Ones and Zeroes (2D Knapsack) - Watch the Algorithm Execute, Step by Step
Watching the dp table fill in real time reveals how the algorithm balances the two constraints and builds up the solution incrementally.
Step 1/20
·Active fill★Answer cell
Initializing dp array
i\w0123
i=00000
i=10000
i=20000
i=30000
i=40000
i=50000
initialized to 0
Item 0 - wt:1 val:1
i\w0123
i=00000
i=10000
i=20000
i=30000
i=40000
i=50000
Item 0 - wt:1 val:1
i\w0123
i=00000
i=10000
i=20000
i=30000
i=40000
i=50001
updated
Item 0 - wt:1 val:1
i\w0123
i=00000
i=10000
i=20000
i=30000
i=40010
i=50001
updated
Item 0 - wt:1 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
updated
Item 1 - wt:3 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
Item 1 - wt:3 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
no change
Item 1 - wt:3 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
no change
Item 1 - wt:3 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
no change
Item 2 - wt:2 val:4
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
Item 2 - wt:2 val:4
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
Item 3 - wt:0 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
Item 3 - wt:0 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50001
no change
Item 3 - wt:0 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50011
updated
Item 3 - wt:0 val:1
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50111
updated
Item 4 - wt:1 val:0
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50111
Item 4 - wt:1 val:0
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40010
i=50111
no change
Item 4 - wt:1 val:0
i\w0123
i=00000
i=10000
i=20000
i=30100
i=40011
i=50111
updated
Item 4 - wt:1 val:0
i\w0123
i=00000
i=10000
i=20000
i=30101
i=40011
i=50111
updated
Initializing dp array
i\w0123
i=00000
i=10000
i=20000
i=30101
i=40011
i=50114
final answer

Key Takeaways

✓ The dp table incrementally builds the maximum subset size respecting two constraints simultaneously.

This insight is hard to see from code alone because the two-dimensional resource constraints and their interaction are subtle.

✓ The dp table is filled in reverse order of zeros and ones to avoid overwriting values needed for future computations.

Watching the fill order visually clarifies why the loops go backwards, which is not obvious from code.

✓ Strings that require more zeros or ones than available are pruned automatically, leaving dp unchanged for those cases.

Seeing no updates for such strings helps understand how resource constraints prune the search space.

Practice

(1/5)
1. Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?
easy
A. 1
B. 0
C. 2
D. 3

Solution

  1. Step 1: Calculate total and half

    Total = 6, half = 3. dp array size = 4, dp[0] = true initially.
  2. Step 2: Update dp for each stone

    For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.
  3. Step 3: Find largest w ≤ half with dp[w] = true

    dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]
Hint: Check dp array for sums up to half total [OK]
Common Mistakes:
  • Returning total instead of minimal difference
  • Off-by-one error in dp indexing
  • Not iterating backwards in dp update
2. What is the time complexity of the optimal bottom-up dynamic programming solution for the Coin Change II problem with n coins and target amount amount?
medium
A. O(amount^2)
B. O(n + amount)
C. O(2^amount)
D. O(n * amount)

Solution

  1. Step 1: Identify loops in code

    Outer loop iterates over n coins, inner loop iterates over amount from coin to amount.
  2. Step 2: Calculate complexity

    Each dp[w] update is O(1), total updates are roughly n * amount, so time complexity is O(n * amount).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Nested loops over coins and amounts confirm O(n * amount) [OK]
Hint: Count nested loops and their ranges [OK]
Common Mistakes:
  • Confusing amount with n
  • Forgetting recursion stack space
  • Assuming quadratic in amount
3. The following code attempts to solve the minimum subset sum difference problem using space-optimized DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 4: dp initialization without dp[0] = true
B. Line 6: Outer loop iterating over elements
C. Line 7: Inner loop iterating backwards from total_sum
D. Line 11: Returning difference using total_sum and w

Solution

  1. Step 1: Check base case initialization

    dp[0] must be true to represent sum zero achievable with empty subset; missing this causes no sums to be marked achievable.
  2. Step 2: Verify other lines

    Loops and return statement are correct; only missing dp[0] initialization breaks correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without dp[0] = true, dp array never updates correctly [OK]
Hint: dp[0] = true is essential base case [OK]
Common Mistakes:
  • Forgetting dp[0] initialization
  • Using forward iteration causing overcounting
4. Suppose the problem is modified so that jobs can be scheduled multiple times (i.e., unlimited reuse of the same job), still without overlapping. Which modification to the optimal DP approach is correct?
hard
A. Replace binary search with linear search to find compatible jobs and keep DP unchanged
B. Use a 1D DP array indexed by time and for each time, consider all jobs that can start then, allowing reuse
C. Keep the same DP with binary search but remove the skip option to always take the current job
D. Sort jobs by start time and use memoized recursion without binary search

Solution

  1. Step 1: Understand unlimited reuse impact

    Allowing multiple uses of the same job means the problem resembles unbounded interval scheduling with no overlaps.
  2. Step 2: Modify DP approach

    Use a 1D DP array indexed by time (e.g., dp[t] = max profit up to time t). For each time, consider all jobs starting at or after t, allowing reuse by updating dp[end_i] = max(dp[end_i], dp[start_i] + profit_i).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search and skip logic do not handle reuse; time-indexed DP handles multiple scheduling [OK]
Hint: Use time-indexed DP for unlimited job reuse [OK]
Common Mistakes:
  • Trying to reuse binary search DP without changes
  • Removing skip option breaks correctness
  • Sorting by start time only
5. Suppose the problem is modified so that each element in the array can be chosen multiple times (unbounded). Which modification to the DP approach correctly solves this variant?
hard
A. Change inner loop to iterate forwards from num to total_sum to allow reuse
B. Keep inner loop iterating backwards from total_sum to num as in original code
C. Use recursion without memoization to handle multiple uses
D. Sort array and greedily pick largest elements repeatedly

Solution

  1. Step 1: Understand reuse impact on DP iteration

    For unbounded knapsack variants, inner loop must iterate forwards to allow multiple counts of the same element.
  2. Step 2: Contrast with original code

    Original code iterates backwards to avoid counting elements multiple times; forward iteration enables reuse.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Forward iteration in inner loop enables multiple uses of elements [OK]
Hint: Forward iteration allows multiple element reuse in DP [OK]
Common Mistakes:
  • Using backward iteration causing single use only
  • Assuming recursion without memo is efficient
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