Closest Room

Closest Room

What is this problem about?

The Closest Room coding problem involves a set of hotel rooms, each with an ID and a size. You are given multiple queries, each with a preferred_id and a min_size. For each query, you must find a room that has a size at least min_size and whose ID is as close as possible to the preferred_id. If there's a tie in ID distance, choose the room with the smaller ID.

Why is this asked in interviews?

Amazon uses the Closest Room interview question to test your ability to use offline query processing and advanced data structures. Since there are many queries, a brute-force search for each query would be O(N * Q). The challenge is to process queries in a specific order so that you only ever consider rooms that meet the size requirement.

Algorithmic pattern used

This problem uses the Offline Queries + Sorting + Ordered Set pattern.

1. Sort all rooms by size in descending order.
2. Sort all queries by their min_size in descending order.
3. Iterate through the sorted queries. For each query, add all rooms that are now large enough into an Ordered Set (or a Balanced BST/TreeSet).
4. Once all valid rooms are in the set, use binary search within the set to find the room ID closest to preferred_id.

Example explanation

Rooms: [(1, 10), (2, 20), (3, 15)] (ID, Size) Query: pref_id=2, min_size=12

1. Sorted Rooms: (2, 20), (3, 15), (1, 10).
2. Valid rooms for size 12 are (2, 20) and (3, 15).
3. Add IDs {2, 3} to an ordered set.
4. Closest ID to 2 in {2, 3} is 2. Result: Room ID 2.

Common mistakes candidates make

• Online Processing: Trying to solve each query as it comes, which is too slow.
• Wrong Sort Order: Sorting by ID instead of Size, which doesn't help with the "min_size" constraint.
• Set Selection: Not using a data structure that allows for O(log N) "closest value" lookup (like bisect in Python on a sorted list, or TreeSet in Java).

Interview preparation tip

"Offline processing" is a key technique to mention when queries have multiple constraints. By sorting both the data and the queries by one constraint, you can focus on the other constraint using an efficient data structure.