Notes
Requirements
Fix the scope. A rider requests a trip with a pickup, a drop and a cab type. We match the nearest free driver of that type. The driver starts and ends the trip, and the fare is a base plus a rate per kilometre and per minute, times a surge multiplier at peak times. The rider can cancel before the trip starts and rate the driver after. Both sides get live updates. Real maps and payment are out of scope.
Ask what changes the code. How far do we look for drivers? Eight kilometres. Does the driver accept, or do we assign automatically? Auto-assign for now, with accept as a follow-up. Two drivers at the same distance? The higher rating wins. Can a rider cancel after the trip starts? No. Each answer lands in exactly one class, which shows the interviewer you think in responsibilities.
- rider requests: pickup, drop,
- cab type (mini, sedan, SUV)
- match the nearest free driver
- driver starts and ends the trip
- fare: base + per km + per minute
- surge multiplier at peak times
- rider can cancel before start
- rate the driver after the trip
- live updates to both sides
- out of scope: maps, payments
- how far to look for drivers?
- within 8 km
- driver must accept, or auto?
- auto-assign for now
- tie on distance?
- higher rating wins
- cancel after the trip starts?
- no
- pool rides?
- later, as an extension
Entities
Underline the nouns: rider, driver, trip, location. A location is an immutable record with a distance method. A driver has a cab type, a status of offline, available or on trip, a current location and a rating. A trip has the rider, pickup and drop, the cab type, a state, the assigned driver and the fare. A rider needs no class of its own yet; an id is enough until profiles or wallets appear.
record Location(double x, double y)
enum CabType { MINI, SEDAN, SUV }
enum DriverStatus { OFFLINE,
AVAILABLE, ON_TRIP }
class Driver: id, type, status,
location, rating
class Trip: id, rider, from, to,
type, state, driver, fare State machine
The trip is a state machine. Requested becomes accepted when a driver is matched. Accepted becomes started at pickup, or cancelled if the rider cancels. Started becomes completed at the drop. Nothing else is allowed. Write it as one move method that takes the expected current state and the next one, and throws on anything else, so a bug like starting a cancelled trip fails loudly instead of corrupting data.
Here is that method. It is synchronized, so a driver tapping start and a rider tapping cancel at the same moment cannot both succeed: whichever runs first changes the state, and the other sees the wrong current state and gets a clear error. Every public action, start, complete and cancel, is a single call to move with its expected from-state.
- REQUESTED
- -> ACCEPTED (driver matched)
- ACCEPTED
- -> STARTED (rider picked up)
- -> CANCELLED (rider cancels)
- STARTED
- -> COMPLETED (drop reached)
- anything else: throw
synchronized void move(TripState from,
TripState next) {
if (state != from)
throw new IllegalStateException(
id + ": cannot go " + state
+ " -> " + next);
state = next;
}
start(): move(ACCEPTED, STARTED) Strategy: matching
Which driver gets the ride is a business policy that will change, so it sits behind an interface: the Strategy pattern. Our default filters to free drivers of the right type within eight kilometres, sorts by distance and breaks ties by rating. Later the business may want road travel time, acceptance rate or fairness so every driver gets work. Each is a new class; the booking service never changes.
interface MatchingStrategy {
List<Driver> rank(DriverSource d,
Trip trip);
}
NearestDriver: right type, free,
within 8 km, nearest first,
then higher rating
later: ETA by road, acceptance
rate, driver fairness Flow: request
The request flow. Create the trip, ask the strategy for ranked candidates, and try to claim each driver in order. If a claim fails because another rider just took that driver, move to the next. On success, attach the driver, move the trip to accepted, store it and tell listeners. If nobody is free, return empty so the app can show no cabs nearby instead of throwing an exception for an everyday case.
Trip trip = new Trip(nextId(), ...)
for (Driver d : matching.rank(..)) {
if (!d.claim()) continue;
trip.driver = d;
trip.move(REQUESTED, ACCEPTED);
trips.put(trip.id, trip);
publish(trip);
return Optional.of(trip);
}
return Optional.empty(); // no cab Concurrency
Now the key concurrency point. Two riders standing on the same corner both rank driver D1 first. If claiming were check the status, then set it, both could win and one driver would get two trips. Instead the status is an atomic reference and claiming is a compare-and-set from available to on trip. Exactly one rider wins; the other simply tries the next driver in their list. No global lock, so riders never wait on each other.
AtomicReference<DriverStatus> status
boolean claim() {
return status.compareAndSet(
AVAILABLE, ON_TRIP);
}
A and B both rank D1 first
A: AVAILABLE -> ON_TRIP, true
B: expected AVAILABLE, false Strategy: fare
The fare is a second strategy. Metered fare charges a base, a rate per kilometre and a rate per minute for the cab type, times the surge multiplier. A ten kilometre, twenty minute sedan ride is two hundred and sixty. Flat airport fares or subscriptions are new classes. Surge comes from a supplier, so a test can set it directly, and money stays as whole paise in a long, never a floating point number.
fare = (base + perKm * km
+ perMin * minutes) * surge
sedan: 70 + 15/km + 2/min
10 km, 20 min = 260.00
mini at 1.5x surge:
5 km, 10 min = 187.50
surge is a Supplier<Double>,
so tests set it directly Observer: updates
Live updates use the Observer pattern. Each interested part registers a trip listener: the rider's push notifications, the driver's app, the receipt emailer, analytics. After every state change the service publishes the trip and its new state. Adding a new subscriber never touches the booking code, and a copy-on-write list lets subscribers join while trips are running.
interface TripListener {
void onChange(Trip t, TripState s);
}
listeners = new CopyOnWriteArrayList
subscribers: rider push, driver
app, receipts, analytics Flow: finish
Finishing a trip moves it from started to completed, prices it from the distance and the time taken, and frees the driver at the drop point so the next match uses their new location. Cancel moves accepted to cancelled and frees the driver where they stand. Rating is allowed only on a completed trip, and the driver keeps a running sum and count so the average is cheap to read.
complete(id): move(STARTED, COMPLETED) fare = fares.fareCents(t, km, took) driver.finishTrip(t.to) cancel(id): move(ACCEPTED, CANCELLED) driver back to AVAILABLE rate(id, stars): only on a COMPLETED trip
Concurrency
Go through every shared field. Driver status is atomic and claimed with compare-and-set. Driver location is volatile so a new position is visible to the matcher at once. Trip state changes only inside the synchronized move method. Drivers and trips live in concurrent hash maps, ids come from an atomic counter, ratings are two atomic longs, and listeners sit in a copy-on-write list.
- driver status: AtomicReference
- claimed with compare-and-set
- driver location: volatile
- trip state: synchronized move()
- trips, drivers: ConcurrentHashMap
- trip ids: AtomicLong
- ratings: AtomicLong sum + count
- listeners: CopyOnWriteArrayList
- records: immutable
Extensibility
Now the follow-ups. Drivers accept or decline? Add an offered state with a timeout, and on decline try the next driver. Pool rides? A trip with several stops. Scheduled rides? Run the matcher ten minutes before pickup. Too many drivers to scan? Index them by grid cell or geohash and search only nearby cells. Payments listen for completed trips. Almost every change is a new state, a new strategy or a new listener.
- driver accepts or declines:
- OFFERED state, timeout, next
- pool rides: a Trip with stops
- scheduled rides: matcher runs
- 10 minutes before pickup
- fast nearest search: grid or
- geohash cells, not a full scan
- payments, wallet: on COMPLETED,
- via a listener
- many cities: one app per city
Testing
The full code is below the player. The demo matches the nearest sedan and prices a ten kilometre ride with a fake clock, cancels a trip and shows the driver is free again, proves a cancelled trip cannot start, applies a one and a half times surge, and finally lets twelve riders request a sedan at once when only two exist. Exactly two are matched, to two different drivers, every run.
asha matched with D1 (nearest) asha fare 10 km, 20 min: 260.00 ravi matched with D2, cancels D2 free again: true start after cancel: cannot go CANCELLED -> STARTED mini, surge 1.5x: 187.50 Race: 12 riders, 2 sedans, matched 2, drivers [D1, D2]
Say it like this
Here is the version to say out loud. Riders request trips, and a trip is a state machine with one guarded move method. Matching and fares are strategies, and live updates are observers. A driver is claimed with a compare-and-set on its status, so two riders never get the same driver, and the loser simply tries the next one.
- "Riders request trips; a Trip is
- a state machine with one guarded
- move(). Matching and fares are
- strategies; updates are
- observers. A driver is claimed
- with compare-and-set on its
- status, so two riders never get
- the same driver."