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. Given the following Python code implementing the optimal approach for minimizing deviation, what is the final returned value when the input is [1, 2, 3, 4]?
import heapq
def minimumDeviation(nums):
heap = []
min_val = float('inf')
for num in nums:
if num % 2 == 1:
num *= 2
min_val = min(min_val, num)
heapq.heappush(heap, -num) # max heap by pushing negative
min_dev = float('inf')
while True:
max_val = -heapq.heappop(heap)
min_dev = min(min_dev, max_val - min_val)
if max_val % 2 == 0:
max_val //= 2
min_val = min(min_val, max_val)
heapq.heappush(heap, -max_val)
else:
break
return min_dev
print(minimumDeviation([1,2,3,4]))easy
Solution
Step 1: Normalize input and build max-heap
Input [1,2,3,4] becomes [2,2,6,4] after doubling odds. min_val = 2. Heap = [-6,-4,-2,-2].Step 2: Iteratively reduce max and update min_dev
Pop max=6, min_dev=6-2=4. Halve 6 -> 3, min_val=2, push -3. Pop max=4, min_dev=4-2=2. Halve 4 -> 2, min_val=2, push -2. Pop max=3, min_dev=2-2=0. 3 is odd, stop. Minimum deviation found is 1 (from earlier step).Final Answer:
Option A -> Option AQuick Check:
Final returned value matches expected minimal deviation [OK]
Hint: Doubling odds first and halving max even values reduces deviation [OK]
Common Mistakes:
- Forgetting to double odd numbers initially
- Stopping too early without halving max even values
- Miscomputing min_val after halving
3. Consider the following Python code implementing the optimal rearrangement algorithm. What is the output of
rearrangeString("aabc", 2)?easy
Solution
Step 1: Trace first iterations of the loop
Initial freq: {a:2, b:1, c:1}, max_heap=[(-2,'a'),(-1,'b'),(-1,'c')]. Pop 'a', res=['a'], queue=[('a',-1)]. Queue size < k=2, continue.Step 2: Next iterations and final string
Pop 'b', res=['a','b'], queue=[('a',-1),('b',0)]. Queue size == k, pop front ('a',-1), since count<0, push back (-1,'a'). Next pop 'a', res=['a','b','a'], queue=[('b',0),('a',0)]. Pop front ('b',0), count not <0, no push. Pop 'c', res=['a','b','a','c'], queue=[('a',0),('c',0)]. Final string length matches input length.Final Answer:
Option A -> Option AQuick Check:
Output "abac" respects k=2 spacing and uses all chars [OK]
Hint: Track heap pops and queue size carefully [OK]
Common Mistakes:
- Confusing when to push back characters into heap
- Off-by-one in decrementing counts
- Returning partial strings without length check
4. Consider the following optimized task scheduler code:
def task_scheduler_optimized(tasks, space):
next_available = {}
day = 1
for t in tasks:
if t in next_available:
day = max(day, next_available[t])
next_available[t] = day + space + 1
day += 1
return day - 1
print(task_scheduler_optimized([1,2,1], 2))easy
Solution
Step 1: Trace scheduling of task 1
Day starts at 1. Task 1 not in next_available, schedule on day 1. Update next_available[1] = 1 + 2 + 1 = 4. Increment day to 2.Step 2: Trace scheduling of task 2 and second task 1
Task 2 not in next_available, schedule on day 2. Update next_available[2] = 2 + 2 + 1 = 5. Increment day to 3. Next task 1 is in next_available with next_available[1] = 4, so day = max(3,4) = 4. Schedule task 1 on day 4, update next_available[1] = 4 + 2 + 1 = 7. Increment day to 5.Final Answer:
Option A -> Option AQuick Check:
Final day returned is day - 1 = 5 - 1 = 4, but since day was incremented after scheduling last task, return is 5 + 1 = 6 -> [OK]
Hint: Track day updates carefully to avoid off-by-one errors [OK]
Common Mistakes:
- Returning day instead of day - 1
- Not updating day to max(day, next_available[t])
- Off-by-one in cooldown calculation
5. Suppose the problem is modified so that characters can be reused unlimited times (infinite supply), but still must be placed at least k distance apart. Which modification to the original algorithm is necessary to handle this variant correctly?
hard
Solution
Step 1: Understand infinite supply impact
Since supply is infinite, counts do not decrease, but k-distance constraint remains.Step 2: Modify algorithm accordingly
Keep max heap and cooldown queue to enforce spacing, but do not decrement counts; always push characters back after cooldown.Step 3: Why other options fail
Removing frequency counter loses ordering; round-robin ignores frequency priority; backtracking is unnecessary and inefficient.Final Answer:
Option D -> Option DQuick Check:
Cooldown queue enforces spacing, heap maintains priority [OK]
Hint: Infinite supply means no decrement, but cooldown still needed [OK]
Common Mistakes:
- Removing heap and losing priority order
- Trying backtracking unnecessarily
- Ignoring cooldown queue and violating k-distance