Ride Sharing with Ordered Matching and Cancellation

### Problem Implement `RideSharingSystem`, which tracks waiting riders and available drivers in their respective arrival order. - `RideSharingSystem()` starts with no riders or drivers. - `void addRider(int riderId)` adds that rider as a new waiting request. - `void addDriver(int driverId)` adds that driver as available. - `vector<int> matchDriverWithRider()` pairs the earliest available driver with the earliest still-waiting rider, removes both from the system, and returns `[driverId,riderId]`. If either side has no eligible participant, return `[-1,-1]` without consuming an eligible participant from the other side. - `void cancelRider(int riderId)` cancels that rider's request if it currently exists and has not been matched. Otherwise it has no effect. Matching happens when the matching method is called; adding a participant does not itself return a match. Preserve the full constructor and method-sequence interface. ```cpp class RideSharingSystem { public: RideSharingSystem(); void addRider(int riderId); void addDriver(int driverId); vector<int> matchDriverWithRider(); void cancelRider(int riderId); }; ``` ### Examples **Example 1:** ```text Operations: ["RideSharingSystem","addDriver","addDriver","addRider","addRider","cancelRider","matchDriverWithRider","matchDriverWithRider","addRider","matchDriverWithRider"] Arguments: [[],[4],[9],[7],[2],[7],[],[],[6],[]] Output: [null,null,null,null,null,null,[4,2],[-1,-1],null,[9,6]] Explanation: Rider 7 cancels, so the first match pairs driver 4 with rider 2. The failed next match leaves driver 9 available. After rider 6 arrives, the final match is [9,6]. ``` **Example 2:** ```text Operations: ["RideSharingSystem","cancelRider","addRider","addDriver","matchDriverWithRider","cancelRider","addDriver","addRider","matchDriverWithRider"] Arguments: [[],[5],[5],[5],[],[5],[2],[9],[]] Output: [null,null,null,null,[5,5],null,null,null,[2,9]] Explanation: Canceling rider 5 before it exists has no effect. Rider 5 and driver 5 may coexist because the roles have separate ID namespaces. After they match, another cancellation of rider 5 has no effect. The last match pairs driver 2 with rider 9. ``` `null` records construction or a `void` method in these example traces; it does not replace the methods' original C++ return types. ### Constraints - `1 <= riderId, driverId <= 1000`. - Each rider ID is added at most once over the object's lifetime, unique among riders. - Each driver ID is added at most once over the object's lifetime, unique among drivers. - The same integer may be used once in each different role; there is no global cross-role uniqueness promise. - At most 1000 total calls are made to `addRider`, `addDriver`, `matchDriverWithRider`, and `cancelRider`. ### Clarifying Questions - Is a canceled or matched rider ID added again? No; the once-per-role addition rule still applies. - Can a driver ID equal a rider ID? Yes, including the two IDs returned by one match. - What happens when an unknown or already-matched rider is canceled? Nothing. - Does canceling a rider remove a driver with the same numeric ID? No; the roles are separate. ### What a Strong Answer Covers - Independent arrival order for both roles and earliest eligible matching. - Cancellation, no-op cancellations, and failure without consuming an eligible counterpart. - The exact once-per-role lifecycle and allowed cross-role ID overlap. - Correct state across the complete method sequence and per-operation resource bounds. ### Follow-up Questions - What would need to be specified if drivers could also cancel availability? - How would returning match timestamps change the interface and required inputs? ```hint Preserve both arrival orders while recognizing cancellations Keep FIFO records for drivers and riders, plus whether each rider is currently waiting. A canceled rider can be removed immediately or skipped before matching. The source's once-per-role addition rule means an old canceled request cannot become a new request with the same rider ID. ```