Top 3 Sweep line Interview Questions
Browse 3 real-world technical and behavioral interview questions about Sweep line. Review scenarios, edge cases, and architectural best practices.
Given everyone's busy calendar, find the slots when all of them are free. What do you sort, and what breaks at the boundaries?
Pool every busy interval, sort by start, and sweep with a cursor marking the end of the busy block so far. Any start beyond the cursor opens a common free slot. Use half-open intervals so back-to-back meetings leave no zero-length gap, and clip to the working day. Sorting costs O(N log N), or O(N log k) with a heap.
Merge a list of overlapping intervals, and justify the key you sorted by
Sorting by start time is what reduces the merge to a single scan carrying one scalar, the end of the open block; sorting by end breaks it, and sorting by end is instead correct for maximum non-overlapping selection. Both run in O(n log n), and equal timestamps decide the answer.
Given a list of meetings with start and end times, tell me the minimum number of rooms needed to hold all of them.
The answer is the maximum number of meetings running at once, found by sweeping the start and end times in sorted order and tracking a running count. The starts and ends can be sorted independently of each other, and a meeting ending exactly when another begins must free its room or you will overcount.