Recommended
Practice
1. You have a list of children each with a greed factor and a list of cookies each with a size. You want to assign cookies to children so that each child gets at most one cookie and the cookie size is at least the child's greed factor. Which algorithmic approach guarantees the maximum number of content children?
easy
Solution
Step 1: Understand problem constraints
Each child can get at most one cookie, and the cookie must satisfy the child's greed factor.Step 2: Identify optimal approach
Sorting both greed and cookie arrays allows a greedy assignment from smallest greed to smallest sufficient cookie, ensuring maximum matches.Final Answer:
Option A -> Option AQuick Check:
Greedy sorting approach is classic for assignment problems [OK]
Hint: Sort both arrays and assign greedily [OK]
Common Mistakes:
- Thinking brute force is needed for optimality
- Assuming DP is required
- Ignoring sorting leads to suboptimal matches
2. You have a list of tasks represented by characters, each task takes 1 unit of time to execute. The CPU must wait for at least
n units of time before executing the same task again. Which approach guarantees the minimum total time to finish all tasks?easy
Solution
Step 1: Understand the cooldown constraint
The CPU must waitnunits before repeating the same task, so scheduling must consider task frequencies and cooldowns.Step 2: Why max-heap greedy works best
Using a max-heap prioritizes tasks with the highest remaining frequency, ensuring minimal idle time by always picking the most urgent task available.Final Answer:
Option B -> Option BQuick Check:
Max-heap approach matches known optimal solution [OK]
Hint: Max-heap greedily schedules highest frequency tasks first [OK]
Common Mistakes:
- Assuming DP or brute force is needed
- Ignoring cooldown leads to incorrect minimal time
- Greedy without priority queue misses optimal order
3. Identify the bug in the following code snippet for Two City Scheduling:
def twoCitySchedCost(costs):
costs.sort(key=lambda x: abs(x[0] - x[1]))
n = len(costs) // 2
total = 0
for i, cost in enumerate(costs):
if i < n:
total += cost[0]
else:
total += cost[1]
return total
medium
Solution
Step 1: Analyze sorting key
The code sorts by absolute difference abs(cost[0] - cost[1]) instead of signed difference cost[0] - cost[1].Step 2: Effect of wrong sorting
Sorting by absolute difference loses the direction of cost preference, causing suboptimal assignments and higher total cost.Final Answer:
Option A -> Option AQuick Check:
Signed difference sorting is required for correct greedy assignment [OK]
Hint: Sort by signed difference, not absolute [OK]
Common Mistakes:
- Sorting by absolute difference
- Miscounting half the people
- Swapping city costs in assignment
4. Suppose the problem changes: you can reuse indices multiple times (cycles allowed). Which modification to the BFS approach ensures correct minimum jumps without infinite loops?
hard
Solution
Step 1: Understand cycles and revisits
Allowing reuse means indices can be revisited, so visited set alone blocks better paths.Step 2: Use distance array for shortest paths
Tracking minimum jumps per index and updating when a shorter path is found prevents infinite loops and finds optimal jumps.Step 3: Why other options fail
Removing visited causes infinite loops; resetting visited loses pruning; keeping visited blocks revisits.Final Answer:
Option D -> Option DQuick Check:
Distance array with updates handles cycles correctly [OK]
Hint: Distance array needed when revisits allowed [OK]
Common Mistakes:
- Removing visited set causing infinite loops
- Resetting visited incorrectly
- Assuming original BFS works unchanged
5. Suppose the wiggle subsequence problem is modified so that elements can be reused multiple times in the subsequence (i.e., repeated picks allowed). Which of the following statements about adapting the optimal greedy algorithm is correct?
hard
Solution
Step 1: Understand reuse impact
Allowing reuse means subsequence elements can repeat, changing the problem fundamentally and invalidating the original greedy assumptions.Step 2: Identify correct adaptation
Greedy approach relies on strictly alternating differences without reuse; to handle reuse, a dynamic programming approach that tracks states and counts is needed.Final Answer:
Option D -> Option DQuick Check:
Reuse requires more complex state tracking than greedy allows [OK]
Hint: Reuse breaks greedy assumptions; DP needed
Common Mistakes:
- Assuming greedy still works
- Thinking reuse is trivial
- Ignoring problem definition changes