Simulate Constant-Time Random Courier Selection

Problem Description

DoorDash dispatch systems dynamically match incoming delivery orders with currently available dashers (couriers). To balance dispatch load fairly across a fleet, the system needs to maintain an active pool of available courier IDs and pick a courier uniformly at random when an order arrives.

Implement the CourierPool class:

• __init__(): Initializes the courier pool.
• register_courier(courier_id: int) -> bool: Inserts courier_id into the pool if it is not already present. Returns True if the courier was successfully registered, or False if the courier was already in the pool.
• deregister_courier(courier_id: int) -> bool: Removes courier_id from the pool if it is present. Returns True if the courier was successfully removed, or False if the courier was not found in the pool.
• get_random_courier() -> int: Returns a courier ID chosen uniformly at random from the pool of currently registered couriers. Each courier currently in the pool must have an equal probability of being selected. If the pool is empty, return -1.

Each function must run in average O(1) time complexity.

Class Interface

class CourierPool:
    def __init__(self):
        pass

    def register_courier(self, courier_id: int) -> bool:
        pass

    def deregister_courier(self, courier_id: int) -> bool:
        pass

    def get_random_courier(self) -> int:
        pass

Examples

Example 1

pool = CourierPool()
pool.register_courier(101)   # returns True; pool: [101]
pool.deregister_courier(202) # returns False; 202 is not in pool
pool.register_courier(202)   # returns True; pool: [101, 202]
pool.get_random_courier()    # returns 101 or 202 with equal probability (50% each)
pool.deregister_courier(101) # returns True; pool: [202]
pool.register_courier(202)   # returns False; 202 is already registered
pool.get_random_courier()    # returns 202

Example 2

pool = CourierPool()
pool.get_random_courier()    # returns -1 because pool is empty

Constraints

• -2^31 <= courier_id <= 2^31 - 1
• At most 2 * 10^5 calls will be made in total to register_courier, deregister_courier, and get_random_courier.
• There will be at least one call to get_random_courier when the pool is non-empty.