Skip to main content
Talentd

Design Ride Sharing System - Solution & Explanation

MediumHash TableDesignQueueData Stream11 min readAsked at: Meta
Practice this problem

Problem Statement

A ride sharing system manages ride requests from riders and availability from drivers. Riders request rides, and drivers become available over time. The system should match riders and drivers in the order they arrive.

Implement the RideSharingSystem class:

  • RideSharingSystem() Initializes the system.
  • void addRider(int riderId) Adds a new rider with the given riderId.
  • void addDriver(int driverId) Adds a new driver with the given driverId.
  • int[] matchDriverWithRider() Matches the earliest available driver with the earliest waiting rider and removes both of them from the system. Returns an integer array of size 2 where result = [driverId, riderId] if a match is made. If no match is available, returns [-1, -1].
  • void cancelRider(int riderId) Cancels the ride request of the rider with the given riderId if the rider exists and has not yet been matched.

 

Example 1:

Input:
["RideSharingSystem", "addRider", "addDriver", "addRider", "matchDriverWithRider", "addDriver", "cancelRider", "matchDriverWithRider", "matchDriverWithRider"]
[[], [3], [2], [1], [], [5], [3], [], []]

Output:
[null, null, null, null, [2, 3], null, null, [5, 1], [-1, -1]]

Explanation

RideSharingSystem rideSharingSystem = new RideSharingSystem(); // Initializes the system
rideSharingSystem.addRider(3); // rider 3 joins the queue
rideSharingSystem.addDriver(2); // driver 2 joins the queue
rideSharingSystem.addRider(1); // rider 1 joins the queue
rideSharingSystem.matchDriverWithRider(); // returns [2, 3]
rideSharingSystem.addDriver(5); // driver 5 becomes available
rideSharingSystem.cancelRider(3); // rider 3 is already matched, cancel has no effect
rideSharingSystem.matchDriverWithRider(); // returns [5, 1]
rideSharingSystem.matchDriverWithRider(); // returns [-1, -1]

Example 2:

Input:
["RideSharingSystem", "addRider", "addDriver", "addDriver", "matchDriverWithRider", "addRider", "cancelRider", "matchDriverWithRider"]
[[], [8], [8], [6], [], [2], [2], []]

Output:
[null, null, null, null, [8, 8], null, null, [-1, -1]]

Explanation

RideSharingSystem rideSharingSystem = new RideSharingSystem(); // Initializes the system
rideSharingSystem.addRider(8); // rider 8 joins the queue
rideSharingSystem.addDriver(8); // driver 8 joins the queue
rideSharingSystem.addDriver(6); // driver 6 joins the queue
rideSharingSystem.matchDriverWithRider(); // returns [8, 8]
rideSharingSystem.addRider(2); // rider 2 joins the queue
rideSharingSystem.cancelRider(2); // rider 2 cancels
rideSharingSystem.matchDriverWithRider(); // returns [-1, -1]

 

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 calls will be made in total to addRiderā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹, addDriver, matchDriverWithRider, and cancelRider.

Approach Overview

Problem Overview: Design a ride sharing system that processes a continuous stream of ride requests and driver availability updates. The system must efficiently match riders with drivers while maintaining fast lookups and ordered processing of requests.

Approach 1: Queue Simulation + Linear Search (O(n) per operation, O(n) space)

The straightforward implementation uses a queue to store incoming ride requests and a list or map of available drivers. Each time a request arrives, you iterate through the driver list to find a suitable match. When a driver becomes available, you scan the queued requests to assign the earliest compatible rider. This approach mirrors the real-world first-come-first-served process but requires scanning potentially many elements for each assignment.

The key operations are queue insertion for incoming requests and linear iteration for matching. While simple to implement, the repeated scans cause O(n) time per match operation, which becomes slow as the number of riders and drivers grows. Space complexity remains O(n) because all active requests and drivers must be stored in memory.

Approach 2: Sorted Set + Hash Table (O(log n) per operation, O(n) space)

A more scalable design combines a sorted structure for ordering with a hash table for constant-time lookups. The hash table maps rider or driver IDs to their current state, while a sorted set maintains ordering based on attributes such as request time, priority, or distance. This allows the system to always retrieve the most suitable match without scanning the entire dataset.

When a new ride request arrives, insert it into the sorted set and record its metadata in the hash table. When a driver becomes available, query the sorted set to fetch the best candidate in O(log n) time. After a match, remove both entities from the sorted structure and update the hash table. This design supports fast updates and efficient matching even under heavy request streams, which is typical in data stream style problems.

The combination works because the sorted set guarantees efficient ordering while the hash table provides direct access to objects during updates or cancellations. Insertions, deletions, and queries all run in O(log n) time, making the system responsive even with thousands of active rides.

Recommended for interviews: Interviewers typically expect the Sorted Set + Hash Table design. A basic queue simulation shows you understand the workflow, but the optimized design demonstrates knowledge of scalable system design and efficient data structures. Mentioning why linear scans fail at scale and replacing them with ordered retrieval is the key insight that signals strong problem-solving ability.

Solution

We use two sorted sets riders and drivers to store waiting riders and available drivers respectively. Each element is a tuple (t, id), representing the ID of the rider/driver and their timestamp t when they joined the system. The timestamp t is used to distinguish the order of arrival. Initially, t = 0, and each time a rider or driver is added, t is incremented by 1.

Additionally, we use a hash table d to store the mapping between each rider's ID and their timestamp, which facilitates lookup when canceling a rider's request.

Specifically:

  • When adding a rider, we add (t, riderId) to riders, set d[riderId] = t, and then increment t by 1.
  • When adding a driver, we add (t, driverId) to drivers and then increment t by 1.
  • When matching a driver with a rider, if either riders or drivers is empty, we return [-1, -1]. Otherwise, we remove the elements with the smallest timestamps from both riders and drivers, namely (t_r, riderId) and (t_d, driverId), and return [driverId, riderId].
  • When canceling a rider's request, we look up the rider's timestamp t through d, and then remove (t, riderId) from riders.

The time complexity is O(log n) per operation, where n is the current number of riders or drivers. The space complexity is O(n).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Queue Simulation + Linear SearchO(n) per matchO(n)Simple prototype or when the number of drivers and riders is very small
Sorted Set + Hash TableO(log n) per operationO(n)Production-scale systems or interview solutions requiring efficient matching

Video Solution

Design Ride Sharing System | LeetCode 3829 | Weekly Contest 487 ā€¢ Sanyam IIT Guwahati ā€¢ 522 views views

Watch 4 more video solutions ā†’

Frequently Asked Questions

Is Design Ride Sharing System easy or hard?
Design Ride Sharing System is typically classified as a medium difficulty problem. The main challenge is choosing the right combination of data structures to support efficient matching and updates in a streaming environment.
Design Ride Sharing System Python/Java solution
Implement the optimized solution using a hash map for rider or driver state and a sorted container such as TreeSet in Java, SortedList in Python, or ordered sets in C++/Go. Each request or availability update inserts or removes entries while maintaining sorted order for efficient matching.
How to solve Design Ride Sharing System in O(log n)?
Maintain ride requests in a sorted structure such as a balanced tree or ordered set keyed by request priority or time. Store driver and rider metadata in a hash map. When a driver becomes available, query the sorted set to retrieve the best rider in O(log n), then update both structures after the match.
What is the best approach for Design Ride Sharing System?
The most efficient solution uses a combination of a sorted set and a hash table. The sorted set maintains ordered ride requests or driver availability, while the hash table provides O(1) lookups for driver or rider metadata. Each insertion, deletion, and match operation runs in O(log n) time with O(n) total space.
Is Design Ride Sharing System asked at Google/Amazon/Meta?
Ride sharing system design and streaming matching problems frequently appear in interviews at companies like Uber, Lyft, Amazon, and Google. These questions test your ability to combine data structures such as heaps, ordered sets, queues, and hash maps for scalable real-time systems.
What data structure is used in Design Ride Sharing System?
The common implementation uses a hash table for quick lookups and a sorted set or balanced tree for ordered retrieval of ride requests or drivers. Queues may also appear in simpler designs that process requests in arrival order.
What is the time complexity of Design Ride Sharing System?
The optimized Sorted Set + Hash Table approach performs insert, remove, and match operations in O(log n) time. Space complexity is O(n) because all active riders and drivers must be stored in memory structures for quick access.

Ready to solve this problem?

Practice Design Ride Sharing System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters