Practice
1. You are given an array of stock prices where you can complete at most two transactions (buy-sell pairs). Which algorithmic approach guarantees finding the maximum profit efficiently?
easy
Solution
Step 1: Understand problem constraints
At most two transactions means we must track states for 0, 1, or 2 completed transactions and whether we hold stock or not.Step 2: Identify suitable algorithm
Greedy and divide-and-conquer fail to consider overlapping subproblems and state transitions correctly. Brute force is correct but inefficient. DP with state machines efficiently tracks profits per transaction count and holding state.Final Answer:
Option A -> Option AQuick Check:
DP with states is standard for multi-transaction stock problems [OK]
Hint: Track transactions and holding states with DP [OK]
Common Mistakes:
- Assuming greedy picks always yield global optimum
- Using brute force without pruning
2. You are given a list of daily stock prices and want to maximize profit by buying and selling any number of times, but you cannot hold more than one stock at a time. Which algorithmic approach guarantees the optimal solution for this problem?
easy
Solution
Step 1: Understand problem constraints
The problem allows unlimited transactions but only one stock can be held at a time.Step 2: Identify suitable algorithm
For this problem, the greedy approach of summing all positive price differences between consecutive days guarantees the optimal profit. This works because any profitable transaction can be decomposed into these increments.Final Answer:
Option A -> Option AQuick Check:
Greedy summing positive differences is optimal for unlimited transactions without cooldown or fees [OK]
Hint: Sum all positive price differences between consecutive days to get max profit [OK]
Common Mistakes:
- Assuming DP is required when greedy suffices
- Using brute force without memoization
- Trying divide and conquer without state tracking
3. Consider the following Python function that computes the maximum profit from unlimited stock transactions. What is the value of the variable
not_holding after the second iteration of the loop (i=2) when called with prices = [3, 2, 6]?
def maxProfit(prices):
n = len(prices)
not_holding = 0
holding = -prices[0]
for i in range(1, n):
prev_not_holding = not_holding
not_holding = max(not_holding, holding + prices[i])
holding = max(holding, prev_not_holding - prices[i])
return not_holding
easy
Solution
Step 1: Initialize variables
not_holding = 0, holding = -3 (since prices[0] = 3)Step 2: Iterate and update for i=1 and i=2
i=1: prev_not_holding=0; not_holding = max(0, -3+2) = 0; holding = max(-3, 0-2) = -2 i=2: prev_not_holding=0; not_holding = max(0, -2+6) = 4; holding = max(-2, 0-6) = -2Final Answer:
Option D -> Option DQuick Check:
At i=2, not_holding is 4 after updates [OK]
Hint: Track variables carefully at each iteration [OK]
Common Mistakes:
- Off-by-one errors in loop index
- Confusing holding and not_holding updates
- Forgetting to use prev_not_holding for holding update
4. What is the time complexity of the space-optimized DP solution for the Best Time -- 2 Transactions problem with input size n and fixed k=2?
medium
Solution
Step 1: Identify loops in the code
Outer loop runs n-1 times, inner loop runs k times (k=2 fixed). So total iterations ~ n*k.Step 2: Simplify complexity with fixed k
Since k=2 is constant, O(n*k) simplifies to O(n).Final Answer:
Option C -> Option CQuick Check:
Linear time due to fixed number of transactions [OK]
Hint: Fixed k means linear time, not quadratic [OK]
Common Mistakes:
- Confusing k as variable leading to O(n*k)
- Assuming nested loops always mean O(n^2)
5. Examine the following code snippet for climbing stairs:
def climb_stairs(n):
if n < 1:
return 1
first, second = 1, 1
for i in range(2, n + 1):
current = first + second
first, second = second, current
return second
medium
Solution
Step 1: Analyze base case condition
The condition 'if n < 1' returns 1 only when n is 0 or negative, but for n=1 it skips and runs the loop, which is incorrect.Step 2: Correct base case to 'if n <= 1'
This ensures for n=0 or n=1, the function returns 1 immediately, matching problem definition.Final Answer:
Option A -> Option AQuick Check:
Base case off-by-one causes wrong results for n=1 [OK]
Hint: Check base cases carefully for off-by-one errors [OK]
Common Mistakes:
- Using '<' instead of '<=' in base cases
- Incorrect loop start index