Debug the Last-Element Random Allocation Case

Problem Statement

DoorDash dynamically matches incoming delivery orders with available active couriers. To balance distribution, an internal dispatcher maintains an active courier pool with three operations that must run in average O(1) time:

1. add(courier_id: int) -> bool: Adds a courier to the pool. Returns True if the courier was newly added, or False if they were already present.
2. remove(courier_id: int) -> bool: Removes a courier from the pool. Returns True if the courier was successfully removed, or False if they were not in the pool.
3. sample() -> int: Returns a uniformly random courier_id from the current pool. If the pool is empty, it should raise an IndexError.

A common pattern for O(1) removal maintains an array of items alongside a hash map of {item: array_index}. The target item is swapped with the last element in the array, the index entry is updated, and the array is popped.

However, a notoriously subtle bug occurs when the item to be removed is already the last element (or the only element) in the array. If the update order is incorrect (e.g., updating the map for the "moved" last element after deleting the target, or overwriting indices improperly), the map can resurrect a deleted key or store an out-of-bounds index.

Your task is to:

1. Implement the CourierPool class correctly handling all edge cases in average O(1) time.
2. Provide a deterministic test function test_last_element_edge_cases() that isolates and validates the self-swap / tail-element removal scenarios without relying on non-deterministic random assertions.

Class Interface

class CourierPool:
    def __init__(self):
        pass

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

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

    def sample(self) -> int:
        pass

Examples

Example 1

pool = CourierPool()
pool.add(101)    # Returns True
pool.add(102)    # Returns True
pool.remove(102) # Removing the tail element! Returns True
pool.sample()    # Returns 101 with 100% probability
pool.remove(101) # Removing the only remaining element (also tail). Returns True
pool.add(102)    # Re-adding previously removed element. Returns True

Example 2

pool = CourierPool()
pool.add(42)     # Returns True
pool.remove(42)  # Returns True
pool.remove(42)  # Returns False (already removed)

Constraints

• -2^31 <= courier_id <= 2^31 - 1
• At most 2 * 10^5 total calls will be made across all methods.
• Each method must execute in O(1) average time.
• Total space complexity should be O(N), where N is the number of distinct couriers currently in the pool.