3829. Design Ride Sharing System
Asked at Rippling
Difficulty
Medium
Time
O(1) amortized per operation
Space
O(n)
Pattern
Hash Table
Companies
1
Problem
Design a class RideSharingSystem that matches riders with drivers. Riders and drivers join over time, and matching always follows arrival order: the earliest waiting rider pairs with the earliest available driver.
Implement these methods:
RideSharingSystem()— create an empty system.addRider(riderId)— a rider joins and starts waiting.addDriver(driverId)— a driver becomes available.matchDriverWithRider()— take the earliest waiting rider and the earliest available driver, remove both from the system, and return[driverId, riderId]. If either side is missing, return[-1, -1]and change nothing.cancelRider(riderId)— remove that rider's request. If the rider was already matched, or never existed, do nothing.
A rider or driver is used at most once. Once matched, they are gone and cannot be matched again. Cancelling only works while the rider is still waiting.
Two queues, first in first out
Constraints
- ●
1 <= riderId, driverId <= 1000 - ●
Each riderId is unique among riders and is added at most once. - ●
Each driverId is unique among drivers and is added at most once. - ●
At most 1000 total calls to addRider, addDriver, matchDriverWithRider and cancelRider.
Examples
["RideSharingSystem", "addRider", "addDriver", "addRider", "matchDriverWithRider", "addDriver", "cancelRider", "matchDriverWithRider", "matchDriverWithRider"]
[[], [3], [2], [1], [], [5], [3], [], []][null, null, null, null, [2, 3], null, null, [5, 1], [-1, -1]]["RideSharingSystem", "addRider", "addDriver", "addDriver", "matchDriverWithRider", "addRider", "cancelRider", "matchDriverWithRider"]
[[], [8], [8], [6], [], [2], [2], []][null, null, null, null, [8, 8], null, null, [-1, -1]]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
Brute force: store all drivers in a list. For each rider request, scan all drivers to find the nearest available one. That's O(n) per match. Too slow for real-time matching at scale.
Key insight: use a hash map for driver info (id → location, status) and a spatial data structure for proximity queries. A k-d tree or grid-based bucketing gives efficient nearest-neighbor search.
Simpler approach for interview: use a hash map of driver_id → (location, available). For matching, iterate through drivers and find the closest available one by Manhattan or Euclidean distance. This is O(n) but acceptable for an interview unless asked to optimize further.
For the queue-based approach: riders who can't find a driver enter a wait queue. When a driver becomes available, match with the longest-waiting rider. Use a deque for the rider queue.
Edge cases: no available drivers (add to wait list), multiple drivers at same distance (pick any or use tie-breaking like driver ID), rider and driver at same location (distance 0, perfect match).
Optimal Approach
Data structures:
drivers: hash map, driver_id → {location: (x,y), available: bool}wait_queue: deque of rider requests waiting for a driver
addDriver(id, x, y):
Add to drivers hash map with available = True.
Check if any riders are waiting. If so, match with the nearest one.
updateLocation(id, x, y):
Update the driver's location in the hash map.
matchRider(rx, ry):
Find the closest available driver by Euclidean distance.
If found: mark driver unavailable, return driver_id.
If not found: add rider to wait_queue, return null.
completeRide(driver_id):
Mark driver as available.
Check wait_queue. If not empty, dequeue and match with this driver.
Time: O(n) per match (linear scan for nearest driver). O(1) for add/update. Space: O(n) for drivers and wait queue.
Match, then clean up cancelled riders
What Trips People Up in Real Interviews
Not handling the wait queue. When no driver is available, the rider request should be queued and matched when a driver becomes available. Forgetting this means lost requests.
Using Euclidean distance when Manhattan distance is specified. Clarify with the interviewer which distance metric to use. Manhattan distance is |x1-x2| + |y1-y2|.
Not updating driver availability after matching. Once a driver is matched with a rider, they must be marked as unavailable so they can't be double-booked.
Forgetting to check the wait queue when a driver becomes available. After completing a ride, immediately check if any riders are waiting and match them.
Over-engineering with a k-d tree. For an interview, a linear scan through the hash map is usually sufficient unless explicitly asked for optimal spatial queries. Keep it simple first.
Solution Code
O(1) amortized per operation timeimport math
from collections import deque
class RideSharingSystem:
def __init__(self):
self.drivers = {}
self.wait_queue = deque()
def addDriver(self, driverId, x, y):
self.drivers[driverId] = {"x": x, "y": y, "available": True}
self._tryMatchWaiting()
def updateLocation(self, driverId, x, y):
if driverId in self.drivers:
self.drivers[driverId]["x"] = x
self.drivers[driverId]["y"] = y
def matchRider(self, riderId, x, y):
best_driver = None
best_dist = float('inf')
for did, info in self.drivers.items():
if info["available"]:
dist = math.sqrt((info["x"] - x) ** 2 + (info["y"] - y) ** 2)
if dist < best_dist:
best_dist = dist
best_driver = did
if best_driver:
self.drivers[best_driver]["available"] = False
return best_driver
self.wait_queue.append((riderId, x, y))
return None
def completeRide(self, driverId):
if driverId in self.drivers:
self.drivers[driverId]["available"] = True
self._tryMatchWaiting()
def _tryMatchWaiting(self):
while self.wait_queue:
riderId, rx, ry = self.wait_queue[0]
matched = False
best_driver = None
best_dist = float('inf')
for did, info in self.drivers.items():
if info["available"]:
dist = math.sqrt((info["x"] - rx) ** 2 + (info["y"] - ry) ** 2)
if dist < best_dist:
best_dist = dist
best_driver = did
if best_driver:
self.drivers[best_driver]["available"] = False
self.wait_queue.popleft()
matched = True
else:
breakFrequently Asked Questions
What is the Design Ride Sharing System problem?
Design a ride sharing system that supports adding drivers with locations, matching riders to nearest available drivers, and updating driver locations. This tests your ability to design a real-time matching system with appropriate data structures.
How do you solve Design Ride Sharing System?
The optimal approach runs in O(1) amortized per operation time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design Ride Sharing System?
Design Ride Sharing System is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Design Ride Sharing System?
- Not handling the wait queue. When no driver is available, the rider request should be queued and matched when a driver becomes available. Forgetting this means lost requests.
- Using Euclidean distance when Manhattan distance is specified. Clarify with the interviewer which distance metric to use. Manhattan distance is `|x1-x2| + |y1-y2|`.
- Not updating driver availability after matching. Once a driver is matched with a rider, they must be marked as unavailable so they can't be double-booked.
- Forgetting to check the wait queue when a driver becomes available. After completing a ride, immediately check if any riders are waiting and match them.
- Over-engineering with a k-d tree. For an interview, a linear scan through the hash map is usually sufficient unless explicitly asked for optimal spatial queries. Keep it simple first.