Practice
1. Consider the following code snippet for counting arithmetic subsequences. What is the final returned value when the input is
[1, 3, 5]?easy
Solution
Step 1: Trace dp and total for input [1,3,5]
i=1,j=0: diff=2, dp[1][2]=0+1=1, total+=0=0; i=2,j=0: diff=4, dp[2][4]=0+1=1, total+=0=0; i=2,j=1: diff=2, dp[2][2]=dp[1][2]+1=1+1=2, total+=dp[1][2]=1Step 2: Calculate final total
Total after all iterations is 1, representing one arithmetic subsequence of length ≥ 3: [1,3,5].Final Answer:
Option A -> Option AQuick Check:
Only one arithmetic subsequence of length ≥ 3 exists [OK]
Hint: Only subsequences length ≥3 count; pairs add to dp but not total [OK]
Common Mistakes:
- Counting pairs as arithmetic subsequences
- Adding dp[i][diff] to total instead of dp[j][diff]
2. What is the time complexity of the space optimized bitmask DP solution for counting ways to assign unique caps to
n people, where caps range up to 100 and each person has a list of caps they can wear?medium
Solution
Step 1: Identify loops in the algorithm
The outer loop iterates over caps (up to 100), the middle loop iterates over all masks (2^n), and the inner loop iterates over persons (up to n) who can wear the current cap.Step 2: Combine loop complexities
Multiplying these gives O(100 * 2^n * n). Other options either omit the cap factor or incorrectly exponentiate caps.Final Answer:
Option B -> Option BQuick Check:
Counting all masks and caps with person checks matches O(100 * 2^n * n) [OK]
Hint: Count loops: caps * masks * persons per cap [OK]
Common Mistakes:
- Ignoring caps loop
- Confusing n with cap count
- Forgetting inner loop over persons
3. Consider the following buggy code for the House Robber III problem. Which line contains the subtle bug that causes incorrect results on some inputs?
def rob(root):
def dfs(node):
if not node:
return (0, 0) # (not_rob, rob)
left = dfs(node.left)
right = dfs(node.right)
rob_node = node.val + left[1] + right[1] # Bug here
not_rob_node = max(left) + max(right)
return (not_rob_node, rob_node)
return max(dfs(root))medium
Solution
Step 1: Understand rob_node calculation
When robbing current node, children cannot be robbed, so we must add left[0] and right[0] (not_rob values).Step 2: Identify bug
The code incorrectly adds left[1] and right[1] (rob values), causing double counting and invalid solutions.Final Answer:
Option B -> Option BQuick Check:
Correct rob_node uses not_rob children sums [OK]
Hint: Robbing node requires adding children's not_rob values [OK]
Common Mistakes:
- Mixing rob and not_rob indices in tuple
4. What is the time complexity of the optimized LIS algorithm using binary search on an input array of length n?
medium
Solution
Step 1: Identify outer loop complexity
The algorithm iterates over all n elements once, so at least O(n).Step 2: Identify inner operation complexity
For each element, binary search on tails array takes O(log n) time.Final Answer:
Option A -> Option AQuick Check:
n iterations x log n binary search -> O(n log n) [OK]
Hint: Binary search inside loop gives n log n [OK]
Common Mistakes:
- Assuming O(n²) because of nested loops
- Ignoring binary search complexity
- Confusing with brute force exponential
5. Examine the following buggy code snippet for shortest path visiting all nodes. Which line contains the subtle bug that can cause incorrect results or infinite loops?
medium
Solution
Step 1: Identify how visited nodes are tracked
Visited nodes are represented by a bitmask. To add a visited node, bitwise OR (|) must be used.Step 2: Spot the incorrect bitmask operation
The code uses XOR (^) instead of OR (|) to update next_mask, which can incorrectly unset bits and cause wrong states or infinite loops.Final Answer:
Option B -> Option BQuick Check:
Using XOR breaks the visited set semantics [OK]
Hint: Visited mask update must use OR, not XOR [OK]
Common Mistakes:
- Using XOR instead of OR for mask update
- Forgetting to initialize dp base cases
- Not checking dp[u][mask] == inf before continuing