Machine coding · not HLD
Ride matching
A rider taps request. Three nearby idle drivers exist on a plain list. Only one may become MATCHED. If ranking and assignment share one mutable step, two riders can claim the same driver.
In-process matching is a list of Driver objects, a , and an atomic step. is a state machine. is two numbers plus a crude distance. Geo indexes, dispatch queues, and surge belong on the related System Design note: Ride-hailing .
This room vs HLD
Two numbers plus a distance function, not a maps SDK.
Ranks idle drivers; assignment stays on Driver.tryAssign.
Compare-and-set Idle to OnTrip so only one rider wins.
The other room
Geo-hash shards, surge, Redis, ETA ML: open the System Design note.
How do I match in one process?
The three-driver story above is the default prompt: assign one idle driver without inventing Redis. Rider, Driver, and are entities. Availability is driver state. Matching is a . Distance can be crude. A value object is enough. The matcher returns a ranked list. calls in order; if none succeed, the trip fails.
Two riders must not get the same driver. tryAssign is atomic, like occupy on a parking spot. The strategy reads a snapshot of idle drivers; assignment still goes through the driver object. Pricing and ETA are follow-ups. A PricingStrategy can wait. The grade is clear trip states, a swappable matcher, and no God DispatchManager that also bills and sends SMS. See Strategy and HLD vs LLD.
How to explain this in an interview
Once the rider request is on the table, three questions decide how much system you draw.
1. Can ranking stay a pure function? Yes. A returns ordered idle drivers. Assignment stays on . If the matcher calls setOnTrip, you cannot retry cleanly.
2. How do two riders not share a driver? Driver status flips with . loops the ranked list until one compare-and-set succeeds or the trip fails.
3. Did someone say Uber scale? Geo-hash shards, surge, and ETA ML belong on the related System Design note (see the hero link). Keep the class diagram finishable this afternoon. Do not open with a region map.
Simple rule of thumb
Strategy ranks. Driver.tryAssign owns the claim. Trip rejects illegal jumps. City scale is the other note.
From problem to mechanism
Here is the request slowed down so you can see which type owns each verb, then the responsibility walk.
Problem. One rider, several idle drivers, one MATCHED trip. Ranking and assignment must not share a single mutable step.
Naive system. A DispatchManager that ranks, sets ON_TRIP, bills, and texts. That couples every follow-up into one God object.
Mechanism. ranks. Driver. compare-and-sets Idle to OnTrip. loops until one wins or the trip fails. owns legal transitions only.
| Type | Does | Does not |
|---|---|---|
| MatchingStrategy | Rank idle drivers | Mutate driver status |
| Driver | tryAssign CAS | Bill the rider |
| Trip | Legal state transitions | SMS, maps SDK |
| DispatchService | rank, loop tryAssign, create Trip | Own surge formulas (follow-up) |
Trip arrows
The mechanism above needs legal transitions. REQUESTED becomes MATCHED only after a successful tryAssign.
Read the diagram definition
stateDiagram-v2
[*] --> REQUESTED
REQUESTED --> MATCHED: tryAssign driver
REQUESTED --> FAILED: no idle driver
MATCHED --> IN_PROGRESS: start
MATCHED --> CANCELLED: rider or driver
IN_PROGRESS --> COMPLETED: dropoff
IN_PROGRESS --> CANCELLED: policy may forbid
FAILED --> [*]
COMPLETED --> [*]
CANCELLED --> [*]Java API sketch
The same four roles as Java. Notice rank stays pure and tryAssign owns the status flip.
final class Location {
final double lat;
final double lon;
double distanceTo(Location other) { /* crude; not a real map */ }
}
interface MatchingStrategy {
/** Ranked candidates; assignment stays on Driver.tryAssign. */
List<Driver> rank(RideRequest request, List<Driver> idle);
}
class NearestDriver implements MatchingStrategy {
public List<Driver> rank(RideRequest request, List<Driver> idle) {
return idle.stream()
.sorted(Comparator.comparingDouble(d -> d.location().distanceTo(request.pickup())))
.toList();
}
}
class Driver {
private final AtomicReference<DriverStatus> status =
new AtomicReference<>(DriverStatus.IDLE);
boolean tryAssign() {
return status.compareAndSet(DriverStatus.IDLE, DriverStatus.ON_TRIP);
}
boolean goIdle() {
return status.compareAndSet(DriverStatus.ON_TRIP, DriverStatus.IDLE);
}
}
class DispatchService {
private final MatchingStrategy matcher;
Trip requestRide(RideRequest request) {
List<Driver> ranked = matcher.rank(request, snapshotIdle());
for (Driver d : ranked) {
if (d.tryAssign()) return Trip.matched(request, d);
}
return Trip.failed(request);
}
}Stale idle snapshot
The sketch above is the API. This is the playbook you write in the round: a lost assign between snapshot and claim, then the seam test that proves retry.
Matcher ranks D1 then D2. Between choose and , another rider took D1. tryAssign fails. Loop to D2. If the had set ON_TRIP itself, you could not retry cleanly and you coupled ranking to mutation. Two riders, one driver, both MATCHED is the lost : the grade of this machine-coding round, same as parking occupy.
is two doubles and a crude distance. You do not need a road network. When they ask Uber scale, open the related System Design note. Keep finishable this afternoon: strategy, CAS, trip states, and no SMS or billing mixed in.
- 01
Location
Value with a simple distance function so nearest ranking stays testable.
- 02
Matcher
Pure ranking over idle drivers; returns an ordered list only.
- 03
Driver
tryAssign CAS claims Idle to OnTrip; failed claims retry next.
- 04
Trip
REQUESTED to MATCHED to IN_PROGRESS to COMPLETED; illegal jumps throw.
Tests that prove the seams
@Test
void lostAssignRetriesNextCandidate() {
Driver d1 = Driver.idle("d1");
Driver d2 = Driver.idle("d2");
d1.tryAssign(); // stolen between snapshot and assign
DispatchService dispatch = new DispatchService(new NearestDriver());
Trip trip = dispatch.requestRide(reqNear(d1, d2));
assertEquals("d2", trip.driver().id());
}Matcher mutates status
If the matcher mutates status, you cannot safely retry ranking after a lost CAS.
Two MATCHED one driver
Two MATCHED trips on one driver means a lost compare-and-set.
Invalid cases, concurrency, and follow-ups
The playbook works until someone mutates in the matcher, skips CAS, or designs city scale in forty-five minutes. These are the misses, then the retry loop, then what a follow-up actually changes.
Invalid cases
- Assign a driver already ON_TRIP: tryAssign fails; retry the next ranked idle driver.
- COMPLETE from REQUESTED: illegal transition; must MATCH then reach IN_PROGRESS.
- Matcher that calls driver.setOnTrip(): strategy stops being a pure ranking function.
- Opening with geo-hash shards: System Design interview, not this machine-coding round.
- Two trips, same driver, both MATCHED: lost CAS; idle snapshot was stale.
Concurrency
The can rank a driver who is stolen between snapshot and assign. Loop: choose, , if false choose next. Same pattern as parking allocation retry after failed occupy. Empty ranked list or all CAS fails means fail or stay REQUESTED: say which.
What the follow-up changes
- Highest rating: new MatchingStrategy class; DispatchService stays unchanged.
- Pricing or ETA: collaborators on Trip start, not on the matcher.
- City scale: open the related System Design note; keep this diagram finishable today.
Still fails when…
- Matcher mutates status, so a lost CAS cannot retry the next ranked driver.
- Trip allows COMPLETE from REQUESTED because transitions were never validated.
- DispatchService also bills and texts, so every follow-up edits the same class.
Trade-offs
- Crude distance beats a maps SDK here; road networks wait for System Design.
- Pure ranking enables retry; mutating in the matcher couples claim to sort order.
- Swappable strategies keep rating follow-ups cheap; God dispatch makes them expensive.
Wrap-up
You have the story, the CAS loop, and the seam test. Use the forty-five minute split as a clock, then follow the related notes.
Forty-five minutes
- 0–8Location plus NearestDriver ranking on a list of two idle drivers.
- 8–20tryAssign CAS so a second rider loses D1 and receives D2.
- 20–32Trip MATCHED to IN_PROGRESS; COMPLETE from REQUESTED throws.
- 32–40Keep the matcher pure; assignment stays on Driver.tryAssign only.
- 40–45Name the related Uber System Design note for city-scale questions.
Read next
You're done when
Ranking is a strategy over idle drivers, tryAssign is compare-and-set so two riders cannot MATCH the same driver, the matcher does not mutate driver status itself, and illegal trip transitions (for example COMPLETE from REQUESTED) throw. Surge and geo-hash shards belong on the related System Design note.