Recommended
Practice
1. Consider the following Python function for interval intersections:
from typing import List
def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
result = []
while i < len(A) and j < len(B):
if A[i][1] < B[j][0]:
i += 1
elif B[j][1] < A[i][0]:
j += 1
else:
start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
result.append([start, end])
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(intervalIntersection(A, B))
easy
Solution
Step 1: Trace first intersection
Compare [0,2] and [1,5]: overlap is [1,2], add to result.Step 2: Advance pointers and find all intersections
Following pointer moves and overlaps yield [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].Final Answer:
Option D -> Option DQuick Check:
Matches manual step-by-step intersection results [OK]
Hint: Trace pointer increments carefully to avoid off-by-one errors [OK]
Common Mistakes:
- Including intervals beyond intersection
- Merging adjacent but non-overlapping intervals
- Off-by-one in pointer increments
2. What is the time complexity of the optimal car pooling solution using the difference array and prefix sum approach, given n trips and maximum location L?
medium
Solution
Step 1: Analyze trip processing
Each of the n trips updates two positions in the difference array -> O(n)Step 2: Analyze prefix sum sweep
We iterate over the difference array of size L once -> O(L)Final Answer:
Option B -> Option BQuick Check:
Sum of O(n) + O(L) operations [OK]
Hint: Difference array updates O(n), prefix sum O(L) [OK]
Common Mistakes:
- Confusing brute force O(n*L) with optimal
- Assuming sorting is required
- Ignoring prefix sum sweep cost
3. What is the time complexity of the optimal sweep line algorithm for Employee Free Time, given N total intervals across all employees?
medium
Solution
Step 1: Identify main operations
We create 2N events (start and end per interval) and sort them.Step 2: Sorting events dominates complexity
Sorting 2N events takes O(N log N). The sweep through events is O(N).Final Answer:
Option A -> Option AQuick Check:
Sorting dominates, so O(N log N) [OK]
Hint: Sorting interval endpoints dominates time complexity [OK]
Common Mistakes:
- Assuming linear time because each interval processed once
4. The following code attempts to determine if a person can attend all meetings. Identify the line containing the subtle bug that causes incorrect results for intervals that just touch (e.g., [1,5] and [5,10]).
from typing import List
def can_attend_meetings(intervals: List[List[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
end = float('-inf')
for interval in intervals:
if interval[0] <= end:
return False
end = interval[1]
return True
medium
Solution
Step 1: Understand the overlap condition
Meetings that just touch (e.g., end=5 and start=5) should not be considered overlapping.Step 2: Identify the bug
The condition uses <= which incorrectly treats touching intervals as overlapping. It should use < instead.Final Answer:
Option A -> Option AQuick Check:
Changing <= to < fixes false positives on touching intervals [OK]
Hint: Overlap check must use <, not <= [OK]
Common Mistakes:
- Using <= causes false overlap detection on touching intervals
5. Examine the following buggy code for the Meeting Rooms II problem. Which line contains the subtle bug that can cause incorrect room count?
medium
Solution
Step 1: Identify missing sorting.
Intervals must be sorted by start time before heap processing; missing this breaks heap logic.Step 2: Confirm other lines.
Empty check is present; condition >= is correct for allowing room reuse; pushing after popping is correct.Final Answer:
Option D -> Option DQuick Check:
Without sorting, heap logic fails to track earliest ending meeting [OK]
Hint: Heap logic requires sorted intervals by start time [OK]
Common Mistakes:
- Confusing overlap condition with <=
- Forgetting to sort intervals
- Misordering heap push/pop