Practice
1. Consider the following Python code implementing the space-optimized 0/1 Knapsack solution. What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50?
def knapsack_space_optimized(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(knapsack_space_optimized(weights, values, W))easy
Solution
Step 1: Trace dp array updates for each item
For item 0 (weight=10, value=60), dp[w] updated for w=50 down to 10, dp[10..50]=60. For item 1 (weight=20, value=100), dp[30]=max(dp[30], dp[10]+100)=160, dp[50]=max(dp[50], dp[30]+100)=220. For item 2 (weight=30, value=120), dp[50]=max(dp[50], dp[20]+120)=max(220, 160+120)=280 but dp[20] is 60, so dp[50]=max(220, 180)=220.Step 2: Final dp[50] value
The maximum value achievable with capacity 50 is 220.Final Answer:
Option D -> Option DQuick Check:
Manual dp tracing confirms max value 220 [OK]
Hint: Trace dp updates backward to avoid overcounting [OK]
Common Mistakes:
- Forwards iteration over w causes overcounting items.
2. The following code attempts to solve the coin change minimum coins problem. Identify the line containing the subtle bug that causes incorrect results or infinite recursion for amount=0.
def coinChange(coins, amount):
def dfs(rem):
if rem == 0:
return 0
res = float('inf')
for coin in coins:
if rem - coin >= 0:
res = min(res, 1 + dfs(rem - coin))
return res
ans = dfs(amount)
return ans if ans != float('inf') else -1
medium
Solution
Step 1: Analyze base cases in recursion
Code handles rem == 0 but lacks base case for rem < 0, but since rem - coin >= 0 check prevents negative rem, no infinite recursion occurs.Step 2: Check return value correctness
Returning res directly without checking if res is still infinity can cause incorrect results when no valid coin combination exists.Final Answer:
Option C -> Option CQuick Check:
Must check if res is infinity before returning to handle no solution cases correctly [OK]
Hint: Check if result is infinity before returning in recursion [OK]
Common Mistakes:
- Forgetting to handle no solution case
- Assuming rem == 0 base case suffices
3. The following code attempts to solve the Equal Partition problem using a 1D DP array. Which line contains a subtle bug that can cause incorrect results on some inputs?
def canPartition(nums):
total = sum(nums)
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for w in range(num, target + 1):
dp[w] = dp[w] or dp[w - num]
return dp[target]
medium
Solution
Step 1: Identify missing even check
Line 2 does not check if total is even, but this causes no incorrect dp updates, only wasted computation.Step 2: Analyze dp iteration direction
Line 6 iterates forwards, which causes reuse of updated dp values in the same iteration, leading to counting elements multiple times and incorrect results.Final Answer:
Option C -> Option CQuick Check:
Backward iteration is required to avoid reusing updated dp values in the same iteration [OK]
Hint: DP must iterate backwards to avoid reuse in 1D array [OK]
Common Mistakes:
- Iterating forwards in dp updates
- Skipping even sum check
4. What is the time complexity of the bottom-up dynamic programming solution for the Perfect Squares problem using the unbounded knapsack pattern, where
n is the input number?medium
Solution
Step 1: Identify loops in the algorithm
The outer loop runs from 1 to n (O(n)). The inner loop iterates over all perfect squares less than or equal to i, which is approximately O(sqrt(n)) because the largest square root is about sqrt(n).Step 2: Combine complexities
Multiplying outer and inner loops gives O(n * sqrt(n)). Other options either overestimate (O(n^2)) or underestimate (O(n log n), O(sqrt(n) log n)) the complexity.Final Answer:
Option D -> Option DQuick Check:
Nested loops: n and sqrt(n) -> O(n * sqrt(n)) [OK]
Hint: Inner loop runs up to sqrt(n), outer up to n [OK]
Common Mistakes:
- Assuming inner loop is O(n)
- Confusing recursion stack space with DP space
5. Suppose the problem is modified so that each string can be chosen multiple times (unbounded usage). Which change to the dynamic programming approach correctly adapts the solution?
hard
Solution
Step 1: Understand difference between 0/1 and unbounded knapsack
Unbounded knapsack allows multiple uses of the same item, so dp updates must allow reuse within the same iteration.Step 2: Adjust dp iteration order
Iterating dp forwards enables using updated states multiple times, correctly counting repeated strings.Step 3: Confirm correctness
Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded usage.Final Answer:
Option A -> Option AQuick Check:
Forward iteration enables multiple item usage [OK]
Hint: Unbounded knapsack uses forward dp iteration [OK]
Common Mistakes:
- Continuing backward iteration from 0/1 knapsack
- Adding extra dp dimensions unnecessarily
