Practice
1. Given the following code snippet for finding employee free time, what is the final output when the input schedule is [[[1,2],[5,6]], [[1,3]], [[4,10]]]?
from typing import List
def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
intervals = [iv for employee in schedule for iv in employee]
intervals.sort(key=lambda x: x[0])
free_times = []
prev_end = intervals[0][1]
for i in range(1, len(intervals)):
start, end = intervals[i]
if start > prev_end:
free_times.append([prev_end, start])
prev_end = max(prev_end, end)
return free_times
schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]
print(employeeFreeTime(schedule))
easy
Solution
Step 1: Sort all intervals
Flattened intervals: [1,2], [5,6], [1,3], [4,10]. Sorted by start: [1,2], [1,3], [4,10], [5,6].Step 2: Merge intervals and find gaps
Initialize prev_end=2. Iterate: - Interval [1,3]: start=1 ≤ prev_end=2, update prev_end=max(2,3)=3 - Interval [4,10]: start=4 > prev_end=3, gap [3,4] added, update prev_end=10 - Interval [5,6]: start=5 ≤ prev_end=10, update prev_end=max(10,6)=10 Return free_times=[[3,4]].Final Answer:
Option D -> Option DQuick Check:
Only one gap between merged intervals is [3,4] [OK]
Hint: Sort intervals and track max end to find gaps [OK]
Common Mistakes:
- Off-by-one errors in gap detection
- Including zero-length intervals
- Incorrect sorting leading to wrong gaps
2. You need to continuously receive numbers from a stream and efficiently find the median after each insertion. Which approach guarantees an optimal solution with O(log n) insertion and O(1) median retrieval?
easy
Solution
Step 1: Understand the problem constraints
The problem requires efficient insertion and median retrieval from a data stream.Step 2: Evaluate approaches
Sorting after each insertion is O(n log n), too slow. A balanced BST can do insertions in O(log n) but median retrieval is not O(1). Using a single min-heap cannot separate lower and upper halves, so median calculation is incorrect. Maintaining two heaps (max-heap for lower half, min-heap for upper half) allows O(log n) insertion and O(1) median retrieval by balancing sizes.Final Answer:
Option A -> Option AQuick Check:
Two heaps balance halves for median -> [OK]
Hint: Two heaps balance halves for median retrieval [OK]
Common Mistakes:
- Sorting entire list each time is too slow
- Using one heap cannot separate halves
- Assuming balanced BST gives O(1) median retrieval
3. You are given a list of intervals, each with a start and end time. For each interval, you want to find the interval with the smallest start time that is greater than or equal to the end time of the current interval. Which approach guarantees an optimal solution in terms of time complexity?
easy
Solution
Step 1: Understand problem requirements
The problem requires finding, for each interval, the next interval with the smallest start time ≥ current interval's end time.Step 2: Evaluate approaches
Brute force (nested loops) is correct but inefficient (O(n²)). Sorting + binary search is efficient but requires extra steps. The two max-heaps approach efficiently tracks max starts and ends to find next intervals in O(n log n) time, guaranteeing optimality.Final Answer:
Option A -> Option AQuick Check:
Two heaps approach matches the problem's need for efficient next interval lookup [OK]
Hint: Two heaps efficiently track max starts and ends [OK]
Common Mistakes:
- Assuming greedy earliest finish works
- Using DP unnecessarily
- Brute force accepted as optimal
4. If the data stream allows removal of arbitrary elements (not just the median), which modification to the balanced two heaps approach is necessary to maintain efficient median retrieval?
hard
Solution
Step 1: Understand removal challenges
Removing arbitrary elements from heaps is not efficient since heaps do not support O(log n) arbitrary removals.Step 2: Evaluate solutions
Rebuilding heaps each removal is O(n log n), too slow. Balanced BST supports removals but is more complex and median retrieval is not O(1). Sorted list has O(n) insertion/removal. Lazy removal uses a delayed dictionary to mark elements for removal and prunes them lazily during heap operations, maintaining O(log n) amortized complexity.Final Answer:
Option A -> Option AQuick Check:
Lazy removal enables efficient arbitrary removals -> [OK]
Hint: Lazy removal with delayed map enables efficient arbitrary removals [OK]
Common Mistakes:
- Rebuilding heaps after each removal is inefficient
- Assuming heaps support O(log n) arbitrary removals directly
- Switching to balanced BST loses O(1) median retrieval
5. Suppose projects can be selected multiple times (reused) in the IPO problem. Which modification to the two-heaps algorithm correctly handles this scenario?
hard
Solution
Step 1: Understand reuse implication
Allowing reuse means projects remain available after selection, so they must be reinserted to be considered again.Step 2: Modify algorithm accordingly
After popping a project from min-capital heap and selecting it, reinsert it to allow future reuse; otherwise, it disappears from consideration.Final Answer:
Option C -> Option CQuick Check:
Reinserting projects enables multiple selections [OK]
Hint: Reinsert projects after selection to allow reuse [OK]
Common Mistakes:
- Ignoring reinsertion, losing projects after first pick
- Keeping all projects always available breaks capital filtering
- Ignoring capital constraints when reusing projects