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 hard 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.

Schedule Non-Overlapping Meetings Efficiently

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Implement a meeting scheduler that stores meetings as half-open intervals `[start, end)`, where `start` and `end` are integer timestamps and `start < end`. The scheduler must support: 1. `book(start, end) -> bool`: Add the meeting if it does not overlap with any existing meeting. Return `true` if the meeting is booked, otherwise return `false` and leave the schedule unchanged. 2. `remove_before(time) -> int`: Given a cutoff timestamp, remove all meetings that end at or before `time`. Return the number of removed meetings. 3. `get_meetings() -> List[Tuple[int, int]]`: Return all currently scheduled meetings sorted by start time. Follow-up discussion: - What data structure would you use to optimize `book` and `remove_before`? - How would the complexity change if you used an unsorted list, a sorted array, or a balanced binary search tree? - What edge cases should be covered by tests? Example: ```text book(10, 20) -> true book(20, 30) -> true # Adjacent meetings are allowed. book(15, 25) -> false # Overlaps with [10, 20). book(5, 10) -> true remove_before(20) -> 2 # Removes [5, 10) and [10, 20). get_meetings() -> [(20, 30)] ``` Assume the number of meetings can be large, so the solution should be efficient.

Quick Answer: This question evaluates understanding of interval scheduling and overlap detection, proficiency in selecting efficient data structures for dynamic ordered intervals, and the ability to reason about algorithmic time and space complexity.

You are given a sequence of scheduler operations for meetings stored as half-open intervals [start, end), where start and end are integers and start < end. Adjacent meetings are allowed, so [10, 20) and [20, 30) do not overlap. Process the operations in order while maintaining the current schedule. Each operation is one of: - ("book", start, end): Add the meeting only if it does not overlap any existing meeting. Return True if it was added, otherwise return False. - ("remove_before", time): Remove every meeting whose end is less than or equal to time. Return the number of removed meetings. - ("get_meetings",): Return all currently scheduled meetings sorted by start time. Return a list containing the result of every operation in the same order. The number of operations can be large, so solutions that scan the full schedule for every booking may be too slow.

Constraints

1 <= len(operations) <= 200000
-10^9 <= timestamp values <= 10^9
For every book operation, start < end
get_meetings must return meetings sorted by start time

Examples

Input: [('book', 10, 20), ('book', 20, 30), ('book', 15, 25), ('book', 5, 10), ('remove_before', 20), ('get_meetings',)]

Expected Output: [True, True, False, True, 2, [(20, 30)]]

Explanation: [10,20) and [20,30) can both be booked. [15,25) overlaps existing meetings, so it is rejected. [5,10) is adjacent to [10,20) and is allowed. Removing meetings ending at or before 20 removes [5,10) and [10,20).

Input: [('get_meetings',), ('remove_before', -10), ('book', -5, -1), ('book', -1, 2), ('get_meetings',)]

Expected Output: [[], 0, True, True, [(-5, -1), (-1, 2)]]

Explanation: Initially the schedule is empty. Removing before -10 removes nothing. Both negative/adjacent meetings can be booked.

Input: []

Expected Output: []

Explanation: No operations means no results.

Input: [('book', 1, 4), ('book', 6, 8), ('book', 4, 6), ('book', 2, 3), ('remove_before', 6), ('book', 0, 1), ('get_meetings',)]

Expected Output: [True, True, True, False, 2, True, [(0, 1), (6, 8)]]

Explanation: [1,4), [4,6), and [6,8) are all valid because they only touch at endpoints. [2,3) overlaps [1,4), so it is rejected. Removing before 6 deletes [1,4) and [4,6).

Hints

If meetings are kept sorted by start time and never overlap, then their end times are also strictly increasing.
Think about a data structure that can quickly split meetings by start time for booking, and also cut off an entire prefix of meetings whose end <= time.

Quick Overview

This question evaluates understanding of interval scheduling and overlap detection, proficiency in selecting efficient data structures for dynamic ordered intervals, and the ability to reason about algorithmic time and space complexity.