Design a Premium Cab Hailing Service (LLD)

Problem Statement

Design and implement a premium cab hailing service (like Uber Black). Focus on the cab allocation logic with clean, running code that handles concurrent ride requests.

Requirements

1. Register drivers with their location and cab type (premium, standard)
2. Request a ride — rider specifies pickup location, destination, cab type
3. Allocate the nearest available cab matching the requested type
4. Handle concurrent requests — multiple riders requesting simultaneously should not be assigned the same driver
5. Trip lifecycle — requested → assigned → in-progress → completed
6. Update driver availability after trip completion

Constraints

• Must be a fully running solution (not pseudocode)
• Thread-safe cab allocation (no double-assignment)
• Extensible for new cab types
• Master one language for this round (syntax matters)

What the Interviewer Expects

1. Core entities: Driver, Rider, Trip, Location, CabType (enum)
2. Allocation strategy — nearest available driver. Use a strategy pattern so allocation logic can be swapped (nearest, highest-rated, etc.)
3. Concurrency handling:
   • Lock on driver assignment to prevent double-booking
   • Use synchronized blocks or concurrent data structures
   • Atomic state transition (available → assigned)
4. Design patterns:
   • Strategy — for allocation algorithm
   • State — for trip lifecycle
   • Observer — for notifying rider/driver of status changes
5. Clean separation — TripManager, DriverManager, AllocationStrategy as separate classes.

Follow-ups

1. How do you handle surge pricing based on demand?
2. What if a driver rejects a ride? How do you reallocate quickly?
3. How would you scale allocation to a city with 100K drivers?
4. How do you handle the case where two riders are equidistant from the same driver?
5. How would you add ride-pooling (multiple riders, one cab)?