Design Ride Sharing System
Asked at Rippling
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.
Asked At
| 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).
Visual walkthrough:
addDriver("D1", 0, 0): drivers = {D1: (0,0, available)}
addDriver("D2", 3, 4): drivers = {D1: (0,0, available), D2: (3,4, available)}
matchRider(1, 2): D1 dist=3, D2 dist=4. Match D1. D1 becomes unavailable.
addDriver("D3", 1, 1): drivers = {D1: (0,0, unavailable), D2: (3,4, available), D3: (1,1, available)}
matchRider(2, 3): D2 dist=2, D3 dist=3. Match D2. D2 becomes unavailable.
updateLocation("D1", 5, 5): D1 location updated to (5,5).
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.
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
import 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.