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.
Step 3: Find largest w ≤ half with dp[w] = true
dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.
Final Answer:
Option B -> Option B
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. Consider the following Python code implementing the optimal job scheduling solution. What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]?
easy
A. 120
B. 20
C. 140
D. 100
Solution
Step 1: Sort jobs by end time
Jobs sorted by end time: [(1,3,20), (2,5,20), (3,10,100)]. Ends = [3,5,10]
Hint: Binary search finds last compatible job index correctly [OK]
Common Mistakes:
Off-by-one in binary search index
Using dp[i-1] incorrectly
Ignoring base case for dp[0]
3. You need to find the number of distinct ways to make a target amount using unlimited supply of given coin denominations. Which algorithmic approach guarantees counting all unique combinations without overcounting permutations?
easy
A. Greedy algorithm that picks the largest coin first until the amount is reached
B. Dynamic programming using a 1D array iterating coins first, then amounts
C. Backtracking exploring all permutations of coins to sum to the amount
D. Sorting coins and using two pointers to find pairs that sum to the amount
Solution
Step 1: Understand problem constraints
The problem requires counting unique combinations, not permutations, of coins to reach the target amount.
Step 2: Identify algorithm that counts combinations without duplicates
Dynamic programming iterating coins first ensures each coin is considered in order, avoiding counting permutations multiple times. The 1D DP approach efficiently accumulates counts for each amount.
Final Answer:
Option B -> Option B
Quick Check:
DP with coin-first iteration counts combinations correctly [OK]
4. What is the time complexity of the space-optimized bottom-up 0/1 Knapsack algorithm when there are n items and the knapsack capacity is W?
medium
A. O(2^n)
B. O(n + W)
C. O(n * W)
D. O(n * log W)
Solution
Step 1: Identify loops in the algorithm
The algorithm has an outer loop over n items and an inner loop over capacities from W down to the item's weight, which can be up to W iterations.
Step 2: Calculate total operations
Multiplying the loops gives O(n * W) time complexity. Recursive brute force is exponential, and linear or logarithmic complexities are incorrect here.
Final Answer:
Option C -> Option C
Quick Check:
Nested loops over n and W -> O(n * W) [OK]
Hint: Nested loops over items and capacity -> O(n * W) [OK]
Common Mistakes:
Confusing recursion stack space with time complexity.
5. Suppose the coin change problem is modified so that each coin can only be used at most once (0/1 knapsack variant). Which of the following changes to the bottom-up DP approach correctly solves this variant?
hard
A. Use a 2D dp array where dp[i][j] represents minimum coins to make amount j using first i coins, iterating coins outer and amounts inner
B. Sort coins and greedily pick largest coins without repetition until amount is reached
C. Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage)
D. Use the same 1D dp but iterate amounts outer and coins inner, updating dp[j] only if dp[j - coin] was from previous iteration
Solution
Step 1: Understand the 0/1 usage constraint
Each coin can be used once, so we must track usage per coin, requiring 2D dp.
Step 2: Identify correct DP structure
2D dp with dp[i][j] = min coins to make j using first i coins ensures no reuse; iterate coins outer, amounts inner.
Step 3: Why other options fail
Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage) allows unlimited reuse; B is greedy and incorrect; D misuses 1D dp which is for unbounded usage.
Final Answer:
Option A -> Option A
Quick Check:
0/1 knapsack requires 2D dp to track coin usage [OK]
Hint: 0/1 knapsack needs 2D dp to prevent reuse [OK]
Common Mistakes:
Using unbounded knapsack DP for 0/1 problem
Assuming greedy works for minimum coins
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.