Ride Hailing Service

On-Demand Transportation Platform

Design the object model of a ride hailing service: riders request trips, a grid index finds the nearest free drivers, offers go out one driver at a time, fares come from a swappable policy, and a trip moves through a fixed set of states.

Overview

A rider asks for a car from one place to another. The service finds free drivers near the pickup, offers the trip to the nearest one, moves on if that driver declines, and once a driver accepts it tracks the trip until drop-off and charges a fare. Drivers move all the time, so the structure that answers 'who is near this point' must be cheap to update as well as to query.

This is a design exercise; it does not describe how any real company builds its dispatch. Interviewers pick it because it combines a spatial lookup (a grid index), a two-sided handshake (offer, accept or decline), a pluggable price (fare policy with surge as a wrapper), and a race (two riders must not be offered the same driver). A strong answer draws the trip states first, keeps the index as a dictionary of cells, offers to one driver at a time, and puts the whole offer step under one lock.

Money is whole cents, and the fare is computed by a policy object so that surge, promotions and vehicle classes are new classes rather than new branches.

Scoping the problem

Offer to one driver at a time, or broadcast to several? — Broadcast needs a first-accept-wins rule; one at a time needs a timeout — One at a time, nearest first, with decline and timeout
One vehicle class or several? — A class is a filter on candidates and a different fare policy — Start with one; show where the filter and the policy go
How is the fare estimated before the trip? — Straight-line distance at an assumed speed is enough for the model — Estimate up front, charge the measured trip at the end
Is surge in scope? — Surge is a multiplier on the base policy, not a new lifecycle — Yes, as a wrapper around the standard fare
How often do drivers report position? — Sets the update rate the index must absorb — Every few seconds; the index update is O(1)
Payments, ratings, maps? — Each is its own service — Out of scope; name the interface

The trip lifecycle

A trip is requested, offered to a driver, matched when one accepts, and then walks through arrival, the ride and completion. A decline keeps the trip in Offered and moves the offer to the next driver. When the candidates run out the trip ends as NoDriver.

The driver has its own small status: Free, Offered, OnTrip, Offline. An offer moves the driver to Offered so no other trip can be offered to them while they decide; an accept moves them to OnTrip; a decline, a cancel or a completion moves them back to Free.

Finding drivers near a point

The index is a dictionary from a grid cell to the drivers in it. A cell is the pair of integers you get by dividing latitude and longitude by the cell size and rounding down. With a cell of 0.01 degrees, a cell is about 1.11 km tall (6,371 km times pi over 180 times 0.01). A query reads only the cells a radius can touch and then sorts those drivers by their exact distance.

Ana — 0.01 degrees north — about 1.11 km — (3778, -12242) — yes, first
Ben — 0.02 degrees west — about 1.76 km — (3777, -12244) — yes, second
Cy — 0.04 degrees north — about 4.45 km — (3781, -12242) — no

When Ana drives 0.03 degrees west, move removes her from her old cell and adds her to the new one: two set operations, no rebuild. The next query sees her at about 2.64 km and ranks Ben first.

List scan — O(all drivers) — O(1) — interview demo, a few hundred drivers
Grid of cells (the code) — O(drivers in nearby cells) — O(1) — one city, in one process
Redis geo set — O(N + log M): N in the bounding box, M inside the shape — one GEOADD — a shared index across servers
H3 hexagons — neighbors of the pickup cell — recompute the cell id — analysis and pricing by area; resolution 8 cells have edges of about 0.53 km

Pricing

The fare policy is an interface with one method: cents for a distance and a duration. StandardFare is base plus per-kilometer plus per-minute with a minimum. SurgeFare wraps any policy and multiplies the result, and refuses a multiplier below 1. The dispatcher never knows which one it holds, so surge is turned on by handing it a different object.

1 km, 2 min — Standard (250 base, 120 per km, 30 per min, 600 minimum) — 250 + 120 + 60 = 430, below the minimum — 600
10 km, 20 min — Standard — 250 + 1,200 + 600 — 2,050
10 km, 20 min — Surge 1.5 over Standard — 2,050 times 1.5 — 3,075
18.2 km, 26 min (the completed demo trip) — Standard — 250 + 2,184 + 780 — 3,214

The estimate shown before the trip uses the straight-line distance at an assumed 30 km/h; the charge at the end uses the measured distance and time. Both numbers are stored on the trip so a dispute can compare them.

Thread safety

Ten riders can call request in the same instant. If each one reads the free drivers and then marks its pick, two of them read the same free driver and both offer him the trip. The dispatcher therefore does the whole step under one threading.Lock: query the index, skip drivers who are not Free or who declined, mark the chosen driver Offered, move the trip to Offered. A decline is the same locked step run again from the next candidate. The demo fires ten requests from ten threads at two free drivers and asserts that exactly two trips are Offered, to two different drivers, and eight end as NoDriver.

What you will be able to do

Draw the trip and driver state machines and enforce the trip's with one transitions table.
Build a grid index by hand, explain its query and update costs, and say when to replace it with Redis geo commands or a hexagonal grid.
Run the offer handshake one driver at a time with declines, and say why the offer step is locked.
Price a trip with a policy object and add surge as a wrapper without touching the dispatcher.
Explain how estimate and final fare differ and why both are stored.

Functional requirements

Request a trip from a pickup to a drop-off; the trip gets an estimate in cents up front
Find the free drivers within a radius of the pickup, nearest first, from a grid index that drivers move through
Offer the trip to one driver at a time; a decline moves the offer to the next candidate; no candidate ends the trip as NoDriver
Move a trip through Requested, Offered, Matched, Arrived, InProgress and Completed, refusing any other move
Charge the completed trip from the measured distance and time through the fare policy, with surge as a wrapper
Cancel a trip and free its driver

Non-functional requirements

A driver holds at most one offer or trip at a time: the offer step runs under one lock
Index update on a position report is O(1): remove from the old cell, add to the new one
The fare policy is swappable at runtime without changing the dispatcher or the trips
Money is integer cents; estimates and fares are both kept on the trip
Every status change is recorded in the trip history

Interview questions

Why offer to one driver at a time instead of broadcasting to everyone nearby?
How does surge pricing fit the design?
Drivers report a new position every few seconds. How does the index keep up?
Two riders request at the same moment and there is one free driver. Walk through what happens.
What do you store, and how do you handle a driver app that sends accept twice?