Ride sharing (Uber / Ola)

The idea

What it is

“Design a ride-hailing service like Uber.” That is the whole prompt. It is deliberately enormous, and the first thing being graded is whether you cut it down to something you can actually build in ninety minutes.

Almost everyone starts drawing Rider, Driver, Trip, Payment, Rating, Notification. That is a list, not a design. The problem has exactly one hard part, and it is this: a rider taps a button, and out of fifty thousand drivers, one specific driver must be found, offered the ride, and — if they do not answer in fifteen seconds — replaced.

The whole lesson in one line

Matching is the problem. Everything else is paperwork. Three things make matching work: you partition space so you never look at every driver, you offer to one driver at a time with a deadline instead of broadcasting, and you flip the driver's state atomically so two riders can never win the same car. Get those three right and the rest of the round is bookkeeping you can do half-asleep.

Every noun in the scene is a class you will write. But notice the last line on the right: the three things that actually decide whether this design works — GeoIndex, MatchingStrategy, PricingStrategy — are invisible in the real-world picture. That is why listing nouns is not designing.

Here is the naive matcher that almost every candidate writes first, and it is the exact thing the round is testing:

the loop that loses the round

// Find a driver for this rider.
for (Driver d : allDrivers) {                 // <- 50,000 iterations
    if (d.state == AVAILABLE && distance(d.location, pickup) < 3000) {
        candidates.add(d);
    }
}
// ...and this runs on EVERY ride request, in a city that has
// hundreds of ride requests per second. It is O(all drivers), forever.

It works. It is also the wrong shape, and the interviewer will ask “what happens at fifty thousand drivers?” the moment you type it. The fix is not a faster loop — it is not looking at most of the drivers at all.

What is actually being graded

Did you partition space? A Map<CellId, Set<Driver>> and a search over the rider's cell plus its eight neighbours. If your answer to “how do you find nearby drivers” is a loop over a list, the rest of the round is uphill.
Does the index survive movement? Drivers move every four seconds. updateLocation() must be remove from the old cell, add to the new cell — O(1). If you reached for a sorted list, say why you did not.
Is the ride offered to one driver at a time, with a deadline? Broadcasting to twenty drivers is the tempting wrong answer, and it recreates the double-booking problem you were trying to avoid.
Is “one driver, one ride” enforced by a compare-and-set? Two ride requests can pick the same nearest driver in the same millisecond. Only an atomic AVAILABLE → OFFERED flip decides which one wins (Atomic operations & CAS).
Is money an integer, and is surge a swappable rule? Fare is base + per-km + per-minute, multiplied by a surge factor, in paise, behind a PricingStrategy (Strategy) so a new pricing rule costs one class and zero edits to the matcher.
Does it run? A main() that requests a ride, watches driver #1 time out, offers #2, accepts, completes, and prints a fare breakdown. Plus the failure path: no cars available.

Say the right-hand column out loud in the first three minutes. Then never mention it again. The three orange lines on the left are the only things anyone remembers about your answer.

Row four is the point of the whole table. The most important class in this design is not a noun anybody said out loud. Interviewers watch for exactly this: can you invent the structure the requirements imply but never name? (Identifying entities, attributes & behaviors)

Mechanics

How it works

Step 1 · Clarify — 5 minutes

The prompt is one sentence, so the questions matter more here than in any other problem in this set. Ask these six, in this order, and write the answers on the board.

How do I find nearby drivers? — ask it as “can I assume I have a geo index, or should I build one?”. They will say build one. That is the interviewer handing you the actual problem; take it.
How many drivers are online in a city? — the number you want is tens of thousands. Say it back: “so a linear scan per request is fifty thousand distance calculations, hundreds of times a second — I will partition space instead.”
Do I offer the ride to one driver or many? — the question that decides your whole dispatch design. Say “one at a time with a timeout” and explain why in a sentence.
What happens when a driver does not respond? — get them to say a number. Fifteen seconds is the industry answer. Now you have a deadline in your design instead of a vague “eventually”.
Is pricing fixed or dynamic? — surge is the follow-up they always ask, so pull it forward. “I will put pricing behind an interface so surge is one class.”
Pool rides, scheduled rides, ratings, payments? — out of scope for the first pass, and each is a two-sentence follow-up you will answer at the end. Say that now so the scope is agreed.

The trap in minute one

The instinct is to start with Ride and its state machine, because it is the comfortable part. Do not. A perfect ride state machine with a linear driver scan fails this round. A rough state machine with a real geo index and a compare-and-set on the driver passes it. Build in the order the grade is in.

Step 2 · You cannot scan every driver. Partition space.

Do the arithmetic out loud, because the arithmetic is the argument. Fifty thousand drivers online. A ride request arrives. The naive loop does fifty thousand distance calculations, and it does them again for the next request, and the one after that.

Now chop the map into squares. Take a cell of about 0.003 degrees on a side — roughly 330 metres. A 50 km by 50 km city is 2,500 km², so that is about 28,000 cells. Fifty thousand drivers spread over 28,000 cells is under two drivers per cell. Look at the rider's cell plus its eight neighbours — nine cells, about 16 drivers. That is the entire change.

The two numbers at the bottom are the whole section. Say them in the interview with the arithmetic attached — “28,000 cells, 50,000 drivers, under two per cell, nine cells is about sixteen” — because a number you can derive sounds different from a number you memorised.

the index, in twelve lines

/** A geohash by another name: the map chopped into fixed squares. */
final class GeoIndex {
    private static final double CELL_DEG = 0.003;          // ~330 m at the equator

    private final Map<Long, Set<String>> cells = new HashMap<>();   // cell -> driver ids
    private final Map<String, Long> whereIs = new HashMap<>();      // driver id -> cell

    static int row(double lat) { return (int) Math.floor(lat / CELL_DEG); }
    static int col(double lng) { return (int) Math.floor(lng / CELL_DEG); }
    static long cellId(int r, int c) { return ((long) r << 32) | (c & 0xffffffffL); }

    void put(String driverId, Location at) {
        long cell = cellId(row(at.lat()), col(at.lng()));
        Long old = whereIs.get(driverId);
        if (cell == (old == null ? Long.MIN_VALUE : old)) return;   // same cell, nothing to do
        remove(driverId);                                           // O(1) out of the old set
        cells.computeIfAbsent(cell, k -> new HashSet<>()).add(driverId);   // O(1) into the new
        whereIs.put(driverId, cell);
    }

    void remove(String driverId) {
        Long old = whereIs.remove(driverId);
        if (old == null) return;
        Set<String> set = cells.get(old);
        if (set != null && set.remove(driverId) && set.isEmpty()) cells.remove(old);
    }
}

Why the cell size is a real trade-off, and what to say about it

Too big and every cell holds thousands of drivers — you are back to scanning, just with extra steps. Too small and the 3×3 neighbourhood covers 60 metres, finds nobody, and you spend every request expanding rings and visiting hundreds of near-empty cells. Around 300–500 m is the sweet spot for a dense city. The honest sentence is: “the right size depends on driver density, and dense city centres want smaller cells than the suburbs — which is exactly the argument for a quadtree, or S2, or H3, where the cell size adapts. A fixed grid is the right ninety-minute answer and I would name the upgrade path.”

Drivers move. That is the part beginners forget. A driver pings a new location every four seconds, so updateLocation() runs tens of thousands of times a second — far more often than requestRide(). It has to be cheap.

The red column is the answer people reach for when they hear “nearby”. Two dimensions do not sort. A hash of buckets does not have to sort at all — it just needs a key you can compute from a coordinate, which is exactly what a cell id is.

One more piece: what if the nine cells are empty? A rider on the edge of town at 3 a.m. Do not give up, and do not silently widen to the whole city either. Expand in rings.

Two design points hide in this picture. Stop at the first ring that yields anybody — the ring is already a distance filter, so you do not need a second one. And cap the expansion: three rings, then fail. “No cars available right now” is a correct answer; a driver twenty kilometres away is not.

Step 3 · Offer one driver at a time, with a deadline

You now have sixteen nearby drivers, ranked. The obvious next move — send the ride to all of them and let the fastest tap win — is wrong, and it is wrong in an interesting way.

The red bar at the bottom is the sentence to say. Broadcasting does not remove the race — it multiplies it, and it moves the rejection to the worst possible moment: after a human already committed. Sequential offers make the race impossible by construction.

The honest trade-off, and how to say it

Sequential offers cost latency: three declines in a row is forty-five seconds of a rider staring at a spinner. Real systems soften this — shorter deadlines (8–10 s), a small batch of two or three offers with the CAS still deciding the winner, and pre-warming the next candidate while the current one is deciding. Say: “I will start strictly sequential because it makes correctness obvious, and I would tune towards small batches once I had acceptance-rate data.” That is the answer of somebody who has shipped one.

Ranking the candidates is a separate decision from dispatching them, so it goes behind its own interface — MatchingStrategy.rank(pickup, candidates). Straight-line distance is the default. Swap in one that weights the driver's rating, or their acceptance rate, or how long they have been idle, and DispatchService does not change a line (Strategy, Open/Closed (OCP)).

Straight-line distance is right for ranking and wrong for money

For ranking, straight line — haversine, or plain squared Euclidean on a small map — is fine and fast. You are ordering candidates that are all within a kilometre; the road network rarely reorders them, and when it does the cost of being slightly wrong is thirty seconds. For the fare, straight line is simply incorrect: a river or a one-way system can make a 2 km hop an 8 km drive, and a rider charged for the crow's flight will notice. So: RouteService.roadMetres(a, b) behind an interface, stubbed as haversine × 1.35 in the round, and one sentence saying a real system calls a routing engine. Two different distances, two different purposes, said out loud — that is a whole grading point.

Step 4 · One driver, one ride — enforced by a compare-and-set

Two riders in the same neighbourhood tap Book in the same millisecond. Both requests query the index. Both get the same nine cells. Both rank the same list. Both pick d3, because d3 really is the nearest car for both of them. Now what?

The naive dispatcher does this, and it is the single most common bug in this problem:

check-then-act — the bug

Driver d = candidates.get(0);
if (d.state == AVAILABLE) {        // thread A reads AVAILABLE. thread B reads AVAILABLE.
    d.state = OFFERED;             // thread A writes.        thread B writes.
    d.rideId = ride.id;            // ...and one of these rides just vanished.
    return d;                      // BOTH riders are told "d3 is on the way".
}

The gap between the if and the assignment is where the second rider gets stolen. The fix is to make reading and writing one indivisible step: a compare-and-set that says “change this driver from AVAILABLE to OFFERED, but only if it is still AVAILABLE”. Exactly one of the two calls returns true. The loser does not crash and does not retry blindly — it moves to candidate #2 and offers there.

Look at the bottom row. The losing request does not fail — it just walks one step down its own ranked list. That is what makes a CAS the right tool here rather than a lock: there is nothing to wait for, because there is always another car.

the whole guarantee, in one method

enum DriverState { OFFLINE, AVAILABLE, OFFERED, ON_TRIP }

/** state + rideId + deadline swapped together, so they can never disagree. */
record Slot(DriverState state, String rideId, long expiresAt) {}

final class Driver {
    final String id;
    private final AtomicReference<Slot> slot =
        new AtomicReference<>(new Slot(DriverState.OFFLINE, null, 0L));

    /** Exactly one concurrent caller can win this. That is the entire invariant. */
    boolean tryOffer(String rideId, long expiresAt) {
        Slot cur = slot.get();
        if (cur.state() != DriverState.AVAILABLE) return false;
        return slot.compareAndSet(cur, new Slot(DriverState.OFFERED, rideId, expiresAt));
    }

    /** The driver tapped Accept. Only valid for the ride they were actually offered. */
    boolean confirm(String rideId) {
        Slot cur = slot.get();
        if (cur.state() != DriverState.OFFERED || !rideId.equals(cur.rideId())) return false;
        return slot.compareAndSet(cur, new Slot(DriverState.ON_TRIP, rideId, 0L));
    }

    /** Declined, timed out, or the trip finished — back into the pool. */
    boolean release(String rideId) {
        Slot cur = slot.get();
        if (cur.state() == DriverState.OFFLINE || !rideId.equals(cur.rideId())) return false;
        return slot.compareAndSet(cur, new Slot(DriverState.AVAILABLE, null, 0L));
    }
}

The one line that prevents most of the bugs

A driver in OFFERED or ON_TRIP is not in the matchable index. Remove them on the successful tryOffer, put them back on decline, timeout or trip completion. Once that is true, a driver who is mid-offer is not even a candidate for the next request, so the CAS almost never has to lose — it is there for the microsecond-wide window, not as the everyday mechanism. Say this while you write tryOffer and you have answered the next three follow-ups at once.

Read the small table on the right first. One state is in the index. That single fact is what turns “stop two riders getting the same car” from a hard concurrency problem into a bookkeeping one — with the CAS left as a cheap guard for the last microsecond. More on the mechanism in Atomic operations & CAS; on why a lock is the heavier alternative, Locks, Mutex, Semaphore.

Why not just synchronized around the whole dispatcher?

You can, and for a ninety-minute round nobody will fail you for it. But say what it costs: one global lock serialises every ride request in the entire city, including the thousands that are nowhere near each other and could never contend. The contended thing is one driver, so the guard belongs on one driver. That is the difference between a lock around the system and an atomic operation on the resource — and interviewers listen for exactly that sentence (Deadlock, race conditions, starvation).

Step 5 · The class diagram

DispatchService is the hub, and everything it depends on is an interface it could not name a vendor for. Four seams — matching, pricing, routing, and the index itself — and the two that interviewers push on (a new ranking signal, a new pricing rule) are both one new class and zero edits. Notation: Class diagrams.

Two lines carry the whole flow. geoIndex.remove(d3) the instant the offer lands — so no other request can even see that car — and tick(now) as the thing that expires offers, because time is a parameter you pass in, not a clock you read. That is what makes this whole path testable. Notation: Sequence diagrams.

The `Ride` state machine (supporting cast, but they will ask)

Once a driver has accepted, the ride walks a short, boring path. Boring is the goal — the interesting concurrency all happened before MATCHED.

REQUESTED → the rider tapped, offers are going out. Nobody is committed yet.
MATCHED → a driver confirmed. This is the first state a rider is allowed to see a name and a number plate in.
DRIVER_ARRIVED → the car is at the pickup. Starts the free-waiting clock, which is what a cancellation fee later depends on.
IN_PROGRESS → the rider is in the car. Distance and time start accruing here, not at MATCHED.
COMPLETED → the fare is finalised, and the driver goes back to AVAILABLE and back into the index.
CANCELLED_BY_RIDER / CANCELLED_BY_DRIVER → two different states, not one, because they have different consequences: one may charge the rider, the other counts against the driver's acceptance rate.
NO_DRIVERS_FOUND → the honest terminal state after three rings and an empty candidate list. It is a result, not an exception.

Keep the transitions in one place

ride.transitionTo(next) with an explicit table of legal moves — and every illegal move throws. It is fifteen lines and it kills a whole family of bugs: completing a ride that was cancelled, starting a trip nobody accepted, cancelling twice and charging twice. The deep treatment of this shape is State; here, a switch and a legal-moves map is enough, and saying that it is enough is part of the answer.

Every terminal state must release the driver

Completed, cancelled by either side, or failed — every path ends with driver.release(rideId) and geoIndex.put(driver). Miss one and you have leaked a car: a driver stuck in ON_TRIP forever, invisible to the index, wondering why they get no rides. Put it in a finally, or in one endRide(ride, terminalState) method that every path goes through. This is the single most common silent bug in a working submission.

Step 6 · Fare is a breakdown, not a number

double totalFare is the wrong type and the wrong shape. Wrong type because money in binary floating point drifts. Wrong shape because a rider who is charged ₹277 will ask why, and “277” is not an answer. Return a Fare record with every component kept, in integer paise.

The red box is a real bug that ships. metres / 1000 * perKm in integer arithmetic silently gives away up to 999 metres of every trip. Multiply before you divide, always — and keep the surge as a basis-points integer (18000) rather than a 1.8 double, so the multiplication stays exact.

Upfront quote versus final fare — the question behind the question

Uber shows a price before you book. That number is computed from the estimated route and duration, and it is a promise. The trip then takes a different road and eleven extra minutes. Do you charge the quote or the meter? Both are defensible; what is not defensible is not having thought about it. The clean answer: store both — quotedFare on the Ride at match time, finalFare at completion — charge the quote, and re-price only when reality diverges beyond a threshold (a big detour, a changed destination). Two fields, one rule, and it answers the follow-up completely.

pricing, whole

record Fare(long basePaise, long distancePaise, long timePaise,
            long surgePaise, long totalPaise) {
    String pretty() { return "Rs." + (totalPaise / 100) + "." + String.format("%02d", totalPaise % 100); }
}

interface PricingStrategy { Fare quote(long metres, long seconds); }

/** surgeBps is basis points: 10000 = x1.0, 18000 = x1.8. Integer all the way down. */
final class StandardPricing implements PricingStrategy {
    private final long basePaise, perKmPaise, perMinPaise, surgeBps;

    StandardPricing(long basePaise, long perKmPaise, long perMinPaise, long surgeBps) {
        this.basePaise = basePaise; this.perKmPaise = perKmPaise;
        this.perMinPaise = perMinPaise; this.surgeBps = surgeBps;
    }

    public Fare quote(long metres, long seconds) {
        long distance = metres * perKmPaise / 1000;      // multiply FIRST, then divide
        long time = seconds * perMinPaise / 60;
        long subtotal = basePaise + distance + time;
        long surged = subtotal * surgeBps / 10000;
        long rounded = (surged + 50) / 100 * 100;        // nearest whole rupee
        return new Fare(basePaise, distance, time, rounded - subtotal, rounded);
    }
}

The follow-ups they always ask

Pool / shared rides. A Ride gains a list of stops instead of one pickup and one drop, and matching gains a constraint: “can this car take a second rider without adding more than N minutes of detour for the first?” That is a routing question, so it belongs in the RouteService, and the change to DispatchService is that candidates now include cars in ON_TRIP with a free seat. Say that and stop; a full pool matcher is its own interview.
Scheduled rides. A ride booked for 7 a.m. tomorrow is not matched now — it is a row in a queue with a matchAt timestamp, and a scheduler calls the same requestRide() a few minutes before. No new matching logic at all. That is the answer they want; anything more is over-engineering.
Driver rating. A number on Driver, updated after each completed ride, and a signal that a MatchingStrategy may read. Keep it out of the dispatcher — the whole reason ranking is an interface is so a new signal costs one class.
Cancellation fees. The rule is a function of the ride's state and the clock: free before DRIVER_ARRIVED, or within two minutes of matching; charged after, because the driver already drove. Notice this needs arrivedAt on the Ride, which is why DRIVER_ARRIVED is a real state and not a UI detail.
The driver's app loses network mid-trip. Do not panic and do not cancel. Keep lastSeenAt and lastKnownLocation on the driver, updated by a heartbeat. If the heartbeat stops, the rider's map freezes at the last point and the ride stays IN_PROGRESS — the trip is happening whether or not the pipe is up. If it stops for many minutes while AVAILABLE, sweep the driver to OFFLINE and out of the index, so you never offer a ride to a phone in a tunnel.
A driver who accepts and never moves. Same sweeper, different timer: an accepted ride with no location change and no arrival for several minutes gets auto-cancelled and re-dispatched, and it counts against the driver. Every timeout in this system is some background sweep over ride state — say that once and it covers three questions.
What changes at ten servers? This is the big one, and it is two moves. The GeoIndex becomes a shared store — Redis GEOADD / GEOSEARCH, or a sharded service keyed by cell — because an in-process HashMap on server 3 does not know about the driver whose ping landed on server 7. And the CAS becomes a conditional write in that shared store (a Redis SET ... NX, or a compare-and-set on a row version), because AtomicReference guards one JVM's memory and nothing else. The design does not change — the guarantee just moves to where the state lives.
How would you test it? Fix the clock, then assert: two requestRide calls against a one-driver city produce exactly one match and one NO_DRIVERS_FOUND; an offer at t is dead at t + 15_001 and the driver is back in the index; a completed ride returns the driver to AVAILABLE; and a driver moving across a cell boundary is found by exactly one near() query, not zero and not two.

The 90 minutes

The orange block on the bar is where the grade is, and the green block is where most people run out of time. Write the timeout loop before you make the ranking clever. Then read the bottom row of the table: the two expensive rows are both about state that stopped being local, which is exactly the boundary between this round and a systems-design round.

How this round is lost

for (Driver d : allDrivers). The one thing the problem exists to test, answered with a linear scan. Everything after it is judged as decoration.
An index that cannot handle movement. A sorted list, a static tree built once, anything that makes updateLocation() expensive. Drivers move every four seconds; the index is written a thousand times more often than it is read.
Broadcasting the ride to every nearby driver. It feels faster and it recreates the double-booking race, moving the rejection to after a human committed.
No timeout on the offer. A driver who puts the phone in their pocket freezes that rider forever. If there is no deadline in your design, there is no dispatch in your design.
Check-then-act on the driver's state. Two riders, one car, no compare-and-set, and the bug is invisible in a single-threaded demo — which is exactly why interviewers ask about it instead of waiting to see it.
A driver left in OFFERED or ON_TRIP on some path. A leaked car, permanently invisible. Usually a cancellation branch that forgot to release().
double for the fare, and System.currentTimeMillis() inside the logic. The first drifts; the second makes the fifteen-second timeout impossible to test, so you will never demo the most interesting behaviour you built.
Building the Ride state machine first because it is comfortable. At minute sixty you will have beautiful enum transitions and no matcher.

Interactive prototype

See it. Build it. Break it.

A sandboxed, hands-on simulation — no setup, no install. Play with it as you read.

simulation › Ride sharing (Uber / Ola)

About this simulation

A toy city with fourteen cars and a visible cell grid. Start with the 🔍 Scan everyone / 🧭 Grid lookup toggle and watch the checked counter — 14 in scan mode, 3 in grid mode, and the gap widens every request. Then press 🚕 Request ride and follow the beats: the 3×3 neighbourhood shades, a ranked candidate list appears, and driver #1 gets a 15-second countdown. Press ⏱ Let the offer time out and 🙅 Driver declines to watch the offer walk down to #2 and #3. Finish with ⚔️ Two riders, one driver under 🔓 Unguarded — both riders get the same car and a red ⚠ double-matched: 1 appears — then flip to 🔒 Guarded and run it again.

Hands-on

Try these yourself

Open the prototype above, predict what happens, then verify.

try 01

Count the checks — 14 versus 3

The map opens in 🧭 Grid lookup mode. Press 🚕 Request ride and read the counters: checked this request: 3 and only the rider's cell plus its eight neighbours are shaded. Now press 🔍 Scan everyone and request again — every one of the fourteen pins flashes and the counter reads checked this request: 14. Do it three or four times and watch checked (cumulative) pull apart. Fourteen is a toy; the real number on the left is 50,000, and it is 50,000 again on the next request.

try 02

Watch an offer time out, twice

In grid mode press 🚕 Request ride and stop at the ranked list — three candidates with distance and rating, and #1 gets a visible 15-second countdown. Press ⏱ Let the offer time out: #1 is struck through, goes back into the index, and the offer moves to #2 in front of you. Press 🙅 Driver declines and it moves to #3. Notice what never happens: the other two drivers are never asked at the same time, so there is never a second accept to reject.

try 03

Fail honestly

Press 📡 No cars nearby. The rider pin jumps to the empty corner of the map and the search expands in front of you: ring 1 shades nine cells and finds nobody, ring 2 shades twenty-five and finds nobody, and then the request ends in NO_DRIVERS_FOUND rather than reaching across the city for a car twenty minutes away. Read the call line — the ring number is a parameter, and the cap is a design decision.

try 04

Two riders, one car — the whole point

Press 🔓 Unguarded, then ⚔️ Two riders, one driver. A second rider pin appears, both requests fire in the same tick, both rank the same nearest car, and both are matched to it — the pin turns red and ⚠ double-matched: 1 lights up. Now press 🔒 Guarded and run ⚔️ Two riders, one driver again: one compare-and-set wins, and you can watch the loser re-rank and take the next car in its own list. Same inputs, same ordering, one line of difference.

try 05

Move the cars, change the price, then build it from memory

Press 🚗 Drivers move and watch the call line: geoIndex.update(d7, cell(3,4) → cell(3,5)) — one removal, one insertion, no rebuild. Then flip 🔥 Surge ×1.8 and read the fare card recompute in paise while the badge says matching code changed: 0 lines. Press ↺ Reset, close this, and write it blank-file in this order: GeoIndex.put/remove/near(loc, ring) → Driver.tryOffer() as a CAS → requestRide() with ring expansion and a sequential offer → tick(now) to expire offers → PricingStrategy.quote() in integer paise.

In practice

When to use it — and what trips people up

The shape you just learned

Take the cars and the city away and what is left is assigning a scarce, moving resource to a request, fast, exactly once. Three moves do all the work: an index that shrinks the search space to a bucket, a sequential offer with a deadline instead of a broadcast, and an atomic state flip on the resource so exactly one claim wins. Those three appear together far more often than you would guess.

Food delivery dispatch — the same matcher, but the resource is a courier and the trip has three actors. The geo index and the offer-with-timeout are literally the same code.
Warehouse robot or forklift assignment — a pick request appears at an aisle, and the nearest free robot must be claimed exactly once. Bucketed by aisle instead of by latitude; everything else is identical.
Ambulance and field-technician dispatch — same partition, same one-at-a-time offer, and the deadline is now a legal requirement rather than a UX preference.
Matchmaking in games — bucket by skill rating instead of by geography, then expand the ring when the bucket is thin. The ring expansion is the widening skill tolerance every matchmaker has.
Ad-serving and auction routing — the index shrinks millions of candidate ads to a few hundred by targeting keys, then a ranker orders them. Same two-stage shape: cheap filter, expensive rank.
Any check-then-act on a shared resource — seat holds, inventory reservations, lock acquisition. The compare-and-set here is the same mechanism, and the same bug lives everywhere it is missing (Atomic operations & CAS).

The 30-second version to say out loud

“Drivers live in a Map<CellId, Set<Driver>> keyed by a fixed grid cell, so a request looks at nine cells and about sixteen drivers instead of fifty thousand — and updateLocation is one remove and one add, which matters because it runs a thousand times more often than a ride request. If the nine cells are empty I expand in rings and give up after three. The candidates go through a MatchingStrategy to be ranked, then I offer to number one alone with a fifteen-second deadline; decline or timeout moves to number two. The offer itself is a compare-and-set from AVAILABLE to OFFERED on the driver, and an offered driver leaves the index entirely — so two riders can never be matched to the same car. Fare is a breakdown in integer paise behind a PricingStrategy, which is where surge lives.”

Where this design stops working

At more than one server. An in-process HashMap index and an AtomicReference guard one JVM. With ten dispatchers, both have to move into shared state: the index becomes Redis geo commands or a sharded cell service, and the CAS becomes a conditional write with a version check. The design survives; the mechanism does not.
When density varies wildly. A fixed grid is uniform and cities are not. The airport cell holds four hundred drivers and the outer-ring cell holds none, so one query is slow and the other always expands. That is the point where a quadtree, S2 or H3 earns its complexity — cells that subdivide where the drivers actually are.
When the ranking needs the road network. Straight-line distance is a fine proxy until a river, a flyover or a one-way grid makes the nearest car the slowest one. Ranking by ETA rather than by metres means calling a routing engine for every candidate, which changes the cost model of matching completely.
When matching should be global rather than greedy. Offering each rider their own nearest car is locally optimal and globally mediocre: two riders and two drivers can be assigned crosswise, doubling everybody's wait. Batching requests over a few seconds and solving an assignment problem is what real systems do, and it is a different algorithm entirely.
When a driver must be reachable to be matched. The index says a driver is nearby; it does not say their phone has signal. Real dispatch weights by recent heartbeat and historical acceptance rate, because offering a ride into a tunnel costs fifteen seconds of a rider's patience.

If you only remember one thing

Never look at a driver you do not have to, and never let two riders look at the same one. The grid is the first half — nine cells instead of a city. The compare-and-set plus removing offered drivers from the index is the second half. Everything else in this lesson — the states, the fare, the follow-ups — is what you say while those two ideas are already on the board.

What it gives you

A fixed cell grid turns nearest-driver search from O(all drivers) into a lookup over nine buckets, and it needs nothing more exotic than a hash map — you can write it correctly in ten minutes under interview pressure.
updateLocation is one remove and one add, so an index that is written thousands of times per second stays cheap; a driver who has not left their cell costs a single comparison.
Offering to one driver at a time with a deadline makes double-acceptance structurally impossible rather than merely unlikely, and it means a rejection never has to be sent to a human who already said yes.
The compare-and-set guards exactly one driver instead of the whole dispatcher, so two ride requests in different neighbourhoods never wait on each other.
Matching, pricing and routing are three separate interfaces, so a new ranking signal, a surge rule or a real routing engine is one new class and zero edits to the dispatcher.
Because time is a parameter to requestRide, accept and tick, the fifteen-second timeout and the whole re-offer chain can be tested deterministically with no sleeping and no clock stubbing.

Common mistakes

A uniform grid does not match non-uniform driver density: the airport cell is huge and the suburb cell is empty, so one query does too much work and the other always expands. A quadtree or S2 fixes it and costs an hour you do not have.
Sequential offers add latency — three declines is forty-five seconds of a rider watching a spinner — which is why real systems batch small groups and shorten the deadline once they have acceptance data.
Greedy per-request matching is locally optimal and globally mediocre; batching riders and solving an assignment problem produces shorter total waits but is a different algorithm and a different interview.
Straight-line ranking can pick a car that is two hundred metres away across a river, and the design has no way to notice; correcting it means an ETA call per candidate, which is far more expensive than the index it sits behind.
Everything here is in-process. Ten dispatch servers need the index and the atomic flip to move into a shared store, and at that point the guarantee depends on that store's consistency rather than on your code.
Cell boundaries are arbitrary: two drivers ten metres apart can sit in different cells, so ring 1 can miss a car that a plain radius query would have found. Ring expansion hides it, at the cost of visiting more cells.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

RideSharing.java

import java.util.*;
import java.util.concurrent.atomic.AtomicReference;

/* ------------------------------------------------------------------ basics */
record Location(double lat, double lng) {
    /** Straight-line metres. Good enough to RANK candidates. Never used for a fare. */
    double metresTo(Location o) {
        double dLat = (lat - o.lat()) * 111_320.0;
        double dLng = (lng - o.lng()) * 111_320.0 * Math.cos(Math.toRadians(lat));
        return Math.sqrt(dLat * dLat + dLng * dLng);
    }
}

record Rider(String id, String name) {}
record Vehicle(String plate, String model, int seats) {}

/** Road distance is a DIFFERENT question from straight-line distance. Stub it. */
interface RouteService {
    long roadMetres(Location a, Location b);
    long etaSeconds(Location a, Location b);
}

final class StubRoutes implements RouteService {
    public long roadMetres(Location a, Location b) {
        return Math.round(a.metresTo(b) * 1.35);      // a real system calls a routing engine
    }
    public long etaSeconds(Location a, Location b) {
        return roadMetres(a, b) * 3600 / 22_000;      // assume 22 km/h in city traffic
    }
}

/* ---------------------------------------------------------------- geoindex */
/** A geohash by another name: the map chopped into fixed squares. */
final class GeoIndex {
    static final double CELL_DEG = 0.003;                      // ~330 m

    private final Map<Long, Set<String>> cells = new HashMap<>();   // cell -> driver ids
    private final Map<String, Long> whereIs = new HashMap<>();      // driver id -> cell

    static int row(double lat) { return (int) Math.floor(lat / CELL_DEG); }
    static int col(double lng) { return (int) Math.floor(lng / CELL_DEG); }
    static long cellId(int r, int c) { return ((long) r << 32) | (c & 0xffffffffL); }
    static String name(Location at) { return "cell(" + row(at.lat()) + "," + col(at.lng()) + ")"; }

    /** Remove from the old cell, add to the new one. Both O(1). Called constantly. */
    void put(String driverId, Location at) {
        long cell = cellId(row(at.lat()), col(at.lng()));
        Long old = whereIs.get(driverId);
        if (old != null && old == cell) return;                // did not leave the cell: nothing to do
        remove(driverId);
        cells.computeIfAbsent(cell, k -> new HashSet<>()).add(driverId);
        whereIs.put(driverId, cell);
    }

    void remove(String driverId) {
        Long old = whereIs.remove(driverId);
        if (old == null) return;
        Set<String> set = cells.get(old);
        if (set != null && set.remove(driverId) && set.isEmpty()) cells.remove(old);
    }

    boolean holds(String driverId) { return whereIs.containsKey(driverId); }

    /** Everyone in the (2*ring+1) x (2*ring+1) square of cells around "at". */
    Set<String> near(Location at, int ring) {
        int r0 = row(at.lat()), c0 = col(at.lng());
        Set<String> out = new LinkedHashSet<>();
        for (int r = r0 - ring; r <= r0 + ring; r++)
            for (int c = c0 - ring; c <= c0 + ring; c++) {
                Set<String> s = cells.get(cellId(r, c));
                if (s != null) out.addAll(s);
            }
        return out;
    }
}

/* ------------------------------------------------------------------ driver */
enum DriverState { OFFLINE, AVAILABLE, OFFERED, ON_TRIP }

/** state + rideId + deadline swapped TOGETHER, so they can never disagree. */
record Slot(DriverState state, String rideId, long expiresAt) {}

final class Driver {
    final String id, name;
    final double rating;
    final Vehicle vehicle;
    volatile Location at;
    private final AtomicReference<Slot> slot =
        new AtomicReference<>(new Slot(DriverState.OFFLINE, null, 0L));

    Driver(String id, String name, double rating, Vehicle vehicle) {
        this.id = id; this.name = name; this.rating = rating; this.vehicle = vehicle;
    }

    DriverState state() { return slot.get().state(); }

    boolean goOnline() {
        Slot cur = slot.get();
        return cur.state() == DriverState.OFFLINE
            && slot.compareAndSet(cur, new Slot(DriverState.AVAILABLE, null, 0L));
    }

    /** THE method. Exactly one concurrent caller can win this. */
    boolean tryOffer(String rideId, long expiresAt) {
        Slot cur = slot.get();
        if (cur.state() != DriverState.AVAILABLE) return false;
        return slot.compareAndSet(cur, new Slot(DriverState.OFFERED, rideId, expiresAt));
    }

    boolean confirm(String rideId) {
        Slot cur = slot.get();
        if (cur.state() != DriverState.OFFERED || !rideId.equals(cur.rideId())) return false;
        return slot.compareAndSet(cur, new Slot(DriverState.ON_TRIP, rideId, 0L));
    }

    /** Declined, expired, cancelled or completed — back into the pool. */
    boolean release(String rideId) {
        Slot cur = slot.get();
        if (cur.state() == DriverState.OFFLINE || cur.state() == DriverState.AVAILABLE) return false;
        if (!rideId.equals(cur.rideId())) return false;
        return slot.compareAndSet(cur, new Slot(DriverState.AVAILABLE, null, 0L));
    }
}

/* ------------------------------------------------------------- strategies */
interface MatchingStrategy { List<Driver> rank(Location pickup, List<Driver> pool); }

final class NearestFirst implements MatchingStrategy {
    public List<Driver> rank(Location pickup, List<Driver> pool) {
        List<Driver> out = new ArrayList<>(pool);
        out.sort(Comparator.comparingDouble(d -> d.at.metresTo(pickup)));
        return out;
    }
}

/** Same interface, a new signal, and DispatchService does not change one line. */
final class NearestThenRating implements MatchingStrategy {
    public List<Driver> rank(Location pickup, List<Driver> pool) {
        List<Driver> out = new ArrayList<>(pool);
        out.sort(Comparator.comparingDouble(d -> d.at.metresTo(pickup) * (1 + (5.0 - d.rating) * 0.10)));
        return out;
    }
}

record Fare(long basePaise, long distancePaise, long timePaise, long surgePaise, long totalPaise) {
    String pretty() { return "Rs." + (totalPaise / 100) + "." + String.format("%02d", totalPaise % 100); }
}

interface PricingStrategy { Fare quote(long metres, long seconds); }

/** surgeBps is basis points: 10000 = x1.0, 18000 = x1.8. Integers all the way down. */
final class StandardPricing implements PricingStrategy {
    private final long basePaise, perKmPaise, perMinPaise, surgeBps;
    StandardPricing(long basePaise, long perKmPaise, long perMinPaise, long surgeBps) {
        this.basePaise = basePaise; this.perKmPaise = perKmPaise;
        this.perMinPaise = perMinPaise; this.surgeBps = surgeBps;
    }
    public Fare quote(long metres, long seconds) {
        long distance = metres * perKmPaise / 1000;       // multiply FIRST, then divide
        long time = seconds * perMinPaise / 60;
        long subtotal = basePaise + distance + time;
        long surged = subtotal * surgeBps / 10000;
        long rounded = (surged + 50) / 100 * 100;         // nearest whole rupee, deterministic
        return new Fare(basePaise, distance, time, rounded - subtotal, rounded);
    }
}

/* -------------------------------------------------------------------- ride */
enum RideState {
    REQUESTED, MATCHED, DRIVER_ARRIVED, IN_PROGRESS, COMPLETED,
    CANCELLED_BY_RIDER, CANCELLED_BY_DRIVER, NO_DRIVERS_FOUND
}

final class Ride {
    private static final Map<RideState, Set<RideState>> LEGAL = Map.of(
        RideState.REQUESTED, Set.of(RideState.MATCHED, RideState.NO_DRIVERS_FOUND,
                                    RideState.CANCELLED_BY_RIDER),
        RideState.MATCHED, Set.of(RideState.DRIVER_ARRIVED, RideState.CANCELLED_BY_RIDER,
                                  RideState.CANCELLED_BY_DRIVER),
        RideState.DRIVER_ARRIVED, Set.of(RideState.IN_PROGRESS, RideState.CANCELLED_BY_RIDER,
                                         RideState.CANCELLED_BY_DRIVER),
        RideState.IN_PROGRESS, Set.of(RideState.COMPLETED)
    );

    final String id;
    final Rider rider;
    final Location pickup, drop;
    RideState state = RideState.REQUESTED;
    Driver driver;
    String offeredTo;
    long offerExpiresAt, startedAt;
    Fare quotedFare, finalFare;
    final Deque<String> candidates = new ArrayDeque<>();
    final Set<String> tried = new HashSet<>();

    Ride(String id, Rider rider, Location pickup, Location drop) {
        this.id = id; this.rider = rider; this.pickup = pickup; this.drop = drop;
    }

    /** One table, one method. An illegal move is an exception, not a silent bug. */
    void transitionTo(RideState next) {
        if (!LEGAL.getOrDefault(state, Set.of()).contains(next))
            throw new IllegalStateException(id + ": " + state + " -> " + next + " is not legal");
        state = next;
    }
}

/* -------------------------------------------------------------- dispatcher */
final class DispatchService {
    static final long OFFER_TTL_MS = 15_000;
    static final int MAX_RING = 3;

    private final Map<String, Driver> drivers = new LinkedHashMap<>();
    private final Map<String, Ride> rides = new LinkedHashMap<>();
    private final GeoIndex index = new GeoIndex();
    private final MatchingStrategy matcher;
    private final PricingStrategy pricing;
    private final RouteService routes;
    private int rideSeq;
    int lastChecked, lastRing;                     // just so the demo can print them

    DispatchService(MatchingStrategy m, PricingStrategy p, RouteService r) {
        this.matcher = m; this.pricing = p; this.routes = r;
    }

    void register(Driver d, Location at) { drivers.put(d.id, d); d.at = at; }

    void goOnline(String driverId, Location at) {
        Driver d = drivers.get(driverId);
        d.at = at;
        if (d.goOnline()) index.put(driverId, at);
    }

    /** Runs a thousand times more often than requestRide. Must stay O(1). */
    void updateLocation(String driverId, Location at) {
        Driver d = drivers.get(driverId);
        d.at = at;
        if (d.state() == DriverState.AVAILABLE) index.put(driverId, at);   // only matchable drivers are indexed
    }

    private List<Driver> availableNear(Ride ride, int ring) {
        List<Driver> pool = new ArrayList<>();
        for (String id : index.near(ride.pickup, ring)) {
            lastChecked++;                                        // this is the number the round is about
            Driver d = drivers.get(id);
            if (d != null && d.state() == DriverState.AVAILABLE && !ride.tried.contains(id)) pool.add(d);
        }
        return pool;
    }

    Ride requestRide(Rider rider, Location pickup, Location drop, long now) {
        Ride ride = new Ride("r" + (++rideSeq), rider, pickup, drop);
        rides.put(ride.id, ride);
        lastChecked = 0;
        if (!expandAndOffer(ride, 1, now)) ride.transitionTo(RideState.NO_DRIVERS_FOUND);
        return ride;
    }

    /** Ring by ring outward. Stop at the first ring that produces an accepted offer. */
    private boolean expandAndOffer(Ride ride, int fromRing, long now) {
        for (int ring = fromRing; ring <= MAX_RING; ring++) {
            lastRing = ring;
            List<Driver> pool = availableNear(ride, ring);
            if (pool.isEmpty()) continue;
            for (Driver d : matcher.rank(ride.pickup, pool)) ride.candidates.addLast(d.id);
            if (offerNext(ride, now)) return true;
        }
        return false;
    }

    /** Offer to ONE driver, with a deadline. Never a broadcast. */
    private boolean offerNext(Ride ride, long now) {
        while (!ride.candidates.isEmpty()) {
            String id = ride.candidates.pollFirst();
            ride.tried.add(id);
            Driver d = drivers.get(id);
            if (d == null) continue;
            if (!d.tryOffer(ride.id, now + OFFER_TTL_MS)) continue;   // CAS lost — somebody beat us here
            index.remove(id);                                         // offered => not a candidate for anyone
            ride.offeredTo = id;
            ride.offerExpiresAt = now + OFFER_TTL_MS;
            return true;
        }
        return false;
    }

    private void withdraw(Ride ride) {
        Driver d = drivers.get(ride.offeredTo);
        if (d != null && d.release(ride.id)) index.put(d.id, d.at);    // straight back into the pool
        ride.offeredTo = null;
    }

    boolean accept(String rideId, String driverId, long now) {
        Ride ride = rides.get(rideId);
        if (ride == null || ride.state != RideState.REQUESTED) return false;
        if (!driverId.equals(ride.offeredTo) || now > ride.offerExpiresAt) return false;
        Driver d = drivers.get(driverId);
        if (!d.confirm(rideId)) return false;
        ride.driver = d;
        ride.offeredTo = null;
        ride.quotedFare = pricing.quote(routes.roadMetres(ride.pickup, ride.drop),
                                        routes.etaSeconds(ride.pickup, ride.drop));
        ride.transitionTo(RideState.MATCHED);
        return true;
    }

    boolean decline(String rideId, String driverId, long now) {
        Ride ride = rides.get(rideId);
        if (ride == null || !driverId.equals(ride.offeredTo)) return false;
        withdraw(ride);
        if (!offerNext(ride, now) && !expandAndOffer(ride, 2, now))
            ride.transitionTo(RideState.NO_DRIVERS_FOUND);
        return true;
    }

    /** Time is a PARAMETER. That is the only reason the 15-second rule is testable. */
    void tick(long now) {
        for (Ride ride : rides.values()) {
            if (ride.state != RideState.REQUESTED || ride.offeredTo == null) continue;
            if (now <= ride.offerExpiresAt) continue;
            withdraw(ride);
            if (!offerNext(ride, now) && !expandAndOffer(ride, 2, now))
                ride.transitionTo(RideState.NO_DRIVERS_FOUND);
        }
    }

    void driverArrived(String rideId) { rides.get(rideId).transitionTo(RideState.DRIVER_ARRIVED); }

    void startTrip(String rideId, long now) {
        Ride ride = rides.get(rideId);
        ride.startedAt = now;
        ride.transitionTo(RideState.IN_PROGRESS);
    }

    Fare complete(String rideId, long actualMetres, long now) {
        Ride ride = rides.get(rideId);
        ride.finalFare = pricing.quote(actualMetres, (now - ride.startedAt) / 1000);
        ride.transitionTo(RideState.COMPLETED);
        endRide(ride);
        return ride.finalFare;
    }

    void cancelByRider(String rideId, long now) {
        Ride ride = rides.get(rideId);
        if (ride.offeredTo != null) withdraw(ride);
        ride.transitionTo(RideState.CANCELLED_BY_RIDER);
        endRide(ride);
    }

    /** EVERY terminal path goes through here, or you leak a car. */
    private void endRide(Ride ride) {
        Driver d = ride.driver;
        if (d != null && d.release(ride.id)) index.put(d.id, d.at);
    }

    Ride ride(String id) { return rides.get(id); }
    String cellOf(String driverId) { return GeoIndex.name(drivers.get(driverId).at); }
}

/* -------------------------------------------------------------------- demo */
public class Main {
    public static void main(String[] args) {
        DispatchService svc = new DispatchService(
            new NearestThenRating(),
            new StandardPricing(5000, 1200, 150, 18000),   // base Rs.50, Rs.12/km, Rs.1.50/min, x1.8
            new StubRoutes());

        Driver d1 = new Driver("d1", "Rahul", 4.9, new Vehicle("KA01AB1234", "Swift", 4));
        Driver d3 = new Driver("d3", "Meena", 4.6, new Vehicle("KA05CD5678", "Baleno", 4));
        Driver d7 = new Driver("d7", "Iqbal", 4.8, new Vehicle("KA03EF9012", "i20", 4));
        Driver d9 = new Driver("d9", "Farida", 4.7, new Vehicle("KA09GH3456", "Dzire", 4));

        svc.register(d1, new Location(12.9710, 77.5940));
        svc.register(d3, new Location(12.9702, 77.5952));
        svc.register(d7, new Location(12.9688, 77.5961));
        svc.register(d9, new Location(12.9500, 77.6300));          // far side of town
        svc.goOnline("d1", d1.at); svc.goOnline("d3", d3.at);
        svc.goOnline("d7", d7.at); svc.goOnline("d9", d9.at);

        Location pickup = new Location(12.9705, 77.5948);
        Location drop = new Location(12.9950, 77.6400);
        Rider anita = new Rider("u1", "Anita"), bala = new Rider("u2", "Bala");

        System.out.println("-- Anita taps Book at t=0 --");
        Ride r1 = svc.requestRide(anita, pickup, drop, 0);
        System.out.println("   ring " + svc.lastRing + ", checked " + svc.lastChecked
                + " drivers (not " + 50_000 + ") -> offered to " + r1.offeredTo
                + ", expires t=" + r1.offerExpiresAt);

        System.out.println("-- Bala taps Book at the SAME instant --");
        Ride r2 = svc.requestRide(bala, pickup, drop, 0);
        System.out.println("   d3 is OFFERED, so it is not in the index at all -> offered to "
                + r2.offeredTo);

        System.out.println("-- nobody answers Anita's offer --");
        svc.tick(15_001);
        System.out.println("   d3 expired and is back in the index; d1 is taken, so the CAS lost");
        System.out.println("   Anita's offer moved to " + r1.offeredTo);

        System.out.println("-- both drivers accept --");
        System.out.println("   Bala + d1: " + svc.accept(r2.id, "d1", 4_200));
        System.out.println("   Anita + d7: " + svc.accept(r1.id, "d7", 16_400));
        System.out.println("   quoted (surge x1.8): " + r1.quotedFare.pretty()
                + "  = " + r1.quotedFare.basePaise() + " + " + r1.quotedFare.distancePaise()
                + " + " + r1.quotedFare.timePaise() + " + " + r1.quotedFare.surgePaise() + " paise");

        System.out.println("-- the trip --");
        svc.driverArrived(r1.id);
        svc.startTrip(r1.id, 40_000);
        Fare fin = svc.complete(r1.id, 8_200, 1_380_000);
        System.out.println("   state=" + r1.state + "  final=" + fin.pretty()
                + "  d7 is " + d7.state() + " again");

        System.out.println("-- d7 drives east across a cell boundary --");
        System.out.println("   before: " + svc.cellOf("d7"));
        svc.updateLocation("d7", new Location(12.9688, 77.5995));
        System.out.println("   after:  " + svc.cellOf("d7") + "   (one remove, one add)");

        System.out.println("-- a rider in an empty part of town --");
        Ride r3 = svc.requestRide(anita, new Location(12.8000, 77.4000), drop, 2_000_000);
        System.out.println("   rings tried: " + DispatchService.MAX_RING
                + ", checked " + svc.lastChecked + " -> " + r3.state);
    }
}

/* ---------------------------------------------------------------- output ---
-- Anita taps Book at t=0 --
   ring 1, checked 3 drivers (not 50000) -> offered to d3, expires t=15000
-- Bala taps Book at the SAME instant --
   d3 is OFFERED, so it is not in the index at all -> offered to d1
-- nobody answers Anita's offer --
   d3 expired and is back in the index; d1 is taken, so the CAS lost
   Anita's offer moved to d7
-- both drivers accept --
   Bala + d1: true
   Anita + d7: true
   quoted (surge x1.8): Rs.309.00  = 5000 + 9088 + 3097 + 13715 paise
-- the trip --
   state=COMPLETED  final=Rs.327.00  d7 is AVAILABLE again
-- d7 drives east across a cell boundary --
   before: cell(4322,25865)
   after:  cell(4322,25866)   (one remove, one add)
-- a rider in an empty part of town --
   rings tried: 3, checked 0 -> NO_DRIVERS_FOUND
--------------------------------------------------------------------------- */

References & further reading

8 sources

Articleuber.com
Uber Engineering — H3, a hexagonal hierarchical spatial index
Uber's own writeup of the index that replaced the naive grid. Read it for why hexagons and multiple resolutions matter once density varies — it is the upgrade path you should be able to name in the round.
Docss2geometry.io
S2 Geometry — the cell hierarchy behind many geo systems
The other standard answer. The key idea to take away is a space-filling curve that turns a 2-D cell into a single sortable integer, which is exactly what your cellId(r, c) is doing by hand.
Docsredis.io
Redis — geospatial commands (GEOADD, GEOSEARCH)
What your in-memory GeoIndex becomes at ten servers. Worth skimming so you can say what moves and what stays when the index leaves the process.
Docsdocs.oracle.com
java.util.concurrent.atomic — package documentation
AtomicReference and compareAndSet, from the source. The package summary is short and it is the difference between “I used an atomic” and “I know what it guarantees”.
Articlegithub.com
awesome-low-level-design — ride sharing problem
The canonical write-up of this exact interview problem. Useful as a checklist of the entities most interviewers have in their head before you walk in.
Articleuber.com
Uber Engineering — how surge pricing actually works
The product side of your PricingStrategy: what the multiplier is trying to do to supply and demand, and why it is a separate concern from matching.
Book
Designing Data-Intensive Applications — Martin Kleppmann
Chapters on partitioning and on linearizability. Your cell key is a partition key, and your compare-and-set is the single-object atomic operation the book builds distributed guarantees from — reading it makes the multi-server follow-up easy.
Articlerefactoring.guru
Refactoring Guru — Strategy pattern
The pattern behind both MatchingStrategy and PricingStrategy, with the standard diagrams. Short, and it gives you the vocabulary to justify the two seams in one sentence.

Knowledge check

Did it land?

Quick questions, answers revealed on submit. Sign in to save your best score.

question 01 / 08

Fifty thousand drivers are online. A ride request arrives. Why is `for (Driver d : allDrivers) if (distance(d, pickup) < 3000)` the answer that loses this round?

question 02 / 08

You bucket the map into cells and keep `Map<CellId, Set<Driver>>`. A driver's location ping arrives. What has to happen, and why does that shape the whole index?

question 03 / 08

Your interviewer asks how you chose a cell size of roughly 300 metres. What is the real trade-off?

question 04 / 08

You have sixteen ranked nearby drivers. Why not push the ride to all of them and let the first to tap Accept win?

question 05 / 08

Two ride requests are processed at the same instant and both rank driver d3 first. What actually prevents both riders from being matched to d3?

question 06 / 08

Which single rule removes most of the concurrency pressure from the matcher in the first place?

question 07 / 08

Driver #1 was offered the ride at t=0 with a fifteen-second deadline and never answered. What has to happen at t=15001, and what makes it testable?

question 08 / 08

The trip is 6.4 km. Your fare code computes `metres / 1000 * perKmPaise` with integer arithmetic. What is wrong?

0/8 answered