These are the notes for Low-Level Design (LLD) episode 81: designing a ride-sharing app, the kind of app where you tap a button and a bike, an auto or a car comes to pick you up. We cover the ride-sharing requirements, the main classes (Rider, Driver, Vehicle, Location, Trip), nearest driver search, a swappable driver matching strategy, a trip state machine, a fare calculation strategy per vehicle type, surge pricing, ratings, and concurrent driver acceptance: three drivers tapping "Accept" on one trip at the same moment.
How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. In the two thread programs, which driver wins changes from run to run; the notes say so where it matters, and describe only what stayed the same in every run (we ran each one 20 times). Riders, drivers, number plates, fares and all other numbers are made up. Nothing here describes how any real company (Uber, Ola, Rapido or any other) builds its app or sets its prices.
1. The problem: the auto stand at the railway station
A train arrives at 11 pm and 200 people walk out together. Outside, a stand manager shouts for the nearest free auto. Sometimes three autos rush to one family, and the manager decides who takes them. The meter decides the fare, and when the crowd is big and autos are few, everyone pays a bit more. A ride-sharing app is that stand, for a whole city, on a phone.
| Real life | In the design |
|---|---|
| People walking out of the station wanting a ride | Riders making ride requests |
| Auto drivers waiting at the stand, free or already on a ride | Drivers (free or busy) with Vehicles |
| "Nearest free auto, come!" | Nearest driver search, a driver matching strategy |
| Three autos rush one family; only one takes them | Concurrent driver acceptance: exactly one winner |
| Waiting, on the way, dropped home | The trip state machine |
| The meter: a base fare plus per kilometre | The fare calculation strategy |
| Paying a bit more at a huge rush | Surge pricing |
| "Good driver, five stars" | Ratings |
2. Requirements and the main classes
Ride-sharing requirements are the list of things the app must do. Ours, kept small enough for a machine-coding round:
- A rider requests a ride from a pickup point to a drop point, choosing a vehicle type.
- The app finds suitable free drivers nearby (the matching step).
- The trip is offered to a few drivers; the first to accept gets it, and only that driver.
- The trip moves through fixed states: requested, accepted, started, completed (or cancelled).
- The fare depends on vehicle type, distance and time, multiplied by surge when demand is high.
- After the trip, the rider rates the driver from 1 to 5 stars.
The classes (nouns in the requirements become classes):
- Rider: the person who wants a ride. Example: Asha at the railway station.
- Driver: the person who drives; has a vehicle, a current location, a rating, and is either free or busy. Example: Imran, free, 1 km away.
- Vehicle: what the driver drives: a type (BIKE, AUTO or CAR) and a number plate. Example:
new Vehicle("AUTO", "MH12-2002"). - Location: a point on the map. To keep numbers easy we use
xandyin kilometres on a simple city grid, with the station at (0, 0). A real app uses latitude and longitude. - Trip: one ride: the rider, the driver, the pickup and the drop, plus its state and fare.
3. Attempt 1: take the first free driver
import java.util.*;
record Location(double x, double y) { // km on a simple city grid
double distanceTo(Location o) { return Math.hypot(x - o.x, y - o.y); } }
record Vehicle(String type, String number) {} // BIKE, AUTO or CAR
record Rider(String name, Location at) {}
class Driver {
final String name; final Vehicle vehicle; Location at; boolean free = true;
Driver(String n, Vehicle v, Location l) { name = n; vehicle = v; at = l; } }
record Trip(Rider rider, Driver driver, Location pickup, Location drop) {}
public class Main { public static void main(String[] args) {
List<Driver> drivers = List.of(
new Driver("Ramesh", new Vehicle("AUTO", "MH12-1001"), new Location(6, 8)),
new Driver("Imran", new Vehicle("AUTO", "MH12-2002"), new Location(0, 1)),
new Driver("Sunita", new Vehicle("CAR", "MH12-3003"), new Location(3, 4)));
Rider asha = new Rider("Asha", new Location(0, 0)); // at the railway station
Driver d = drivers.stream().filter(x -> x.free).findFirst().get(); // first free
Trip t = new Trip(asha, d, asha.at(), new Location(4, 3));
System.out.println("Trip: " + asha.name() + " with " + t.driver().name);
for (Driver x : drivers)
System.out.println(" " + x.name + " is free, " + x.at.distanceTo(asha.at()) + " km");
} }
Real output:
Trip: Asha with Ramesh
Ramesh is free, 10.0 km
Imran is free, 1.0 km
Sunita is free, 5.0 km
Why it failed
Asha gets Ramesh, 10 km away, while Imran is free and only 1 km away. "First in the list" just means "whoever logged in first". It says nothing about distance.
The distance: Math.hypot(dx, dy) is the straight-line distance, the square root of dx² + dy². From (0, 0) to (6, 8) is √(36 + 64) = 10. Roads are not straight lines, so a real app would use a road distance or an estimated time, but straight-line distance is a fine first filter.
4. Nearest driver search and the driver matching strategy
- Nearest driver search: keep only free drivers, and pick the one with the smallest distance to the rider.
- A plain search checks every driver one by one (a linear scan). That is fine for 3 drivers and slow for 50,000 in a big city at rush hour: every request would compute 50,000 distances. The fix (section 9 and the mini project) is to cut the city into grid cells and look only in nearby cells.
- Rating: the stars, 1 to 5, that riders give a driver after a trip. A driver's rating is the average of all of them.
- Driver matching strategy: the rule that decides which driver gets a request. Rules change ("nearest" today, "best-rated for premium rides" tomorrow), so we put each rule in its own class behind one interface: the Strategy pattern (episode 34). New rule = new class; nothing else is edited.
import java.util.*;
record Location(double x, double y) {
double distanceTo(Location o) { return Math.hypot(x - o.x, y - o.y); } }
record Rider(String name, Location at) {}
record Driver(String name, Location at, double rating, boolean free) {
Driver(String n, int x, int y, double r, boolean f) { this(n, new Location(x, y), r, f); } }
interface DriverMatchingStrategy { Optional<Driver> match(Rider r, List<Driver> ds); }
class NearestDriver implements DriverMatchingStrategy { // nearest FREE driver
public Optional<Driver> match(Rider r, List<Driver> ds) {
return ds.stream().filter(Driver::free)
.min(Comparator.comparingDouble(d -> d.at().distanceTo(r.at()))); } }
class BestRatedDriver implements DriverMatchingStrategy { // best rated, within 5 km
public Optional<Driver> match(Rider r, List<Driver> ds) {
return ds.stream().filter(d -> d.free() && d.at().distanceTo(r.at()) <= 5)
.max(Comparator.comparingDouble(Driver::rating)); } }
public class Main { public static void main(String[] args) {
List<Driver> ds = List.of(new Driver("Ramesh", 6, 8, 4.2, true),
new Driver("Imran", 0, 1, 4.0, true), new Driver("Sunita", 3, 4, 4.9, true),
new Driver("Vikram", 1, 0, 4.5, false)); // Vikram is busy
Rider asha = new Rider("Asha", new Location(0, 0));
Rider neha = new Rider("Neha", new Location(20, 20)); // far outside the city
for (DriverMatchingStrategy s : List.of(new NearestDriver(), new BestRatedDriver()))
for (Rider r : List.of(asha, neha)) System.out.println(s.getClass().getName() + ", "
+ r.name() + " -> " + s.match(r, ds).map(Driver::name).orElse("no driver")); } }
Real output:
NearestDriver, Asha -> Imran
NearestDriver, Neha -> Ramesh
BestRatedDriver, Asha -> Sunita
BestRatedDriver, Neha -> no driver
NearestDrivergives Asha Imran (1 km). It skips Vikram (also 1 km, but busy on a trip).BestRatedDrivergives Asha Sunita (4.9 stars, 5 km away, within its 5 km limit).- For Neha, far outside the city,
NearestDriverstill sends Ramesh from about 18 km away, whileBestRatedDriversays no driver because nobody is within 5 km.Optionalmakes "no driver" an honest answer instead of anull. s.getClass().getName()prints the class name, so we can see which strategy answered.- Both strategies run on the same data; the code that calls them does not change. That is what "swappable" means.
5. Attempt 2: three drivers accept one trip
The app offers a trip to three nearby drivers at once (drivers don't always say yes), and the first tap on "Accept" should win. Our first attempt keeps the status as a String and checks it, then sets it.
import java.util.*; import java.util.concurrent.*;
class Trip { // attempt: status is just a String
String status = "REQUESTED", driver;
final List<String> acceptedBy = new CopyOnWriteArrayList<>();
boolean accept(String d) throws InterruptedException {
if (!status.equals("REQUESTED")) return false; // 1. check
Thread.sleep(20); // ...network, database...
status = "ACCEPTED"; driver = d; acceptedBy.add(d); // 2. act
return true; } }
public class Main { public static void main(String[] args) throws Exception {
Trip trip = new Trip();
ExecutorService pool = Executors.newFixedThreadPool(3); // 3 drivers tap "Accept"
CountDownLatch go = new CountDownLatch(1);
for (String d : List.of("Imran", "Ramesh", "Sunita"))
pool.submit(() -> { go.await(); return trip.accept(d); });
go.countDown(); pool.shutdown(); pool.awaitTermination(5, TimeUnit.SECONDS);
System.out.println("accepted by " + trip.acceptedBy + ", trip says: " + trip.driver);
Trip t2 = new Trip(); t2.status = "COMPLETED"; // never accepted, never started
System.out.println("T2: " + t2.status + " -> charge the rider");
} }
Real output of one run:
accepted by [Imran, Sunita, Ramesh], trip says: Ramesh
T2: COMPLETED -> charge the rider
In all 20 runs, all three drivers were accepted. The order in the list and the driver the trip finally "says" changed from run to run (it is whoever wrote last). Other runs printed, for example, accepted by [Ramesh, Imran, Sunita], trip says: Sunita and accepted by [Sunita, Ramesh, Imran], trip says: Imran.
Why it failed
- Check-then-act: all three threads checked
status.equals("REQUESTED")before any of them set"ACCEPTED". TheThread.sleep(20)stands for the time spent on the network and the database; it makes the gap wide enough that the race happens every time. This is a race condition: the result depends on which thread runs when. - A
Stringstatus has no rules:t2.status = "COMPLETED"on a trip that was never accepted or started went through, and the rider would be charged for a ride that never happened.
The words, from episodes 46 and 75: a thread is one line of work running inside a program; a thread pool (ExecutorService) is a team of ready threads; a CountDownLatch is a starting gun: threads await(), and one countDown() releases them all together.
6. The fix: a trip state machine and compareAndSet
-
Trip state machine: the trip's states are an
enum, and each state lists the moves it allows:- REQUESTED → ACCEPTED or CANCELLED
- ACCEPTED → STARTED or CANCELLED
- STARTED → COMPLETED
- COMPLETED and CANCELLED are the end: no moves out.
Anything else throws an
IllegalStateException. This is the State idea from episode 37, written as an enum with aswitch. - Concurrent driver acceptance: the state lives in anAtomicReference<TripState>.compareAndSet(REQUESTED, ACCEPTED)says "change it to ACCEPTED, but only if it is still REQUESTED", as one atomic step (atomic = it cannot be split; no other thread can act in the middle). Exactly one thread seestrue; the others seefalse.
import java.util.*; import java.util.concurrent.*; import java.util.concurrent.atomic.*;
enum TripState { REQUESTED, ACCEPTED, STARTED, COMPLETED, CANCELLED; // the trip state machine
boolean canGo(TripState to) { return switch (this) {
case REQUESTED -> to == ACCEPTED || to == CANCELLED;
case ACCEPTED -> to == STARTED || to == CANCELLED;
case STARTED -> to == COMPLETED; default -> false; }; } } // COMPLETED, CANCELLED: end
class Trip { volatile String driver;
final AtomicReference<TripState> state = new AtomicReference<>(TripState.REQUESTED);
boolean accept(String d) { // only ONE tap can win
if (!state.compareAndSet(TripState.REQUESTED, TripState.ACCEPTED)) return false;
driver = d; return true; }
void move(TripState to) {
TripState now = state.get();
if (!now.canGo(to) || !state.compareAndSet(now, to))
throw new IllegalStateException("trip is " + state.get() + ", cannot go " + to); } }
public class Main { public static void main(String[] args) throws Exception {
Trip trip = new Trip(); ExecutorService pool = Executors.newFixedThreadPool(3);
CountDownLatch go = new CountDownLatch(1); List<Future<Boolean>> taps = new ArrayList<>();
for (String d : List.of("Imran", "Ramesh", "Sunita"))
taps.add(pool.submit(() -> { go.await(); Thread.sleep(20); return trip.accept(d); }));
go.countDown(); int wins = 0; for (Future<Boolean> f : taps) if (f.get()) wins++;
pool.shutdown(); System.out.println("winners: " + wins + ", driver: " + trip.driver);
trip.move(TripState.STARTED); trip.move(TripState.COMPLETED);
System.out.println("state: " + trip.state.get()); trip.move(TripState.CANCELLED); } }
Real output (the driver's name changes from run to run; the rest never did in 20 runs):
winners: 1, driver: Imran
state: COMPLETED
Exception in thread "main" java.lang.IllegalStateException: trip is COMPLETED, cannot go CANCELLED
at Trip.move(Main.java:15)
at Main.main(Main.java:24)
- winners: 1 in every run. Which driver wins is decided by timing, but it is always exactly one, and only that driver is on the trip.
- The trip goes REQUESTED → ACCEPTED → STARTED → COMPLETED.
- Cancelling a completed trip throws
IllegalStateException: trip is COMPLETED, cannot go CANCELLED. move()also usescompareAndSet(now, to), so two threads can't both move the trip from the same state (for example, the rider cancelling while the driver starts the ride: one wins, the other gets the exception).synchronizedonacceptwould also work (only one thread inside at a time).compareAndSetneeds no lock, and it's the same idea a database uses with a conditional update.- A small detail:
driveris set just after the state changes. In this program nobody reads the driver in between; in a bigger system, keep the driver and the state in one object, or set the driver with its owncompareAndSet(null, d)first.
7. Fares, surge pricing and ratings
- Fare calculation strategy: the rule that turns a trip into a price. A
FareStrategyinterface with one method,fare(km, minutes), and one rule per vehicle type. Ours: base + per km × km + per minute × minutes. For an auto: 25 + 12 × 5 + 1 × 15 = Rs 100. Any other rule (a flat airport fare, a night fare) is another class implementingFareStrategy. - Surge pricing: when many people want rides and few drivers are free, the fare is multiplied. Our multiplier is the demand/supply ratio, requests ÷ free drivers, never below 1 and capped at 2. 15 requests, 10 drivers → × 1.5. 40 requests, 10 drivers → 4, capped to × 2. The cap stops a rider paying four times on a rainy night; the ratio pulls more drivers onto the road.
- Ratings: only 1 to 5 is allowed (anything else is a bug or an attack, so it throws). The driver's rating is the average: total stars ÷ number of ratings.
import java.util.*;
interface FareStrategy { double fare(double km, int minutes); }
record PerKmFare(int base, int perKm, int perMin) implements FareStrategy { // per vehicle
public double fare(double km, int min) { return base + perKm * km + perMin * min; } }
class Surge { // demand / supply: never below 1, capped at 2
static double multiplier(int requests, int freeDrivers) {
return Math.min(2.0, Math.max(1.0, (double) requests / Math.max(1, freeDrivers))); } }
class Driver {
private int stars, trips;
void rate(int s) {
if (s < 1 || s > 5) throw new IllegalArgumentException("rating must be 1 to 5, got " + s);
stars += s; trips++; }
double rating() { return trips == 0 ? 0 : (double) stars / trips; } }
public class Main { public static void main(String[] args) {
Map<String, FareStrategy> fares = new LinkedHashMap<>();
fares.put("BIKE", new PerKmFare(15, 6, 1)); fares.put("AUTO", new PerKmFare(25, 12, 1));
fares.put("CAR", new PerKmFare(45, 15, 2));
fares.forEach((t, f) -> System.out.printf("%s 5 km 15 min: Rs %.0f%n", t, f.fare(5, 15)));
for (int requests : new int[] {15, 40}) { // 10 free drivers nearby
double m = Surge.multiplier(requests, 10);
System.out.printf("%d requests, 10 drivers: x%.1f, AUTO Rs %.0f%n", requests, m,
m * fares.get("AUTO").fare(5, 15)); }
Driver imran = new Driver(); imran.rate(5); imran.rate(4); imran.rate(4);
System.out.printf("Imran: %.1f stars%n", imran.rating()); imran.rate(6); } }
Real output:
BIKE 5 km 15 min: Rs 60
AUTO 5 km 15 min: Rs 100
CAR 5 km 15 min: Rs 150
15 requests, 10 drivers: x1.5, AUTO Rs 150
40 requests, 10 drivers: x2.0, AUTO Rs 200
Imran: 4.3 stars
Exception in thread "main" java.lang.IllegalArgumentException: rating must be 1 to 5, got 6
at Driver.rate(Main.java:11)
at Main.main(Main.java:24)
- Bike Rs 60 (15 + 30 + 15), auto Rs 100 (25 + 60 + 15), car Rs 150 (45 + 75 + 30).
- 15 requests for 10 drivers: × 1.5, so the auto costs Rs 150.
- 40 requests for 10 drivers would be × 4.0; the cap holds it at × 2.0: Rs 200.
- Imran's stars 5, 4, 4 average to 13 ÷ 3 = 4.33, printed as 4.3.
rate(6)throwsIllegalArgumentException: rating must be 1 to 5, got 6.LinkedHashMapkeeps the order we put things in, so the output is always BIKE, AUTO, CAR.
8. The class diagram
Rider(name, at) ─ requests ─▶ Trip(rider, pickup, drop) ◀─ accepts ─ Driver(name, Vehicle, at)
Location(x, y) in km · distanceTo() = straight line · Vehicle(type BIKE/AUTO/CAR, number)
DriverMatchingStrategy ◁─ NearestDriver (free, nearest) · BestRatedDriver (within 5 km, top rating)
TripState: REQUESTED ─▶ ACCEPTED ─▶ STARTED ─▶ COMPLETED (REQUESTED / ACCEPTED ─▶ CANCELLED)
accept(): compareAndSet(REQUESTED, ACCEPTED) → exactly ONE driver wins · illegal move → exception
FareStrategy per vehicle: base + per km × km + per minute × minutes × surge
surge = requests ÷ free drivers, never below 1, capped at 2 · rating: 1 to 5, average of all trips
9. Interview follow-ups
| Question | Answer |
|---|---|
| 50,000 drivers: is a scan of all of them OK? | No. Cut the city into grid cells (say 1 km squares) and keep a map from cell to drivers. Look only in the rider's cell and the 8 around it; widen the ring if nobody is free. A geohash is a ready-made version: a short text code for each cell, where nearby places share a prefix. The mini project does the 1 km grid. |
| Drivers move. How do you keep cells right? | Each driver's phone sends its location every few seconds; move the driver from the old cell to the new one when the cell changes. |
| Many servers, not one JVM? | compareAndSet protects one JVM's memory. Let the database decide: UPDATE trips SET state = 'ACCEPTED', driver = ? WHERE id = ? AND state = 'REQUESTED'; 1 row changed = you won, 0 = someone else did. |
| Nobody accepts? | A timeout (say 15 seconds), then offer the trip to the next drivers, maybe a wider area. |
| The rider cancels late? | A cancellation fee rule, for example after ACCEPTED and more than 5 minutes later. It belongs to the CANCELLED move. |
| Vehicle type? | The strategy filters by the type the rider asked for (the mini project does this). |
| Who else rates? | Drivers can rate riders too: the same rate() on a Rider. |
| How is ETA shown? | Distance ÷ an average speed for the area and hour, refreshed as the driver moves (ETA estimation came up in the food delivery episode). |
10. Common mistakes
| Mistake | What you see (real) | Fix |
|---|---|---|
| Take the first free driver | Trip: Asha with Ramesh while Ramesh is 10.0 km away and Imran 1.0 km |
Nearest free driver |
| An if-else per matching rule | one matching method that keeps growing | DriverMatchingStrategy, one class per rule |
| Check the status, then set it | accepted by [Imran, Ramesh, Sunita], ... (all three) |
compareAndSet(REQUESTED, ACCEPTED) |
Status as a free-form String |
T2: COMPLETED -> charge the rider for a trip never started |
A trip state machine: trip is COMPLETED, cannot go CANCELLED |
| No validation on ratings | a 6-star or 0-star rating breaks the average | rating must be 1 to 5, got 6 |
| Surge with no cap | 40 requests, 10 drivers → × 4.0 | Math.min(2.0, ...): × 2.0 |
| Surge of 0 drivers | division by zero | Math.max(1, freeDrivers) |
Mini project: a small ride-sharing app with a grid
One program that puts it all together: a 1 km grid for driver search, a matching strategy that filters by vehicle type and offers the trip to the 3 nearest free drivers, three threads accepting at once, the state machine, a fare with surge, and ratings.
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicReference;
record Location(double x, double y) {
double distanceTo(Location o) { return Math.hypot(x - o.x, y - o.y); }
String cell() { return (int) Math.floor(x) + ":" + (int) Math.floor(y); } // 1 km grid cell
}
enum VehicleType { BIKE, AUTO, CAR }
record Vehicle(VehicleType type, String number) {}
record Rider(String name, Location at) {}
class Driver {
final String name; final Vehicle vehicle; volatile Location at; volatile boolean free = true;
private int stars, ratings;
Driver(String name, Vehicle vehicle, Location at) { this.name = name; this.vehicle = vehicle; this.at = at; }
synchronized void rate(int s) {
if (s < 1 || s > 5) throw new IllegalArgumentException("rating must be 1 to 5, got " + s);
stars += s; ratings++;
}
synchronized double rating() { return ratings == 0 ? 5.0 : (double) stars / ratings; } // new drivers start at 5
}
enum TripState { REQUESTED, ACCEPTED, STARTED, COMPLETED, CANCELLED;
boolean canGo(TripState to) {
return switch (this) {
case REQUESTED -> to == ACCEPTED || to == CANCELLED;
case ACCEPTED -> to == STARTED || to == CANCELLED;
case STARTED -> to == COMPLETED;
default -> false;
};
}
}
class Trip {
final String id; final Rider rider; final VehicleType type; final Location pickup, drop;
final AtomicReference<TripState> state = new AtomicReference<>(TripState.REQUESTED);
volatile Driver driver;
Trip(String id, Rider rider, VehicleType type, Location drop) {
this.id = id; this.rider = rider; this.type = type; this.pickup = rider.at(); this.drop = drop;
}
boolean accept(Driver d) { // single winner
if (!state.compareAndSet(TripState.REQUESTED, TripState.ACCEPTED)) return false;
driver = d; d.free = false; return true;
}
void move(TripState to) {
TripState now = state.get();
if (!now.canGo(to) || !state.compareAndSet(now, to))
throw new IllegalStateException(id + ": trip is " + state.get() + ", cannot go " + to);
}
}
interface DriverMatchingStrategy { List<Driver> candidates(Trip t, List<Driver> nearby, int howMany); }
class NearestDriver implements DriverMatchingStrategy {
public List<Driver> candidates(Trip t, List<Driver> nearby, int howMany) {
return nearby.stream().filter(d -> d.free && d.vehicle.type() == t.type)
.sorted(Comparator.comparingDouble(d -> d.at.distanceTo(t.pickup))).limit(howMany).toList();
}
}
interface FareStrategy { double fare(double km, int minutes); }
record PerKmFare(int base, int perKm, int perMin) implements FareStrategy {
public double fare(double km, int min) { return base + perKm * km + perMin * min; }
}
class RideApp {
private final Map<String, List<Driver>> grid = new ConcurrentHashMap<>(); // cell -> drivers
private final Map<VehicleType, FareStrategy> fares = new EnumMap<>(VehicleType.class);
private DriverMatchingStrategy matching = new NearestDriver();
int openRequests = 0;
RideApp() {
fares.put(VehicleType.BIKE, new PerKmFare(15, 6, 1));
fares.put(VehicleType.AUTO, new PerKmFare(25, 12, 1));
fares.put(VehicleType.CAR, new PerKmFare(45, 15, 2));
}
void setMatching(DriverMatchingStrategy s) { matching = s; }
void addDriver(Driver d) { grid.computeIfAbsent(d.at.cell(), k -> new CopyOnWriteArrayList<>()).add(d); }
List<Driver> nearby(Location p) { // the rider's cell + the 8 around it
List<Driver> out = new ArrayList<>();
int cx = (int) Math.floor(p.x()), cy = (int) Math.floor(p.y());
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++)
out.addAll(grid.getOrDefault((cx + dx) + ":" + (cy + dy), List.of()));
return out;
}
List<Driver> offer(Trip t) { return matching.candidates(t, nearby(t.pickup), 3); }
long freeDriversNear(Location p) { return nearby(p).stream().filter(d -> d.free).count(); }
double surge(Location p) {
return Math.min(2.0, Math.max(1.0, (double) openRequests / Math.max(1, freeDriversNear(p))));
}
double fare(Trip t, int minutes, double surge) {
return fares.get(t.type).fare(t.pickup.distanceTo(t.drop), minutes) * surge;
}
}
public class Main {
public static void main(String[] args) throws Exception {
RideApp app = new RideApp();
app.addDriver(new Driver("Imran", new Vehicle(VehicleType.AUTO, "MH12-2002"), new Location(0.5, 1.2)));
app.addDriver(new Driver("Ramesh", new Vehicle(VehicleType.AUTO, "MH12-1001"), new Location(1.5, 0.4)));
app.addDriver(new Driver("Sunita", new Vehicle(VehicleType.CAR, "MH12-3003"), new Location(0.2, 0.3)));
app.addDriver(new Driver("Pooja", new Vehicle(VehicleType.AUTO, "MH12-4004"), new Location(-0.6, 0.8)));
app.addDriver(new Driver("Far Away Faiz", new Vehicle(VehicleType.AUTO, "MH12-5005"), new Location(9.0, 9.0)));
Rider asha = new Rider("Asha", new Location(0.1, 0.1));
Trip trip = new Trip("T1", asha, VehicleType.AUTO, new Location(3.1, 4.1)); // 5 km away
List<Driver> offered = app.offer(trip);
System.out.println("nearby: " + app.nearby(asha.at()).size() + " drivers, offered to "
+ offered.stream().map(d -> d.name).toList());
ExecutorService pool = Executors.newFixedThreadPool(offered.size());
CountDownLatch go = new CountDownLatch(1);
List<Future<Boolean>> taps = new ArrayList<>();
for (Driver d : offered) taps.add(pool.submit(() -> { go.await(); return trip.accept(d); }));
go.countDown();
int wins = 0; for (Future<Boolean> f : taps) if (f.get()) wins++;
pool.shutdown();
System.out.println("winners: " + wins + ", state " + trip.state.get());
app.openRequests = 6; // 6 open requests, 3 free drivers nearby
double surge = app.surge(asha.at());
trip.move(TripState.STARTED);
trip.move(TripState.COMPLETED);
trip.driver.free = true;
System.out.printf("surge x%.1f, fare Rs %.0f, state %s%n", surge, app.fare(trip, 15, surge), trip.state.get());
trip.driver.rate(5);
trip.driver.rate(4);
System.out.printf("driver rating %.1f%n", trip.driver.rating());
try { trip.move(TripState.CANCELLED); } catch (IllegalStateException e) { System.out.println(e.getMessage()); }
try { trip.driver.rate(0); } catch (IllegalArgumentException e) { System.out.println(e.getMessage()); }
}
}
Real output (the same in every run; which of the three drivers won changes, so it is not printed):
nearby: 4 drivers, offered to [Pooja, Imran, Ramesh]
winners: 1, state ACCEPTED
surge x2.0, fare Rs 200, state COMPLETED
driver rating 4.5
T1: trip is COMPLETED, cannot go CANCELLED
rating must be 1 to 5, got 0
Notes on the design:
Location.cell()turns a point into its 1 km cell, like"0:0".nearby()looks in 9 cells only, so "Far Away Faiz" at (9, 9) is never even looked at: 4 drivers checked, not 5 (and not 50,000 in a real city).NearestDriverfilters by vehicle type: Sunita drives a car, so she is not offered an auto ride, even though she is the closest.- After one driver accepts, 3 drivers are still free nearby (Sunita and two autos); 6 open requests ÷ 3 = × 2.0 surge. The trip is 5 km (from (0.1, 0.1) to (3.1, 4.1)), so the auto fare is 100 × 2 = Rs 200.
- A new driver with no ratings starts at 5.0 here; that's a product decision, written down in one place.
Practice
1. Add a CheapestNearbyStrategy? No: matching picks drivers, not prices. Instead, add LeastBusyDriver: among free drivers within 3 km, pick the one who has done the fewest trips today. What changes?
Answer
Add a tripsToday field to Driver and one new class: class LeastBusyDriver implements DriverMatchingStrategy, which filters free && distance <= 3 and takes min(Comparator.comparingInt(d -> d.tripsToday)). Nothing else changes: the caller still calls match(rider, drivers). That is the point of the Strategy pattern.
2. In the state machine, a rider cancels while the driver presses "Start ride" at the same moment. What happens?
Answer
Both threads read ACCEPTED. Both moves are allowed from ACCEPTED, but move() uses compareAndSet(ACCEPTED, to), so only one succeeds. The other sees the state already changed and throws IllegalStateException ("trip is STARTED, cannot go CANCELLED" or "trip is CANCELLED, cannot go STARTED"). The app shows that driver or rider the real state.
3. A car: base 45, 15 per km, 2 per minute. 8 km, 20 minutes, 25 requests, 20 free drivers. What is the fare?
Answer
45 + 15 × 8 + 2 × 20 = 45 + 120 + 40 = 205. Surge = 25 ÷ 20 = 1.25 (between 1 and 2). Fare = 205 × 1.25 = Rs 256.25, which a real app would round, for example to Rs 256.
4. Why does the surge use Math.max(1, freeDrivers)?
Answer
With 0 free drivers, requests / 0 with doubles is Infinity (and with ints, an ArithmeticException). Math.max(1, ...) treats "no drivers" as 1, and the cap then gives × 2.0.
5. Add a cancellation fee: Rs 30 if the rider cancels after ACCEPTED, free before.
Answer
In a cancel() method: read the state; if it is REQUESTED, move(CANCELLED) and charge 0; if ACCEPTED, move(CANCELLED) and charge 30; in any other state, move(CANCELLED) throws, which is what we want (you cannot cancel a started or finished trip). Because move uses compareAndSet, read the fee from the state you actually moved from.
6. Why is a grid cell lookup faster than a scan?
Answer
A scan computes a distance to every driver in the city: 50,000 for each request. A grid keeps a map from cell to drivers, so a request looks in 9 cells, typically a few dozen drivers. Getting a cell's list from a hash map takes about the same time however big the city is.
Quick quiz
An auto: base 25 + 12 per km + 1 per minute. The trip is 5 km and 15 minutes. Right now: 60 requests, 20 free drivers. Surge = requests ÷ drivers, capped at 2. What does the rider pay? (a) Rs 100 (b) Rs 150 (c) Rs 200 (d) Rs 300
Answer
(c) Rs 200. Fare = 25 + 60 + 15 = 100. Surge = 60 ÷ 20 = 3, but the cap is 2. So 100 × 2 = 200. (d) is what you get if you forget the cap.
Interview questions
- What are the main classes of a ride-sharing app? Rider, Driver, Vehicle, Location, Trip, plus a matching strategy, a fare strategy and a service that ties them together.
- How do you find the nearest driver? Filter free drivers (of the right vehicle type), take the minimum distance; at scale, search only nearby grid cells or geohash cells.
- Why a strategy for matching? The rule changes (nearest, best-rated, least busy); each rule is a class behind one interface, swapped without editing callers.
- What are the trip states? REQUESTED, ACCEPTED, STARTED, COMPLETED, CANCELLED, with only the allowed moves; anything else throws.
- Three drivers accept at once. How do you give the trip to exactly one? An atomic compare-and-set from REQUESTED to ACCEPTED (or
synchronized); in a database, anUPDATE ... WHERE state = 'REQUESTED'. - How is the fare calculated? A fare strategy per vehicle: base + per km + per minute, times the surge multiplier.
- How does surge pricing work, and why cap it? Demand ÷ supply in an area, never below 1; capped so riders are never charged an extreme price.
- How do ratings work? 1 to 5 only, validated; the rating is the average; new drivers need a starting value.
- What if no driver accepts? Time out and offer the trip to the next drivers or a wider area; tell the rider if nobody is found.
- What changes with many servers? In-memory locks don't cross servers: use database conditional updates, and keep driver locations in a shared store.
Glossary
| Term | Meaning, with an example |
|---|---|
| Ride-sharing app | An app that connects people who want a ride with drivers nearby: tap, and an auto comes |
| Ride-sharing requirements | What the app must do: request, match, accept, ride, pay, rate |
| Rider | The person who wants a ride: Asha at the station |
| Driver | The person who drives; free or busy, with a location and a rating: Imran |
| Vehicle | What a driver drives: type BIKE, AUTO or CAR, and a number plate MH12-2002 |
| Vehicle type | The kind of vehicle; it decides the fare rule and which drivers match |
| Location | A point on the map; here (x, y) in km on a city grid, the station at (0, 0) |
| City grid | Pretend the city is graph paper with 1 km squares, so distances are easy numbers |
| Distance (straight line) | Math.hypot(dx, dy): from (0, 0) to (6, 8) is 10 km |
| Trip | One ride: rider, driver, pickup, drop, state, fare |
| Pickup / drop | Where the ride starts / ends |
| Free / busy | Whether a driver can take a new trip right now |
| Nearest driver search | Among free drivers, pick the smallest distance: Imran at 1 km, not Ramesh at 10 km |
| Linear scan | Checking every item one by one: fine for 3 drivers, slow for 50,000 |
| Grid cell lookup | Keep drivers in a map by 1 km cell and search only the rider's cell and its neighbours |
| Geohash | A short text code for a map cell; nearby places share the start of the code |
| Driver matching strategy | The swappable rule that picks a driver: NearestDriver, BestRatedDriver |
| Strategy pattern | One interface, one class per rule, chosen at run time (episode 34) |
| Optional | A box that holds a value or is empty: Optional.empty = "no driver" |
| Rating | Stars from 1 to 5 given after a trip; the driver's rating is the average: 5, 4, 4 → 4.3 |
| Average | Total ÷ count: 13 stars ÷ 3 trips = 4.33 |
| Validation | Refusing bad input: rating must be 1 to 5, got 6 |
| Trip state machine | The states a trip can be in and the only moves allowed between them |
| State | Where the trip is right now: REQUESTED, ACCEPTED, STARTED, COMPLETED or CANCELLED |
| Transition | A move from one state to another: ACCEPTED → STARTED |
| Illegal transition | A move the machine does not allow: COMPLETED → CANCELLED, which throws |
| enum | A Java type with a fixed list of values: enum TripState { REQUESTED, ... } |
| IllegalStateException | Java's exception for "this object can't do that right now": trip is COMPLETED, cannot go CANCELLED |
| IllegalArgumentException | Java's exception for a bad argument: rating must be 1 to 5, got 6 |
| Thread | One line of work running in a program; one per driver tap here |
| Thread pool / ExecutorService | A team of ready threads: Executors.newFixedThreadPool(3) |
| Future | A handle to a task's result, collected with get() |
| CountDownLatch | A starting gun: threads await(), one countDown() releases them all |
| Race condition | The result depends on which thread runs first: one trip accepted by 3 drivers |
| Check-then-act | Checking and acting as two separate steps, with a gap between them |
| Concurrent driver acceptance | Several drivers accepting one trip at the same moment; exactly one must win |
| Atomic | Done as one step that can't be split; nobody can act in the middle |
| AtomicReference | A Java holder for one value that supports atomic updates |
| compareAndSet (CAS) | "Set it to B only if it is still A", atomically; returns true to the one winner |
| synchronized | Java keyword: only one thread at a time runs this method or block |
| volatile | Java keyword: every thread sees the latest value of this field |
| CopyOnWriteArrayList | A list that many threads can add to safely |
| Fare | The price the rider pays for a trip |
| Fare calculation strategy | The swappable rule that prices a trip: FareStrategy |
| Base fare | The fixed part of a fare: 25 for an auto |
| Per km / per minute rate | The price per kilometre / per minute: 12 and 1 for an auto |
| Surge pricing | Multiplying the fare when demand is high and few drivers are free |
| Demand / supply ratio | Ride requests ÷ free drivers in an area: 15 ÷ 10 = 1.5 |
| Surge multiplier | The number the fare is multiplied by: between 1 and 2 here |
| Cap | An upper limit: 40 ÷ 10 = 4, capped to 2 |
| Record | A short Java class for plain data: record Location(double x, double y) |
| Interface | A list of methods a class promises to have: DriverMatchingStrategy |
| LinkedHashMap | A map that remembers the order you put things in |
| Timeout | Giving up waiting after a set time: re-offer a trip after 15 seconds |
| Cancellation fee | A charge for cancelling late, after a driver accepted |
| ETA | Estimated time of arrival: how long until the driver reaches you |
| Conditional update | A database update with a condition: ... WHERE state = 'REQUESTED'; 0 rows changed = you lost |
| JVM | The Java Virtual Machine: the program that runs your Java code; one per server |
Summary
- The ride-sharing requirements give five classes: Rider, Driver, Vehicle, Location, Trip.
- First free driver sent Ramesh from 10 km away; nearest driver search sends Imran from 1 km. At scale, search grid cells, not every driver.
- A driver matching strategy (
NearestDriver,BestRatedDriver) lets the rule change without editing callers. - A
Stringstatus and check-then-act let three drivers accept one trip, and let a trip "complete" without starting. - A trip state machine allows only legal moves, and
compareAndSet(REQUESTED, ACCEPTED)makes exactly one driver win. - A fare calculation strategy per vehicle (base + per km + per minute) times a surge multiplier (demand ÷ supply, capped at 2) gives the fare; ratings are 1 to 5 and averaged.
- Next episode: a meeting room scheduler and calendar: rooms, meetings, time intervals and overlap detection.