Uber Coding Interview: Meeting Room Booker

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Uber. We'll work through one coding problem together, so please think out loud as you go. You can pause the interview any time with the Pause button at the top right of your screen.

The problem is about assigning meeting rooms to booking requests as they arrive, which is a bit like matching limited vehicles to overlapping trips. It's in the Problem tab on the right, so please read it through, take your time, and ask me anything before you start.

The problem

An office has n meeting rooms, and booking requests arrive one at a time.

• n: number of rooms, numbered 0 to n-1
• requests: list of {start, end} in arrival order (integers, start < end); requests may arrive in any time order

Process the requests in order. Each request books the lowest-numbered room that has no existing booking overlapping [start, end). Intervals are half-open, so [10,20) and [20,30) don't overlap. Return a list with, for each request, the room it got, or -1 (INVALID) if no room is free for the whole interval.

Example: n = 2, requests = [[10,20],[15,25],[12,18],[20,30],[5,10]] → [0, 1, -1, 0, 0]

Sizes: n ≤ 100, up to 10^4 requests.