Top items and scheduling: A Sample Coding Interview Solution

The coding question

You've got n meeting rooms. Write book(start, end) that returns a room that's free for that whole time, or INVALID if none is. Then add a way to cancel a booking.

Ask a few questions first

Ask	What we'll assume
Can a meeting start the minute another ends?	Yes. Times are half-open, so 9 to 11 and 11 to 12 don't clash.
If several rooms are free, which one?	The lowest-numbered one, so the answers are predictable.
How does cancel know which booking?	cancel(room, start). A room can't have two bookings that start at the same time.
What if start isn't before end?	Return INVALID.

A couple of examples

Input	Output
n = 2: book(9, 11), book(10, 12), book(10, 11), book(11, 12)	0, 1, "INVALID", 0
then cancel(0, 9), then book(10, 11)	True, then 0, since room 0 is free until 11
then cancel(1, 5)	False, since there's no such booking

Start with brute force

Keep a list of bookings per room. To book, go through the rooms and check the new meeting against every booking in that room.

Cost: O(total bookings) per call. Fine for a small office, slow once each room has thousands of bookings.

A better way

Inside one room, bookings never overlap. So if we keep them sorted by start time, a new meeting can only clash with two of them: the one that starts right after our start, and the one just before it.

Binary search finds that spot. The new meeting fits if the next booking starts at or after our end, and the previous one ends at or before our start. That's two checks per room instead of a scan. Cancelling is a lookup and a removal from the same sorted list.

For each room, keep a sorted list of start times and a map from start to end.
To check a room, binary search for where our start would go.
If the booking at that spot starts before our end, it clashes. If the booking just before it ends after our start, it clashes too.
book tries rooms from 0 up and takes the first one with no clash, adding the booking to both structures.
cancel looks up the start in that room's map, and if it's there, removes it from both.

The code

solution.pypython

from bisect import bisect_left, insort


class RoomBooker:
    def __init__(self, n):
        self.starts = [[] for _ in range(n)]  # sorted start times per room
        self.ends = [{} for _ in range(n)]    # start time -> end time per room

    def _is_free(self, room, start, end):
        starts = self.starts[room]
        i = bisect_left(starts, start)
        if i < len(starts) and starts[i] < end:
            return False  # the next booking starts before we'd finish
        if i > 0 and self.ends[room][starts[i - 1]] > start:
            return False  # the booking before us hasn't finished yet
        return True

    def book(self, start, end):
        if start >= end:
            return "INVALID"
        for room in range(len(self.starts)):
            if self._is_free(room, start, end):
                insort(self.starts[room], start)
                self.ends[room][start] = end
                return room
        return "INVALID"

    def cancel(self, room, start):
        if start not in self.ends[room]:
            return False
        del self.ends[room][start]
        self.starts[room].pop(bisect_left(self.starts[room], start))
        return True

	Cost	Why
Book	O(n log b) to check, plus O(b) to insert	A binary search per room for b bookings in a room. Python's list insert shifts items, a balanced tree would make it O(log b)
Cancel	O(b)	The lookup's quick, and removing from the list shifts items
Space	O(total bookings)	Each booking is stored once

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Back-to-back meetings, like 9 to 11 then 11 to 12: half-open times mean they fit.
A meeting that fully covers an existing one: the next-booking check catches it.
A meeting that sits inside an existing one: the previous-booking check catches it.
Cancelling something that isn't booked: return False and change nothing.
start equal to end, or after it: INVALID.

Common mistakes

Only checking the previous booking, or only the next one. You need both.
Using closed intervals, so 9 to 11 and 11 to 12 clash when they shouldn't.
Using a min-heap of end times like the 'how many rooms do I need' problem. That works when all meetings are known up front and you never cancel. Here you can't remove from the middle of a heap.
Forgetting to remove from both the sorted list and the map when cancelling.

Follow-up questions

What if many threads call book at once?

Two threads could both see room 0 free and both take it. Lock each room while you check and insert, so only one booking wins. A single lock is simpler, and fine if it's not too busy.

What if you want the room that fits most snugly instead of the lowest number?

Check every room, and pick the one where the gap around the new meeting is smallest. Same checks, just don't stop at the first match.

What if they just ask for the k longest trips from a stream?

Keep a min-heap of size k. A new trip only goes in if it beats the smallest one we're holding, so each add is O(log k).

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Brute force and what it costs
10–15	Explain the better idea
15–30	Write the code
30–38	Test it out loud
38–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Uber.