Find available reservation time slots
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
You are building an API to show which time slots are available for booking at a restaurant.
You are given:
- The restaurant’s **opening hours** (per day), and
- A list of **existing reservations** (per day), each with a start and end time.
Opening hours and reservations are provided in a **nested dictionary** structure.
### Input
Assume times are in the same timezone and represented as minutes-from-midnight or as `HH:MM` strings that can be converted to minutes.
- `hours[day] = [open_time, close_time]`
- `reservations[day] = [[start1, end1], [start2, end2], ...]`
Example shape:
```python
hours = {
"Mon": ["11:00", "22:00"],
"Tue": ["11:00", "22:00"],
}
reservations = {
"Mon": [["12:00", "12:30"], ["18:00", "19:15"]],
"Tue": [],
}
```
### Task
Write a function that returns, for each day, the list of **available time intervals** within opening hours that are not blocked by existing reservations.
Clarify/handle these cases:
- Reservations may be unsorted.
- Reservations may touch endpoints (e.g., one ends at 13:00 and another starts at 13:00).
- If reservations overlap, they should be merged before computing availability.
### Output
Return a nested dictionary:
- `available[day] = [[free_start1, free_end1], [free_start2, free_end2], ...]`
(Optionally, if a booking duration `D` minutes is provided, return only free intervals of length `>= D`, or return discrete start times valid for a `D`-minute reservation—state your choice.)
Quick Answer: This question evaluates a candidate's ability to reason about time-interval data and temporal normalization, testing competencies in interval manipulation, conflict detection, and algorithmic problem-solving for scheduling contexts.
You are building an API for a restaurant booking system. Given the restaurant's opening hours for each day and a list of existing reservations for each day, return the free time intervals that remain available for booking.
For each day in `hours`, compute the gaps inside that day's opening interval after accounting for reservations.
Rules:
- Reservations for a day may be unsorted.
- Overlapping reservations must be merged.
- Reservations that touch at endpoints (for example, one ends at `13:00` and another starts at `13:00`) should be treated as one continuous blocked interval.
- If a reservation falls partially outside opening hours, only the overlapping portion inside opening hours matters.
- If a day exists in `hours` but not in `reservations`, treat it as having no reservations.
- If `duration` is provided, return only free intervals whose length is at least `duration` minutes.
Times may be given as `HH:MM` strings or as integer minutes-from-midnight. Return all output times as `HH:MM` strings.
Constraints
- 0 <= number of days in `hours` <= 7
- 0 <= total number of reservations across all days <= 10^4
- Each day in `hours` has exactly one opening interval with open_time < close_time
- Each reservation has start_time < end_time before clamping
- `duration` is either `None` or an integer between 1 and 1440
Examples
Input: ({'Mon': ['11:00', '22:00'], 'Tue': ['11:00', '22:00']}, {'Mon': [['12:00', '12:30'], ['18:00', '19:15']], 'Tue': []})
Expected Output: {'Mon': [['11:00', '12:00'], ['12:30', '18:00'], ['19:15', '22:00']], 'Tue': [['11:00', '22:00']]}
Explanation: Monday has two blocked intervals, so the free time is before, between, and after them. Tuesday has no reservations, so the whole opening interval is free.
Input: ({'Wed': ['09:00', '17:00']}, {'Wed': [['13:00', '14:00'], ['09:30', '10:30'], ['10:30', '11:00'], ['12:00', '13:30'], ['08:00', '09:15']]})
Expected Output: {'Wed': [['09:15', '09:30'], ['11:00', '12:00'], ['14:00', '17:00']]}
Explanation: The reservations are unsorted. After clamping and merging, the blocked intervals are [09:00, 09:15], [09:30, 11:00], and [12:00, 14:00]. The gaps between them are the available slots.
Hints
- For each day, sort the reservations by start time and merge any intervals that overlap or touch.
- After merging, walk from opening time to closing time and collect the gaps between blocked intervals.