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

What role is this question designed for?

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

Simulate meeting-room bookings and return busiest room

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You manage `n` meeting rooms labeled `0..n-1` and receive a list of meetings. Each meeting is an interval `[start, end)` with `start < end`. Process meetings in increasing order of `start` time (if not already sorted). **Room assignment rules** 1. If one or more rooms are free at the meeting’s `start`, assign the meeting to the free room with the **smallest room id**. 2. If no room is free at `start`, the meeting is **delayed** until the earliest time when some room becomes free. It must keep the **same duration** `duration = end - start`, and it is assigned to the room that becomes free earliest (break ties by smallest room id). 3. When a delayed meeting starts at time `t`, it ends at `t + duration`. Let `count[i]` be the number of meetings assigned to room `i`. Return the room id with the **maximum** `count[i]`. If there is a tie, return the **smallest room id** among the tied rooms. **Input** - `n`: integer - `meetings`: list of pairs `[start, end)` **Output** - integer room id **Constraints (typical for this problem)** - `1 ≤ n ≤ 10^5` - `1 ≤ len(meetings) ≤ 2*10^5` - times fit in 32-bit integers; delayed times may exceed original end times **Notes** - You should aim for an efficient solution (e.g., using priority queues / heaps).

Quick Answer: This question evaluates a candidate's competence in scheduling and resource-allocation algorithms, focusing on simulation of interval-based bookings, tie-breaking logic, and tracking per-resource assignment counts.

You manage `n` meeting rooms labeled from `0` to `n - 1` and receive a list of meetings, where each meeting is an interval `[start, end)` with `start < end`. Process meetings in increasing order of `start` time. Room assignment rules: 1. If one or more rooms are free at the meeting's `start`, assign the meeting to the free room with the smallest room id. 2. If no room is free at `start`, delay the meeting until the earliest time when a room becomes free. The meeting keeps the same duration `end - start`, and it is assigned to the room that becomes free earliest. If multiple rooms become free at the same earliest time, choose the smallest room id. 3. If a delayed meeting starts at time `t`, it ends at `t + (end - start)`. Let `count[i]` be the number of meetings assigned to room `i`. Return the room id with the maximum `count[i]`. If multiple rooms have the same maximum count, return the smallest room id among them.

Constraints

`1 <= n <= 10^5`
`1 <= len(meetings) <= 2 * 10^5`
Each meeting satisfies `0 <= start < end <= 2^31 - 1`
Delayed meeting end times may exceed the original input time range

Examples

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

Expected Output: 0

Explanation: Room 0 gets meetings [0,10] and delayed [10,11]. Room 1 gets [1,5] and delayed [5,10]. Both handle 2 meetings, so return the smaller room id 0.

Input: (3, [[1, 20], [2, 10], [3, 5], [4, 9], [6, 8]])

Expected Output: 1

Explanation: Two meetings must be delayed. Final counts are room 0 -> 1, room 1 -> 2, room 2 -> 2. Rooms 1 and 2 tie, so return 1.

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

Expected Output: 0

Explanation: There is only one room, so every meeting goes to room 0. Meetings at exact end times can start immediately, so room 0 handles all 4 meetings.

Input: (3, [[0, 5], [0, 5], [0, 5], [5, 10], [5, 10], [5, 10]])

Expected Output: 0

Explanation: The first three meetings use rooms 0, 1, and 2. At time 5 all rooms become free, and the next three meetings again use rooms 0, 1, and 2. Each room handles 2 meetings, so return 0.

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

Expected Output: 1

Explanation: After sorting, room 0 stays busy with [0,100]. Room 1 repeatedly becomes the smallest available room for the short meetings, so it handles 5 meetings in total and is the busiest.

Hints

Use one min-heap for currently free rooms so you can always pick the smallest room id quickly.
Use another min-heap for busy rooms ordered by `(end_time, room_id)`. Before processing a meeting, release every room whose meeting has already ended.

Quick Overview

This question evaluates a candidate's competence in scheduling and resource-allocation algorithms, focusing on simulation of interval-based bookings, tie-breaking logic, and tracking per-resource assignment counts.