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 role is this question designed for?

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

Find Any Available Meeting Room | Uber Coding Question

Find Any Available Meeting Room

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Onsite

You are given multiple meeting rooms. For each room, the existing bookings are represented as a list of non-overlapping time intervals sorted by start time. Each interval is half-open: `[start, end)`. Given a new meeting interval `[s, e)`, return the identifier of **any** room where the new meeting can be inserted without overlapping an existing booking. If multiple rooms are valid, returning the first valid one is acceptable. If no room can hold the meeting, return `-1`. A booking `[s, e)` can be inserted into a room if it does not overlap any existing interval in that room. Example: - Room 0: `[[1, 3], [5, 7]]` - Room 1: `[[2, 4], [8, 10]]` - New meeting: `[3, 5)` - Valid answer: `0` Design an efficient algorithm. A straightforward solution may check rooms one by one, but within each room you should avoid scanning every existing meeting if the room's bookings are already sorted.

Quick Answer: This question evaluates a candidate's competence in handling interval-based scheduling problems, specifically managing interval data and performing efficient searches within sorted bookings to detect potential overlaps.

You are given multiple meeting rooms. Room i has a schedule represented by a list of non-overlapping booking intervals sorted by start time. Each interval is half-open: [start, end), so two meetings that only touch at an endpoint do not overlap. Given a new meeting interval [s, e), return the identifier of the first room (smallest index) where the meeting can be inserted without overlapping any existing booking. If no room can hold the meeting, return -1. You should design an efficient algorithm: rooms may be checked one by one, but inside each room you should use the fact that its bookings are already sorted instead of scanning every booking linearly.

Constraints

0 <= len(rooms) <= 10^5
0 <= total number of existing bookings across all rooms <= 2 * 10^5
Each booking interval satisfies start < end
Each room's bookings are sorted by start time and do not overlap
-10^9 <= start < end <= 10^9 for all times

Examples

Input: ([[[1, 3], [5, 7]], [[2, 4], [8, 10]]], [3, 5])

Expected Output: 0

Explanation: In room 0, [3, 5) fits exactly between [1, 3) and [5, 7) because touching endpoints is allowed.

Input: ([[[1, 2], [4, 6]], [], [[0, 10]]], [2, 4])

Expected Output: 0

Explanation: The new meeting fits exactly in the gap of room 0. Although room 1 is also empty, the first valid room index is 0.

Input: ([[[1, 4]], [], [[0, 10]]], [2, 3])

Expected Output: 1

Explanation: Room 0 overlaps with [1, 4). Room 1 has no bookings, so it is the first valid room.

Input: ([[[1, 5]], [[5, 8]]], [2, 3])

Expected Output: 1

Explanation: Room 0 overlaps with [1, 5). In room 1, the meeting ends exactly when the existing booking starts, so it fits.

Input: ([[[1, 3], [6, 9]], [[0, 2], [3, 5]]], [2, 6])

Expected Output: -1

Explanation: The new meeting overlaps an existing booking in both rooms, so no room can hold it.

Input: ([], [1, 2])

Expected Output: -1

Explanation: There are no rooms at all.

Input: ([[[-5, -3], [0, 2]], [[-1, 1]]], [-3, 0])

Expected Output: 0

Explanation: In room 0, the meeting touches the end of the first booking and the start of the second booking, which is allowed for half-open intervals.

Hints

For one room, think about where the new interval would be inserted if you kept the bookings sorted by start time.
After finding that insertion position with binary search, you only need to check the neighboring intervals, not every interval in the room.

Quick Overview

This question evaluates a candidate's competence in handling interval-based scheduling problems, specifically managing interval data and performing efficient searches within sorted bookings to detect potential overlaps.