Design an in-memory ride-hailing system that allows riders to request trips, matches them with nearby drivers, tracks trip progress, calculates fares, supports cancellations, and processes payments.

The public methods model the main booking, tracking, cancellation, pricing, and payment operations of a ride-hailing API.

Class

RideHailingSystem

Entities and Design Requirements

• A location is represented by integer coordinates (locationX, locationY).
• Trip states are REQUESTED, ACCEPTED, IN_PROGRESS, COMPLETED, and CANCELLED.
• The valid successful state sequence is REQUESTED → ACCEPTED → IN_PROGRESS → COMPLETED.
• A trip in REQUESTED, ACCEPTED, or IN_PROGRESS may instead move to CANCELLED.
• COMPLETED and CANCELLED are terminal trip states.
• A rider and a driver may each participate in at most one non-terminal trip at a time.

Constructor

public RideHailingSystem(long baseFareInCents, long farePerDistanceUnitInCents, int maxPaymentAttempts, List<String> drivers)

• Initializes the system with the supplied drivers and no riders or trips.
• Each value in drivers uses the comma-separated format "driverId,driverName,locationX,locationY".
• All supplied drivers are initially available for matching.
• Drivers cannot be added or removed after construction.
• baseFareInCents is charged for every completed trip.
• farePerDistanceUnitInCents is charged for every actual distance unit travelled.
• maxPaymentAttempts is the maximum number of distinct payment attempts allowed for one trip.

Methods

addRider

public boolean addRider(String riderId, String riderName)

• Adds a rider with the supplied identifier and name.
• Returns true when the rider is added.
• Returns false if riderId already exists.

updateDriverLocation

public boolean updateDriverLocation(String driverId, int locationX, int locationY)

• Updates the driver's current location and the spatial index.
• The location may be updated while the driver is available, assigned, or travelling so that the driver can be tracked.
• Returns false if the driver does not exist.
• Otherwise, updates the location and returns true.

setDriverAvailability

public boolean setDriverAvailability(String driverId, boolean available)

• Changes whether a driver may receive a new trip request.
• Returns false if the driver does not exist or is assigned to a nonterminal trip.
• Otherwise, sets the requested availability and returns true.

updateSurgePricing

public int updateSurgePricing(String zoneId, int activeRequests, int availableDrivers)

• Calculates and stores the surge multiplier percentage for zoneId using the supplied market-demand values.
• If activeRequests is 0, the multiplier is 100.
• If activeRequests is positive and availableDrivers is 0, the multiplier is 300.
• If activeRequests ≤ availableDrivers, the multiplier is 100.
• If availableDrivers < activeRequests ≤ 2 × availableDrivers, the multiplier is 150.
• In every other case, the multiplier is 200.
• Returns the stored multiplier percentage.
• A zone that has never been updated uses a multiplier of 100.

estimateFare

public long estimateFare(String zoneId, int estimatedDistanceUnits)

• Uses the current surge multiplier of the specified zone.
• First calculates subtotal = baseFareInCents + estimatedDistanceUnits × farePerDistanceUnitInCents.
• The estimated fare is ceil(subtotal × surgeMultiplierPercentage / 100).
• Returns the estimated fare in cents.

requestTrip

public String requestTrip(String tripId, String riderId, int pickupX, int pickupY, int destinationX, int destinationY, String zoneId, String paymentMethodId)

• Creates a trip request and assigns the nearest available driver.
• Driver distance is compared using (driverX - pickupX) × (driverX - pickupX) + (driverY - pickupY) × (driverY - pickupY).
• If multiple drivers have the same distance, the lexicographically smallest driverId is selected.
• The selected driver becomes unavailable and is reserved for this trip.
• The trip stores the zone's current surge multiplier. Later surge changes do not affect this trip.
• The newly created trip has state REQUESTED.
• Returns the selected driverId when successful.
• Returns an empty string if the trip identifier already exists, the rider does not exist, the rider already has a nonterminal trip, or no driver is available.
• A failed request does not create a trip or reserve a driver.

acceptTrip

public boolean acceptTrip(String tripId, String driverId)

• Changes a trip from REQUESTED to ACCEPTED.
• Returns true only if the trip is currently REQUESTED and driverId is its assigned driver.
• Otherwise, returns false.

startTrip

public boolean startTrip(String tripId, String driverId)

• Changes a trip from ACCEPTED to IN_PROGRESS.
• Returns true only if driverId is the assigned driver and the trip is currently ACCEPTED.
• Otherwise, returns false.

completeTrip

public long completeTrip(String tripId, String driverId, int actualDistanceUnits)

• Completes a trip only when it is currently IN_PROGRESS and driverId is its assigned driver.
• Calculates subtotal = baseFareInCents + actualDistanceUnits × farePerDistanceUnitInCents.
• The final fare is ceil(subtotal × storedSurgeMultiplierPercentage / 100).
• The trip becomes COMPLETED, its payment status becomes PENDING, the driver's location becomes the trip's destination, and the driver becomes available again.
• Returns the final fare in cents when successful.
• Returns -1 when the trip cannot be completed.

cancelTrip

public boolean cancelTrip(String tripId, String requesterId)

• Cancels a trip in REQUESTED, ACCEPTED, or IN_PROGRESS.
• requesterId must be either the trip's rider or its assigned driver.
• A cancelled trip has a fare of 0 and does not create a payment.
• The assigned driver becomes available again.
• Returns true when the trip is cancelled.
• Returns false if any cancellation rule is not satisfied.

processPayment

public String processPayment(String tripId, String paymentRequestId, boolean gatewaySuccessful)

• Payment may be processed only for a COMPLETED trip.
• Each new paymentRequestId represents one payment attempt.
• If the same paymentRequestId is submitted again for the same trip, its original result is returned without creating another attempt. The new value of gatewaySuccessful is ignored.
• A payment request identifier previously used for a different trip is invalid.
• A successful gateway result changes the payment status to SUCCEEDED and returns "SUCCEEDED".
• If a gateway attempt fails while more attempts remain, the payment status becomes RETRY_PENDING and the method returns "RETRY_PENDING".
• When the final allowed attempt fails, the payment status becomes FAILED and the method returns "FAILED".
• Once the overall payment status is SUCCEEDED or FAILED, a new payment request returns that status without creating another attempt.
• Returns "INVALID_REQUEST" when payment processing is not allowed.

getTripDetails

public String getTripDetails(String tripId)

• Returns an empty string if the trip does not exist.
• Otherwise, returns the trip information in the following comma-separated format: "tripId,riderId,driverId,tripStatus,pickupX,pickupY,destinationX,destinationY,zoneId,surgeMultiplierPercentage,fareInCents,paymentStatus,paymentAttempts".
• Before completion, fareInCents is 0.
• Before payment becomes applicable, paymentStatus is NOT_STARTED.

Constraints

• 1 ≤ baseFareInCents ≤ 1,000,000
• 0 ≤ farePerDistanceUnitInCents ≤ 1,000,000
• 1 ≤ maxPaymentAttempts ≤ 10
• 0 ≤ drivers.size() ≤ 100,000
• Every driver entry contains exactly four comma-separated values.
• All supplied driverId and other id values are globally unique.
• 1 ≤ riderId.length(), driverId.length(), tripId.length() ≤ 100
• 1 ≤ riderName.length(), driverName.length() ≤ 100
• 1 ≤ zoneId.length(), paymentMethodId.length(), paymentRequestId.length() ≤ 100
• -1,000,000 ≤ locationX, locationY, pickupX, pickupY, destinationX, destinationY ≤ 1,000,000
• 0 ≤ activeRequests, availableDrivers ≤ 1,000,000
• 0 ≤ estimatedDistanceUnits, actualDistanceUnits ≤ 1,000,000
• 1 ≤ total method calls ≤ 100,000
• All names and identifiers contain only lowercase English letters, digits, spaces, and hyphens.
• All string parameters are nonempty.
• All fare calculations fit in a signed 64-bit integer.
• Method calls are processed sequentially.

Examples

Example 1

new RideHailingSystem(baseFareInCents = 200, farePerDistanceUnitInCents = 50, maxPaymentAttempts = 3, drivers = ["driver-9,aman,2,1", "driver-3,ravi,0,3"])

addRider(riderId = "rider-2", riderName = "maya")
Output: true

updateSurgePricing(zoneId = "north", activeRequests = 4, availableDrivers = 2)
Output: 150

estimateFare(zoneId = "north", estimatedDistanceUnits = 8)
Output: 900

requestTrip(tripId = "trip-7", riderId = "rider-2", pickupX = 0, pickupY = 0, destinationX = 8, destinationY = 0, zoneId = "north", paymentMethodId = "card-2")
Output: "driver-9"

Driver driver-9 has squared distance 5 from the pickup, while driver-3 has squared distance 9.

getTripDetails(tripId = "trip-7")
Output: "trip-7,rider-2,driver-9,REQUESTED,0,0,8,0,north,150,0,NOT_STARTED,0"

acceptTrip(tripId = "trip-7", driverId = "driver-9")
Output: true

startTrip(tripId = "trip-7", driverId = "driver-9")
Output: true

completeTrip(tripId = "trip-7", driverId = "driver-9", actualDistanceUnits = 8)
Output: 900

The subtotal is 200 + 8 × 50 = 600. Applying the stored 150% multiplier produces a final fare of 900.

processPayment(tripId = "trip-7", paymentRequestId = "payment-attempt-1", gatewaySuccessful = false)
Output: "RETRY_PENDING"

processPayment(tripId = "trip-7", paymentRequestId = "payment-attempt-1", gatewaySuccessful = true)
Output: "RETRY_PENDING"

The repeated request returns its cached result and does not create another payment attempt.

processPayment(tripId = "trip-7", paymentRequestId = "payment-attempt-2", gatewaySuccessful = true)
Output: "SUCCEEDED"

getTripDetails(tripId = "trip-7")
Output: "trip-7,rider-2,driver-9,COMPLETED,0,0,8,0,north,150,900,SUCCEEDED,2"

Example 2

new RideHailingSystem(baseFareInCents = 100, farePerDistanceUnitInCents = 20, maxPaymentAttempts = 2, drivers = ["driver-z,kabir,1,0", "driver-a,sara,-1,0"])

addRider(riderId = "rider-8", riderName = "neha")
Output: true

requestTrip(tripId = "trip-9", riderId = "rider-8", pickupX = 0, pickupY = 0, destinationX = 5, destinationY = 5, zoneId = "central", paymentMethodId = "card-8")
Output: "driver-a"

Both drivers have the same squared distance from the pickup, so the lexicographically smaller identifier is selected. The unchanged zone uses the default multiplier of 100.

cancelTrip(tripId = "trip-9", requesterId = "another-rider")
Output: false

cancelTrip(tripId = "trip-9", requesterId = "driver-a")
Output: true

getTripDetails(tripId = "trip-9")
Output: "trip-9,rider-8,driver-a,CANCELLED,0,0,5,5,central,100,0,NOT_STARTED,0"