Design Ride Sharing System
Problem
Design a RideSharingSystem that matches riders with drivers in arrival order. Support four operations: addRider(riderId) and addDriver(driverId) enqueue a rider or driver; matchDriverWithRider() pairs the earliest still-waiting rider with the earliest available driver, removes both, and returns [driverId, riderId] (or [-1, -1] if either queue is empty); and cancelRider(riderId) withdraws a rider's request only if that rider exists and has not already been matched.
Every id is unique within its role and added at most once, so the only twist is making cancellation play nicely with FIFO matching: a canceled rider must never be paired, yet everyone else keeps their place in line.
addRider(3), addDriver(2), addRider(1), match(), addDriver(5), cancelRider(3), match(), match()[2, 3], [5, 1], [-1, -1]from collections import deque
class RideSharingSystem:
def __init__(self):
self.riders = deque() # waiting riders, arrival order
self.drivers = deque() # available drivers, arrival order
self.canceled = set() # riders canceled before matching
def addRider(self, riderId):
self.riders.append(riderId)
def addDriver(self, driverId):
self.drivers.append(driverId)
def matchDriverWithRider(self):
while self.riders and self.riders[0] in self.canceled:
self.canceled.discard(self.riders.popleft())
if not self.riders or not self.drivers:
return [-1, -1]
driverId = self.drivers.popleft()
riderId = self.riders.popleft()
return [driverId, riderId]
def cancelRider(self, riderId):
self.canceled.add(riderId)class RideSharingSystem {
constructor() {
this.riders = []; // waiting riders, arrival order
this.drivers = []; // available drivers, arrival order
this.head = 0; // front index into riders
this.dHead = 0; // front index into drivers
this.canceled = new Set(); // canceled rider ids
}
addRider(riderId) { this.riders.push(riderId); }
addDriver(driverId) { this.drivers.push(driverId); }
matchDriverWithRider() {
while (this.head < this.riders.length && this.canceled.has(this.riders[this.head])) {
this.canceled.delete(this.riders[this.head++]);
}
if (this.head >= this.riders.length || this.dHead >= this.drivers.length) {
return [-1, -1];
}
const driverId = this.drivers[this.dHead++];
const riderId = this.riders[this.head++];
return [driverId, riderId];
}
cancelRider(riderId) { this.canceled.add(riderId); }
}class RideSharingSystem {
Deque<Integer> riders = new ArrayDeque<>(); // waiting riders
Deque<Integer> drivers = new ArrayDeque<>(); // available drivers
Set<Integer> canceled = new HashSet<>(); // canceled rider ids
public void addRider(int riderId) { riders.addLast(riderId); }
public void addDriver(int driverId) { drivers.addLast(driverId); }
public int[] matchDriverWithRider() {
while (!riders.isEmpty() && canceled.contains(riders.peekFirst())) {
canceled.remove(riders.pollFirst());
}
if (riders.isEmpty() || drivers.isEmpty()) {
return new int[]{-1, -1};
}
int driverId = drivers.pollFirst();
int riderId = riders.pollFirst();
return new int[]{driverId, riderId};
}
public void cancelRider(int riderId) { canceled.add(riderId); }
}class RideSharingSystem {
deque<int> riders; // waiting riders, arrival order
deque<int> drivers; // available drivers, arrival order
unordered_set<int> canceled; // canceled rider ids
public:
void addRider(int riderId) { riders.push_back(riderId); }
void addDriver(int driverId) { drivers.push_back(driverId); }
vector<int> matchDriverWithRider() {
while (!riders.empty() && canceled.count(riders.front())) {
canceled.erase(riders.front());
riders.pop_front();
}
if (riders.empty() || drivers.empty()) {
return {-1, -1};
}
int driverId = drivers.front(); drivers.pop_front();
int riderId = riders.front(); riders.pop_front();
return {driverId, riderId};
}
void cancelRider(int riderId) { canceled.insert(riderId); }
};Explanation
The phrase “match the earliest waiting rider with the earliest available driver” is the giveaway: this is FIFO matching, so two queues do the heavy lifting. addRider enqueues onto the rider queue, addDriver enqueues onto the driver queue, and a match pops one from each front. With plain queues every operation is O(1).
The only complication is cancelRider. A canceled rider may be sitting anywhere in the queue, and physically deleting from the middle of a FIFO queue is awkward and slow. The clean trick is lazy deletion: cancelRider simply records the id in a canceled set and leaves the queue untouched. The rider is still in line on paper, but marked invalid.
The cleanup happens lazily inside matchDriverWithRider. Before pairing, we peek at the front of the rider queue and, while that rider is in the canceled set, we pop it off (and drop it from the set, since each id appears once). This skips over any withdrawn riders so the front always holds a genuine, still-waiting rider before we commit to a match.
After that skip loop, if either queue is empty we return [-1, -1]. Otherwise we pop the front driver and the front rider and return [driverId, riderId]. Because each id is added at most once, a rider that was already matched is gone from the queue, so a later cancelRider on it just adds a set entry that is never consumed — exactly the “cancel has no effect” behaviour the problem requires.
Walk the example: riders join as [3, 1] and drivers as [2]. The first match skips nothing, pairs driver 2 with rider 3 → [2, 3]. Then driver 5 arrives and cancelRider(3) marks 3 canceled — but 3 already left the queue, so nothing happens. The next match sees rider 1 at the front (not canceled), pairs it with driver 5 → [5, 1]. The final match finds the rider queue empty and returns [-1, -1].
Each rider and driver is pushed and popped at most once, and the skip loop charges each canceled rider a single pop over the whole run, so all four operations are amortized O(1).