Katkat
Back

Support room moves and query top-k fastest

PinterestMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a data structure that efficiently manages room assignments and retrieves the top-k rooms based on a primary priority (number of people) and a secondary priority (earliest arrival time).

Problem Statement

You are building a room-management system for a distributed office. You need to implement a class RoomManager that tracks how many people are in each room and supports efficient retrieval of the busiest rooms.

Requirements

  1. add_person(person_id, room_id): Registers that a person has entered a specific room. If the person was already in another room, they must leave that room first (FIFO order). The arrival time for this person in the new room is the current global timestamp.
  2. leave_room(person_id): Removes a person from their current room.
  3. get_top_k_rooms(k): Returns the IDs of the top k rooms. The criteria for ranking are:
    • Primary: Higher count of people in the room.
    • Secondary: For rooms with the same count, the one with the earliest arrival time of its most recent member takes precedence (i.e., the room that reached its current count state most recently, in terms of its latest addition).

Constraints

  • Total number of people N up to 10^5.
  • Total number of rooms M up to 10^4.
  • get_top_k_rooms should be optimized better than O(M log M).

Example

# Initialize with 3 rooms
rm = RoomManager()
rm.add_person(1, "A") # Room A: 1 person, time 1
rm.add_person(2, "B") # Room B: 1 person, time 2
rm.add_person(3, "A") # Room A: 2 people, time 3

# get_top_k_rooms(2)
# Returns ["A", "B"]

Considerations

  • How will you handle the movement of a person between rooms in O(log M) time?
  • What data structures are needed to keep the room counts and timestamps synchronized?

Hints

Hint 1

Use a hash map to store the mapping of person_id to their current room_id.

Hint 2

Maintain a balanced Binary Search Tree or a sorted set of rooms where the key is a tuple of (count, -latest_arrival_time).

Hint 3

Ensure that whenever you update a room's count or arrival time, you remove the old record from the sorted structure and insert the updated record.

Follow-up questions

  • How would the design change if we needed to support 'get_top_k_rooms' in O(k) time?
  • If the number of rooms grows to 10^7, how would you distribute this data structure across multiple nodes?
  • How would you handle the case where the system requires thread-safety for concurrent room updates?