Listing Windows: Find All Time Windows Where Active Listings Exceed a Threshold
Interview Experience
Problem
You have a list of marketplace listings, each with a start_date and end_date. Find all contiguous time windows where the number of simultaneously active listings is strictly greater than a threshold k.
Return each window as (start, end) with the peak count.
python
def find_busy_windows(
listings: list[tuple[int, int]], # (start_day, end_day) inclusive
k: int
) -> list[dict]:
**Return** [{"start": int, "end": int, "peak": int}]
pass
Example:
listings = [(1,5),(2,8),(4,6),(9,12)]
k = 2
At day 2-5: 3 active (listings 1,2,3 overlap here at peak)
At day 6-8: 2 active
k=2 means strictly > 2, so only days 2-5 qualify with peak=3
Output: [{"start": 2, "end": 5, "peak": 3}]
Approach
Use a sweep line: create events (day, +1) for starts and (day, -1) for ends, sort by day, sweep to track active count, then merge contiguous windows above threshold.
Follow-ups
- What is the time complexity of the sweep line approach?
- How does your answer change if listings can have fractional (hourly) durations?
- If the threshold itself varies by day of week, how do you adapt the sweep?
- How would you express this query in SQL using window functions?
Full Details
Problem
You have a list of marketplace listings, each with a start_date and end_date. Find all contiguous time windows where the number of simultaneously active listings is strictly greater than a threshold k.
Return each window as (start, end) with the peak count.
python
def find_busy_windows(
listings: list[tuple[int, int]], # (start_day, end_day) inclusive
k: int
) -> list[dict]:
**Return** [{"start": int, "end": int, "peak": int}]
pass
Example:
listings = [(1,5),(2,8),(4,6),(9,12)]
k = 2
At day 2-5: 3 active (listings 1,2,3 overlap here at peak)
At day 6-8: 2 active
k=2 means strictly > 2, so only days 2-5 qualify with peak=3
Output: [{"start": 2, "end": 5, "peak": 3}]
Approach
Use a sweep line: create events (day, +1) for starts and (day, -1) for ends, sort by day, sweep to track active count, then merge contiguous windows above threshold.
Follow-ups
- What is the time complexity of the sweep line approach?
- How does your answer change if listings can have fractional (hourly) durations?
- If the threshold itself varies by day of week, how do you adapt the sweep?
- How would you express this query in SQL using window functions?
About This Question
This is a candidate experience report from a stubhub interview during the phone round.