How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find earliest common meeting slot | Uber Coding Question

Quick Overview

An Uber Software Engineer onsite coding question: given N attendees' busy calendars as sorted half-open intervals plus per-attendee working hours, find the earliest time window of length d in which everyone is simultaneously free, or return -1. It covers the merge-busy/scan-gaps algorithm and complexity, then follow-ups on scaling to N participants, time zones and DST, very large fragmented inputs, clock-injection API design, and concurrency control for live calendar updates.

Find earliest common meeting slot

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question Given the calendars of `N` attendees, find the **earliest** time window of length at least `d` minutes during which **all** attendees are simultaneously free. Each attendee's calendar is a sorted list of non-overlapping, half-open **busy** intervals `[start, end)` (times in minutes since the epoch). Each attendee also has a daily **working-hours window**; a valid slot must fall inside every attendee's working hours. Return the earliest start time `t` such that every attendee is free for `d` consecutive minutes starting at `t` (equivalently, return the `[start, end)` slot). If no such slot exists, return `-1`. **Example.** - Attendee A busy: `[[60, 120), [180, 240)]`, working hours `[0, 480)` - Attendee B busy: `[[0, 90), [150, 200)]`, working hours `[30, 480)` - Required duration `d = 30` The first window of length ≥ 30 free for both inside both working windows starts at `t = 120` (A and B are both free on `[120, 150)`), so return `120`. Discuss the algorithm and its time/space complexity, then address the follow-ups below. ##### Follow-ups 1. **Multiple participants.** Generalize cleanly from 2 attendees to `N`. What changes in the algorithm and the complexity? 2. **Time zones.** Attendees may be in different time zones and have different working hours per local day. How do you normalize times and handle DST so the answer is correct? 3. **Fragmented / very large inputs.** Schedules can be highly fragmented with up to ~`1e6` total intervals. How do you keep the solution efficient, and how does fragmentation affect cost? 4. **API design for "now".** Redesign the function so it only considers free slots strictly after the current time **without** taking `now` as a parameter. Discuss injecting a monotonic clock, testability, and determinism. 5. **Concurrency.** Calendars may be updated concurrently while `find-meeting` calls execute. Describe how you keep reads consistent and writes safe (locks vs. copy-on-write vs. versioned snapshots), the data structures involved, and how you avoid starvation.

Quick Answer: An Uber Software Engineer onsite coding question: given N attendees' busy calendars as sorted half-open intervals plus per-attendee working hours, find the earliest time window of length d in which everyone is simultaneously free, or return -1. It covers the merge-busy/scan-gaps algorithm and complexity, then follow-ups on scaling to N participants, time zones and DST, very large fragmented inputs, clock-injection API design, and concurrency control for live calendar updates.

Given the calendars of `N` attendees, find the **earliest** start time `t` of a window of length at least `d` minutes during which **all** attendees are simultaneously free. Each attendee's calendar is a sorted list of non-overlapping, half-open **busy** intervals `[start, end)` (times in minutes since the epoch). Each attendee also has a daily **working-hours window** `[ws, we)`; a valid slot must fall inside **every** attendee's working hours. Return the earliest start time `t` such that every attendee is free for `d` consecutive minutes starting at `t` (the slot is `[t, t + d)`). If no such slot exists, return `-1`. **Function signature:** `solution(calendars, working_hours, d)` where `calendars[i]` is the sorted list of `[start, end)` busy intervals for attendee `i`, `working_hours[i]` is `[ws, we)` for attendee `i`, and `d` is the required duration. **Example.** - Attendee A busy: `[[60, 120], [180, 240]]`, working hours `[0, 480]` - Attendee B busy: `[[0, 90], [150, 200]]`, working hours `[30, 480]` - `d = 30` Both attendees are free on `[120, 150)`, which has length 30 inside both working windows, so the earliest valid start is `t = 120`. **Approach:** The clean reframe is to intersect all working-hour windows into a common window `W = [max(ws), min(we))`, merge every attendee's *busy* intervals (clipped to `W`) into one timeline of "someone-is-busy" blocks, then scan the gaps between consecutive busy blocks for the first gap of length `>= d`. Respect the half-open convention: intervals `[a, b)` and `[b, c)` are adjacent (not overlapping) and leave no free time at `b`. **Constraints note:** Times can be any integers (including negative epoch-minute values). An empty calendar means that attendee is free for the whole window. If the common working window is shorter than `d`, return `-1`. *(Discussion follow-ups in the original prompt — N participants, time zones/DST, ~1e6 fragmented intervals, injecting a clock for "now", and concurrent updates — are conceptual; the console verifies the core algorithm.)*

Constraints

1 <= N (number of attendees); each attendee has a working-hours window [ws, we) with ws < we
Each attendee's busy list is sorted, non-overlapping, and uses half-open [start, end) intervals
Total busy intervals M can be large (up to ~1e6 in the fragmented follow-up)
Times are integers in minutes since the epoch and may be negative
An empty calendar means that attendee is free for the entire window
Return -1 if no qualifying slot exists (including when the common working window is shorter than d)

Examples

Input: ([[[60, 120], [180, 240]], [[0, 90], [150, 200]]], [[0, 480], [30, 480]], 30)

Expected Output: 120

Explanation: Common window [30,480). Merged busy = [0..120) (A's [60,120) clipped, B's [0,90)) then [150,240). Gap [120,150) has length 30 >= d, so earliest start is 120.

Input: ([[[0, 480]]], [[0, 480]], 30)

Expected Output: -1

Explanation: The single attendee is busy for the entire working window [0,480), leaving no free gap of length 30.

Input: ([[], []], [[0, 480], [60, 300]], 60)

Expected Output: 60

Explanation: Both calendars empty so everyone is free. Common window = [60,300); the earliest 60-minute slot starts at the window start, 60.

Input: ([[[100, 200]]], [[0, 480]], 50)

Expected Output: 0

Explanation: Free gap [0,100) before the first busy block has length 100 >= 50, so the earliest slot starts at 0.

Input: ([[[0, 100]]], [[0, 480]], 50)

Expected Output: 100

Explanation: Busy [0,100) covers the window start, so the first 50-minute free slot starts right after it at 100 (gap [100,480)).

Input: ([[[60, 120]], [[120, 180]]], [[0, 480], [0, 480]], 60)

Expected Output: 0

Explanation: Merged busy = [60,180) (the two blocks touch at 120 and merge). The leading gap [0,60) has length 60 >= d, so earliest start is 0.

Input: ([[[0, 60], [120, 180]]], [[0, 200]], 60)

Expected Output: 60

Explanation: Gaps are [60,120) length 60 (qualifies) and [180,200) length 20. First qualifying gap starts at 60.

Input: ([[[0, 60], [100, 180]]], [[0, 200]], 50)

Expected Output: -1

Explanation: Gaps are [60,100) length 40 and tail [180,200) length 20; neither reaches 50, so no slot exists.

Input: ([[[0, 100]], [[50, 200]]], [[0, 250]], 40)

Expected Output: 200

Explanation: Merged busy = [0,200) (overlapping blocks merge). Only free gap is the tail [200,250) length 50 >= 40, so earliest start is 200.

Input: ([[]], [[0, 100]], 100)

Expected Output: 0

Explanation: Empty calendar, common window exactly [0,100) length 100 == d, so the whole window is the slot starting at 0.

Input: ([[]], [[0, 100]], 101)

Expected Output: -1

Explanation: Common window length 100 is shorter than the required 101 minutes, so return -1.

Input: ([[[-50, -10]]], [[-100, 0]], 30)

Expected Output: -100

Explanation: Negative epoch-minute times. Leading gap [-100,-50) has length 50 >= 30, so the earliest slot starts at -100.

Hints

Intersect all working-hour windows first: the feasible region is W = [max(ws), min(we)). If W is empty or shorter than d, return -1 immediately.
Don't intersect free intervals pairwise across attendees — instead merge all attendees' busy intervals into one sorted timeline, then look at the gaps between consecutive busy blocks.
Walk left to right tracking prev_end (start it at W.start). The first busy block whose start minus prev_end is >= d gives the answer prev_end. Remember to check the tail gap [last_end, W.end) too.
Half-open matters: busy [a, b) followed by busy [b, c) are adjacent, not overlapping, and leave no free time at b — so treat touching blocks as merged and never report a zero-length slot.

Quick Overview

Find earliest common meeting slot

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Constraints

1 <= N (number of attendees); each attendee has a working-hours window [ws, we) with ws < we
Each attendee's busy list is sorted, non-overlapping, and uses half-open [start, end) intervals
Total busy intervals M can be large (up to ~1e6 in the fragmented follow-up)
Times are integers in minutes since the epoch and may be negative
An empty calendar means that attendee is free for the entire window
Return -1 if no qualifying slot exists (including when the common working window is shorter than d)

Examples

Input: ([[[60, 120], [180, 240]], [[0, 90], [150, 200]]], [[0, 480], [30, 480]], 30)

Expected Output: 120

Explanation: Common window [30,480). Merged busy = [0..120) (A's [60,120) clipped, B's [0,90)) then [150,240). Gap [120,150) has length 30 >= d, so earliest start is 120.

Input: ([[[0, 480]]], [[0, 480]], 30)

Expected Output: -1

Explanation: The single attendee is busy for the entire working window [0,480), leaving no free gap of length 30.

Input: ([[], []], [[0, 480], [60, 300]], 60)

Expected Output: 60

Explanation: Both calendars empty so everyone is free. Common window = [60,300); the earliest 60-minute slot starts at the window start, 60.

Input: ([[[100, 200]]], [[0, 480]], 50)

Expected Output: 0

Explanation: Free gap [0,100) before the first busy block has length 100 >= 50, so the earliest slot starts at 0.

Input: ([[[0, 100]]], [[0, 480]], 50)

Expected Output: 100

Explanation: Busy [0,100) covers the window start, so the first 50-minute free slot starts right after it at 100 (gap [100,480)).

Input: ([[[60, 120]], [[120, 180]]], [[0, 480], [0, 480]], 60)

Expected Output: 0

Explanation: Merged busy = [60,180) (the two blocks touch at 120 and merge). The leading gap [0,60) has length 60 >= d, so earliest start is 0.

Input: ([[[0, 60], [120, 180]]], [[0, 200]], 60)

Expected Output: 60

Explanation: Gaps are [60,120) length 60 (qualifies) and [180,200) length 20. First qualifying gap starts at 60.

Input: ([[[0, 60], [100, 180]]], [[0, 200]], 50)

Expected Output: -1

Explanation: Gaps are [60,100) length 40 and tail [180,200) length 20; neither reaches 50, so no slot exists.

Input: ([[[0, 100]], [[50, 200]]], [[0, 250]], 40)

Expected Output: 200

Explanation: Merged busy = [0,200) (overlapping blocks merge). Only free gap is the tail [200,250) length 50 >= 40, so earliest start is 200.

Input: ([[]], [[0, 100]], 100)

Expected Output: 0

Explanation: Empty calendar, common window exactly [0,100) length 100 == d, so the whole window is the slot starting at 0.

Input: ([[]], [[0, 100]], 101)

Expected Output: -1

Explanation: Common window length 100 is shorter than the required 101 minutes, so return -1.

Input: ([[[-50, -10]]], [[-100, 0]], 30)

Expected Output: -100

Explanation: Negative epoch-minute times. Leading gap [-100,-50) has length 50 >= 30, so the earliest slot starts at -100.

Hints

Intersect all working-hour windows first: the feasible region is W = [max(ws), min(we)). If W is empty or shorter than d, return -1 immediately.
Don't intersect free intervals pairwise across attendees — instead merge all attendees' busy intervals into one sorted timeline, then look at the gaps between consecutive busy blocks.
Walk left to right tracking prev_end (start it at W.start). The first busy block whose start minus prev_end is >= d gives the answer prev_end. Remember to check the tail gap [last_end, W.end) too.
Half-open matters: busy [a, b) followed by busy [b, c) are adjacent, not overlapping, and leave no free time at b — so treat touching blocks as merged and never report a zero-length slot.