Design Uber

package com.androidinterview.uber.matching;

import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

import com.androidinterview.uber.model.Driver;
import com.androidinterview.uber.model.Location;
import com.androidinterview.uber.model.RideType;

// Where nearby drivers come from. This one scans, which is honest for an
// interview and wrong for a city. In production the same method signature
// sits over a geohash, a quadtree or an H3 grid, and saying that in one
// sentence is worth more than twenty minutes of drawing one.
public final class DriverIndex {

    private static final Duration MAX_PING_AGE = Duration.ofMinutes(1);

    private final Map<String, Driver> drivers = new ConcurrentHashMap<>();

    public void register(Driver driver) {
        drivers.put(driver.id(), driver);
    }

    public List<Driver> findNearby(Location pickup, double radiusKm, RideType rideType, Instant now) {
        List<Driver> nearby = new ArrayList<>();
        for (Driver driver : drivers.values()) {
            if (!driver.isAvailable()) continue;
            if (driver.vehicle().rideType() != rideType) continue;
            // A driver whose last ping is old is probably not there any more.
            // Matching on stale coordinates sends a car that has left.
            if (Duration.between(driver.lastSeen(), now).compareTo(MAX_PING_AGE) > 0) continue;
            if (driver.location().distanceKmTo(pickup) > radiusKm) continue;
            nearby.add(driver);
        }
        return nearby;
    }
}

package com.androidinterview.uber.matching;

import java.util.List;

import com.androidinterview.uber.model.Driver;
import com.androidinterview.uber.model.RideRequest;

// Ranking only. It orders the candidates and stops there. Claiming a driver is
// the service's job, because the claim has to be atomic and a policy author
// should not have to get that right again in every new strategy.
public interface MatchingStrategy {
    List<Driver> rank(RideRequest request, List<Driver> candidates);
}

package com.androidinterview.uber.matching;

import java.util.Comparator;
import java.util.List;

import com.androidinterview.uber.model.Driver;
import com.androidinterview.uber.model.RideRequest;

// The policy everybody starts with. A rating aware or idle time aware version
// is a different class and one line of wiring.
public final class NearestDriverStrategy implements MatchingStrategy {

    @Override
    public List<Driver> rank(RideRequest request, List<Driver> candidates) {
        return candidates.stream()
                .sorted(Comparator.comparingDouble(
                        driver -> driver.location().distanceKmTo(request.pickup())))
                .toList();
    }
}

package com.androidinterview.uber.model;

import java.time.Instant;

// The most important small class in this design, because the whole race for a
// driver is settled inside it.
public final class Driver {

    private final String id;
    private final String name;
    private final Vehicle vehicle;
    private DriverStatus status = DriverStatus.OFFLINE;
    private Location location;
    private Instant lastSeen;
    private String currentTripId;
    private double rating;

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

    public String id() { return id; }
    public String name() { return name; }
    public Vehicle vehicle() { return vehicle; }
    public double rating() { return rating; }
    public synchronized DriverStatus status() { return status; }
    public synchronized boolean isAvailable() { return status == DriverStatus.AVAILABLE; }
    public synchronized Location location() { return location; }
    public synchronized Instant lastSeen() { return lastSeen; }

    // Position first, availability second. The other order makes the driver
    // discoverable for an instant with no location and no ping to filter on.
    public synchronized void goOnline(Location at, Instant now) {
        ping(at, now);
        status = DriverStatus.AVAILABLE;
    }

    public synchronized void ping(Location at, Instant now) {
        this.location = at;
        this.lastSeen = now;
    }

    // The atomic check and set. Reading the status and then writing it as two
    // separate calls leaves a window in which two trips both see AVAILABLE and
    // both assign the same driver. Doing both inside one critical section
    // means exactly one caller gets true and everyone else moves on to the
    // next candidate.
    public synchronized boolean tryAssignToTrip(String tripId) {
        if (status != DriverStatus.AVAILABLE) {
            return false;
        }
        status = DriverStatus.ON_TRIP;
        currentTripId = tripId;
        return true;
    }

    // Owner checked release, the same idea as an expiring hold. A driver who
    // accepted at fourteen and a half seconds must not be freed by the offer
    // timeout that fires at fifteen.
    public synchronized boolean releaseIfOn(String tripId) {
        if (!tripId.equals(currentTripId)) {
            return false;
        }
        status = DriverStatus.AVAILABLE;
        currentTripId = null;
        return true;
    }
}

package com.androidinterview.uber.model;

public enum DriverStatus {
    OFFLINE,
    AVAILABLE,
    ON_TRIP
}

package com.androidinterview.uber.model;

// A point, and the one piece of maths this problem needs. Keeping distance on
// the value object means no service anywhere writes trigonometry.
public record Location(double latitude, double longitude) {

    private static final double EARTH_RADIUS_KM = 6371.0;

    public double distanceKmTo(Location other) {
        double dLat = Math.toRadians(other.latitude - latitude);
        double dLng = Math.toRadians(other.longitude - longitude);
        double a = Math.pow(Math.sin(dLat / 2), 2)
                + Math.cos(Math.toRadians(latitude))
                * Math.cos(Math.toRadians(other.latitude))
                * Math.pow(Math.sin(dLng / 2), 2);
        return 2 * EARTH_RADIUS_KM * Math.asin(Math.sqrt(a));
    }
}

package com.androidinterview.uber.model;

// Minor units and a currency. A fare computed in floating point is a fare that
// disagrees with the receipt.
public record Money(String currency, long amount) {

    public Money plus(Money other) {
        return new Money(currency, amount + other.amount);
    }

    public Money scale(double factor) {
        return new Money(currency, Math.round(amount * factor));
    }
}

package com.androidinterview.uber.model;

// One request, carried as a value so pricing and matching take a single
// argument rather than six that can be passed in the wrong order.
public record RideRequest(
        Rider rider,
        Location pickup,
        Location dropOff,
        RideType rideType,
        double estimatedKm,
        int estimatedMinutes) {
}

package com.androidinterview.uber.model;

// The rates live on the enum, so nothing else in the system ever writes a
// switch over ride types. Adding a new product is one line here.
public enum RideType {
    BIKE(2000, 800, 150),
    AUTO(3000, 1100, 200),
    SEDAN(5000, 1500, 300),
    SUV(7000, 2200, 400);

    private final long baseFare;
    private final long perKm;
    private final long perMinute;

    RideType(long baseFare, long perKm, long perMinute) {
        this.baseFare = baseFare;
        this.perKm = perKm;
        this.perMinute = perMinute;
    }

    public long baseFare() { return baseFare; }
    public long perKm() { return perKm; }
    public long perMinute() { return perMinute; }
}

package com.androidinterview.uber.model;

public record Rider(String id, String name) {
}

package com.androidinterview.uber.model;

import java.util.HashSet;
import java.util.Set;

// The fare is quoted once, at request time, and stored. Recomputing it at the
// end would let a surge that started mid ride change a price the rider already
// agreed to.
//
// Two kinds of transition live here. The offer protocol, offer, accept and
// withdraw, answers yes or no, because it races a timer by design and losing
// that race is an expected outcome. The rest throw, because a caller who
// starts a trip nobody accepted has a bug, not a race.
public final class Trip {

    private final String id;
    private final RideRequest request;
    private final Money quotedFare;
    private TripStatus status = TripStatus.REQUESTED;
    private Driver driver;
    // Drivers who let an offer lapse. A rematch skips them, otherwise the
    // nearest driver who ignored the offer is simply asked again.
    private final Set<String> declined = new HashSet<>();

    public Trip(String id, RideRequest request, Money quotedFare) {
        this.id = id;
        this.request = request;
        this.quotedFare = quotedFare;
    }

    public String id() { return id; }
    public RideRequest request() { return request; }
    public Money quotedFare() { return quotedFare; }
    public synchronized TripStatus status() { return status; }
    public synchronized Driver driver() { return driver; }
    public synchronized boolean hasDeclined(String driverId) { return declined.contains(driverId); }

    // Push the offer to a driver the service has already claimed. False means
    // the trip is no longer waiting, which is to say the rider cancelled while
    // the claim was happening, and the caller hands the driver straight back.
    public synchronized boolean offerTo(Driver candidate) {
        if (status != TripStatus.REQUESTED) {
            return false;
        }
        status = TripStatus.OFFERED;
        driver = candidate;
        return true;
    }

    // Only the driver the offer went to can accept it, and only while it is
    // still open. A retry from a flaky client and a tap that lands after the
    // timeout both get false and change nothing.
    public synchronized boolean accept(String driverId) {
        if (status != TripStatus.OFFERED || !driver.id().equals(driverId)) {
            return false;
        }
        status = TripStatus.ASSIGNED;
        return true;
    }

    // The timeout side of the same race. It succeeds only while the offer to
    // this driver is still open, so an accept that landed first wins, and it
    // hands back the driver it withdrew from so the caller can release them.
    public synchronized Driver withdrawOffer(String driverId) {
        if (status != TripStatus.OFFERED || !driver.id().equals(driverId)) {
            return null;
        }
        Driver withdrawn = driver;
        declined.add(withdrawn.id());
        driver = null;
        status = TripStatus.REQUESTED;
        return withdrawn;
    }

    public synchronized TripStatus start() {
        return moveTo(TripStatus.IN_PROGRESS);
    }

    public synchronized TripStatus complete() {
        return moveTo(TripStatus.COMPLETED);
    }

    public synchronized TripStatus cancel() {
        return moveTo(TripStatus.CANCELLED);
    }

    // Returns the status it left, read under the same lock as the write, so
    // the event the service publishes says where the trip really came from.
    private TripStatus moveTo(TripStatus next) {
        if (!status.canMoveTo(next)) {
            throw new IllegalStateException("cannot move a trip from " + status + " to " + next);
        }
        TripStatus from = status;
        status = next;
        return from;
    }
}

package com.androidinterview.uber.model;

// The lifecycle, with the legal moves in one place. It stops a trip being
// completed before it started and a completed trip being cancelled.
//
// OFFERED is the state most write ups leave out. A driver has been claimed and
// asked, and has not yet said yes. The edge back to REQUESTED is what a timed
// out offer takes.
public enum TripStatus {
    REQUESTED,
    OFFERED,
    ASSIGNED,
    IN_PROGRESS,
    COMPLETED,
    CANCELLED;

    public boolean canMoveTo(TripStatus next) {
        return switch (this) {
            case REQUESTED -> next == OFFERED || next == CANCELLED;
            case OFFERED -> next == ASSIGNED || next == REQUESTED || next == CANCELLED;
            case ASSIGNED -> next == IN_PROGRESS || next == CANCELLED;
            case IN_PROGRESS -> next == COMPLETED;
            case COMPLETED, CANCELLED -> false;
        };
    }
}

package com.androidinterview.uber.model;

public record Vehicle(String plate, String model, RideType rideType) {
}

package com.androidinterview.uber.pricing;

import com.androidinterview.uber.model.Money;
import com.androidinterview.uber.model.RideRequest;

public interface PricingStrategy {
    Money quote(RideRequest request);
}

package com.androidinterview.uber.pricing;

import com.androidinterview.uber.model.Money;
import com.androidinterview.uber.model.RideRequest;
import com.androidinterview.uber.model.RideType;

// Base plus distance plus time, at the rates carried by the ride type.
public final class StandardPricing implements PricingStrategy {

    private final String currency;

    public StandardPricing(String currency) {
        this.currency = currency;
    }

    @Override
    public Money quote(RideRequest request) {
        RideType type = request.rideType();
        long amount = type.baseFare()
                + Math.round(type.perKm() * request.estimatedKm())
                + type.perMinute() * request.estimatedMinutes();
        return new Money(currency, amount);
    }
}

package com.androidinterview.uber.pricing;

import java.util.function.ToDoubleFunction;

import com.androidinterview.uber.model.Location;
import com.androidinterview.uber.model.Money;
import com.androidinterview.uber.model.RideRequest;

// Surge is a decorator over pricing, not another pricing strategy. That
// distinction is the best small idea in this problem.
//
// As a sibling it would have to reimplement base plus distance plus time, and
// then again for every future rule, airport fees, tolls, a promotion. As a
// wrapper it multiplies whatever came out of the rule underneath, so it
// composes with all of them and stays four lines forever.
//
// Where the multiplier comes from is a windowed count of requests against
// available cars in a geofence. That is a background pipeline, and for this
// round it is a function that answers a question.
public final class SurgePricing implements PricingStrategy {

    private final PricingStrategy inner;
    private final ToDoubleFunction<Location> multiplierAt;

    public SurgePricing(PricingStrategy inner, ToDoubleFunction<Location> multiplierAt) {
        this.inner = inner;
        this.multiplierAt = multiplierAt;
    }

    @Override
    public Money quote(RideRequest request) {
        return inner.quote(request).scale(multiplierAt.applyAsDouble(request.pickup()));
    }
}

package com.androidinterview.uber.service;

import java.time.Clock;
import java.time.Duration;
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.UUID;
import java.util.concurrent.CopyOnWriteArrayList;

import com.androidinterview.uber.matching.DriverIndex;
import com.androidinterview.uber.matching.MatchingStrategy;
import com.androidinterview.uber.model.Driver;
import com.androidinterview.uber.model.Money;
import com.androidinterview.uber.model.RideRequest;
import com.androidinterview.uber.model.Trip;
import com.androidinterview.uber.model.TripStatus;
import com.androidinterview.uber.pricing.PricingStrategy;

// The one class the apps talk to. It sequences the steps and owns nothing that
// varies. Matching policy, pricing and the driver index were all handed to it.
//
// The offer protocol is push and accept. One driver is claimed and asked, and
// a scheduler calls offerTimedOut after OFFER_WINDOW if the driver has not
// answered. The service never sleeps and never owns a timer, so a test can
// drive the whole protocol with plain method calls.
public final class RideService {

    public static final Duration OFFER_WINDOW = Duration.ofSeconds(15);

    private static final double[] SEARCH_RADII_KM = {2.0, 5.0, 10.0};

    private final DriverIndex index;
    private final MatchingStrategy matching;
    private final PricingStrategy pricing;
    private final Clock clock;
    private final List<TripObserver> observers = new CopyOnWriteArrayList<>();

    public RideService(DriverIndex index, MatchingStrategy matching,
                       PricingStrategy pricing, Clock clock) {
        this.index = index;
        this.matching = matching;
        this.pricing = pricing;
        this.clock = clock;
    }

    public void subscribe(TripObserver observer) {
        observers.add(observer);
    }

    // Quote once, then offer. The quote is stored on the trip, so a surge that
    // starts while the rider is still deciding cannot change a price they have
    // already seen.
    public Optional<Trip> requestRide(RideRequest request) {
        Money fare = pricing.quote(request);
        Trip trip = new Trip(UUID.randomUUID().toString(), request, fare);
        return offer(trip) ? Optional.of(trip) : Optional.empty();
    }

    // Widen the circle rather than failing at the first empty ring. The walk
    // over ranked candidates is where the race is settled. tryAssignToTrip
    // either wins outright or returns false, and a loser simply takes the next
    // name on the list. The first driver claimed gets the offer, and nobody
    // else can be offered that driver while they decide.
    //
    // The claim comes first because it is the contested step. If the trip
    // then refuses the offer, the rider cancelled while we were claiming, and
    // the driver goes straight back so no driver is ever stuck on a trip that
    // was never offered to them.
    private boolean offer(Trip trip) {
        for (double radiusKm : SEARCH_RADII_KM) {
            List<Driver> candidates = index.findNearby(
                    trip.request().pickup(), radiusKm, trip.request().rideType(), clock.instant());
            for (Driver driver : matching.rank(trip.request(), candidates)) {
                if (trip.hasDeclined(driver.id()) || !driver.tryAssignToTrip(trip.id())) {
                    continue;
                }
                if (!trip.offerTo(driver)) {
                    driver.releaseIfOn(trip.id());
                    return false;
                }
                publish(trip, TripStatus.REQUESTED);
                return true;
            }
        }
        return false;
    }

    // The driver tapped accept. True means they now hold the trip. False means
    // the offer was not theirs or was no longer open, and nothing changed.
    public boolean acceptOffer(Trip trip, String driverId) {
        if (!trip.accept(driverId)) {
            return false;
        }
        publish(trip, TripStatus.OFFERED);
        return true;
    }

    // The window closed without an accept. Withdraw the offer on the trip
    // first and release the driver second. The other order opens a window in
    // which an accept lands on a trip whose driver has already been given
    // away. The withdrawal only succeeds while the offer to this driver is
    // still open, so an accept at fourteen point nine beats a timeout at
    // fifteen, and the driver keeps the job.
    //
    // Returns true when a fresh offer went out to somebody else. False means
    // either the driver accepted first, or nobody else is available and the
    // trip is back in REQUESTED for the caller to retry or cancel.
    public boolean offerTimedOut(Trip trip, String driverId) {
        Driver driver = trip.withdrawOffer(driverId);
        if (driver == null) {
            return false;
        }
        driver.releaseIfOn(trip.id());
        publish(trip, TripStatus.OFFERED);
        return offer(trip);
    }

    public void startTrip(Trip trip) {
        publish(trip, trip.start());
    }

    public void completeTrip(Trip trip) {
        TripStatus from = trip.complete();
        trip.driver().releaseIfOn(trip.id());
        publish(trip, from);
    }

    // Either side can cancel, and the driver goes back in the pool either way.
    // A second cancel throws on the status guard before it reaches the
    // release, which is what stops two cancellations freeing the driver twice.
    // Whether a fee is charged is a policy question, and policy does not belong
    // in the class that moves cars around.
    public void cancelTrip(Trip trip) {
        Driver driver = trip.driver();
        TripStatus from = trip.cancel();
        if (driver != null) {
            driver.releaseIfOn(trip.id());
        }
        publish(trip, from);
    }

    private void publish(Trip trip, TripStatus from) {
        List<TripObserver> snapshot = new ArrayList<>(observers);
        for (TripObserver observer : snapshot) {
            observer.onStatusChanged(trip, from);
        }
    }
}

package com.androidinterview.uber.service;

import com.androidinterview.uber.model.Trip;
import com.androidinterview.uber.model.TripStatus;

// One event, several audiences. The rider app, the driver app and the
// analytics feed all want the same status change and none of them belong in
// the trip lifecycle, so the service publishes and forgets.
@FunctionalInterface
public interface TripObserver {
    void onStatusChanged(Trip trip, TripStatus from);
}

package com.androidinterview.uber.matching

import com.androidinterview.uber.model.Driver
import com.androidinterview.uber.model.Location
import com.androidinterview.uber.model.RideRequest
import com.androidinterview.uber.model.RideType
import java.time.Duration
import java.time.Instant
import java.util.concurrent.ConcurrentHashMap

// Ranking only. It orders the candidates and stops there. Claiming a driver is
// the service's job, because the claim has to be atomic and a policy author
// should not have to get that right again in every new strategy.
//
// It is a function type, not an interface, because it has no state and no
// configuration. A rating aware policy is a lambda.
typealias MatchingStrategy = (RideRequest, List<Driver>) -> List<Driver>

val nearestFirst: MatchingStrategy = { request, candidates ->
    candidates.sortedBy { it.location.distanceKmTo(request.pickup) }
}

val bestRatedFirst: MatchingStrategy = { _, candidates ->
    candidates.sortedByDescending { it.rating }
}

// Where nearby drivers come from. This one scans, which is honest for an
// interview and wrong for a city. In production the same signature sits over a
// geohash, a quadtree or an H3 grid.
class DriverIndex {

    private val drivers = ConcurrentHashMap<String, Driver>()

    fun register(driver: Driver) {
        drivers[driver.id] = driver
    }

    fun findNearby(pickup: Location, radiusKm: Double, rideType: RideType, now: Instant): List<Driver> =
        drivers.values.filter { driver ->
            driver.isAvailable &&
                driver.vehicle.rideType == rideType &&
                // A driver whose last ping is old is probably not there any
                // more. Matching on stale coordinates sends a car that has left.
                Duration.between(driver.lastSeen, now) <= MAX_PING_AGE &&
                driver.location.distanceKmTo(pickup) <= radiusKm
        }

    private companion object {
        val MAX_PING_AGE: Duration = Duration.ofMinutes(1)
    }
}

package com.androidinterview.uber.model

import kotlin.math.PI
import kotlin.math.asin
import kotlin.math.cos
import kotlin.math.roundToLong
import kotlin.math.sin
import kotlin.math.sqrt

// Minor units and a currency. A fare computed in floating point is a fare that
// disagrees with the receipt.
data class Money(val currency: String, val amount: Long) {
    operator fun times(factor: Double) = copy(amount = (amount * factor).roundToLong())
}

// A point, and the one piece of maths this problem needs. Keeping distance on
// the value object means no service anywhere writes trigonometry.
data class Location(val latitude: Double, val longitude: Double) {

    fun distanceKmTo(other: Location): Double {
        val dLat = (other.latitude - latitude).toRadians()
        val dLng = (other.longitude - longitude).toRadians()
        val a = sin(dLat / 2) * sin(dLat / 2) +
            cos(latitude.toRadians()) * cos(other.latitude.toRadians()) *
            sin(dLng / 2) * sin(dLng / 2)
        return 2 * EARTH_RADIUS_KM * asin(sqrt(a))
    }

    private companion object {
        const val EARTH_RADIUS_KM = 6371.0
        fun Double.toRadians() = this * PI / 180
    }
}

// The rates ride on the enum, so nothing else ever writes a when over ride
// types. A new product is one line here.
enum class RideType(val baseFare: Long, val perKm: Long, val perMinute: Long) {
    BIKE(2000, 800, 150),
    AUTO(3000, 1100, 200),
    SEDAN(5000, 1500, 300),
    SUV(7000, 2200, 400),
}

data class Vehicle(val plate: String, val model: String, val rideType: RideType)

data class Rider(val id: String, val name: String)

data class RideRequest(
    val rider: Rider,
    val pickup: Location,
    val dropOff: Location,
    val rideType: RideType,
    val estimatedKm: Double,
    val estimatedMinutes: Int,
)

package com.androidinterview.uber.model

import java.time.Instant
import java.util.concurrent.atomic.AtomicReference

// What a driver is doing, as a sealed interface. The trip id exists only in the
// state that has one, so there is no field that is meaningfully null half the
// time.
sealed interface DriverAssignment {
    data object Offline : DriverAssignment
    data object Available : DriverAssignment
    data class OnTrip(val tripId: String) : DriverAssignment
}

// The most important small class in this design, because the whole race for a
// driver is settled inside it.
class Driver(
    val id: String,
    val name: String,
    val vehicle: Vehicle,
    val rating: Double,
    initialLocation: Location,
    initialPing: Instant,
) {
    // One immutable value behind an atomic reference, so the check and the set
    // really are one operation rather than two under a lock.
    private val assignment = AtomicReference<DriverAssignment>(DriverAssignment.Offline)

    @Volatile
    var location: Location = initialLocation
        private set

    @Volatile
    var lastSeen: Instant = initialPing
        private set

    val isAvailable: Boolean get() = assignment.get() == DriverAssignment.Available

    fun goOnline(at: Location, now: Instant) {
        ping(at, now)
        assignment.set(DriverAssignment.Available)
    }

    fun ping(at: Location, now: Instant) {
        location = at
        lastSeen = now
    }

    // compareAndSet is the check and the set in one instruction. Exactly one
    // caller can move this driver out of Available. Every other caller gets
    // false and takes the next name on the list.
    fun tryAssignToTrip(tripId: String): Boolean =
        assignment.compareAndSet(DriverAssignment.Available, DriverAssignment.OnTrip(tripId))

    // Owner checked release. Read the current value, check the trip id it
    // carries, and swap against exactly the value that was read. The swap has
    // to be against the read value and not a fresh OnTrip(tripId), because
    // compareAndSet compares references, not data class equality. A driver who
    // accepted a moment before the offer timed out keeps the trip.
    fun releaseIfOn(tripId: String): Boolean {
        val before = assignment.get()
        return before is DriverAssignment.OnTrip &&
            before.tripId == tripId &&
            assignment.compareAndSet(before, DriverAssignment.Available)
    }
}

package com.androidinterview.uber.model

import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.atomic.AtomicReference

// The lifecycle as a sealed interface rather than an enum, and this is where
// Kotlin genuinely beats the Java version. A driver exists only in the states
// that have one, so there is no nullable driver field to guard.
//
// Offered is the state most write ups leave out. A driver has been claimed and
// asked, and has not yet said yes. The move back to Requested is what a timed
// out offer takes.
sealed interface TripState {
    data object Requested : TripState
    data class Offered(val driver: Driver) : TripState
    data class Assigned(val driver: Driver) : TripState
    data class InProgress(val driver: Driver) : TripState
    data class Completed(val driver: Driver) : TripState
    data class Cancelled(val reason: String) : TripState
}

// The driver, for the states that have one. Written once as an extension so
// neither the trip nor the service repeats the when.
val TripState.driver: Driver?
    get() = when (this) {
        is TripState.Offered -> driver
        is TripState.Assigned -> driver
        is TripState.InProgress -> driver
        is TripState.Completed -> driver
        TripState.Requested, is TripState.Cancelled -> null
    }

// The fare is quoted once, at request time, and stored. Recomputing it at the
// end would let a surge that started mid ride change a price the rider already
// agreed to.
//
// The state sits behind an atomic reference and every move is a compareAndSet
// against the exact value that was read, so two callers can never both pass a
// check and both write. The offer protocol answers yes or no, because it races
// a timer by design. The rest throw, because a caller who starts a trip nobody
// accepted has a bug, not a race.
class Trip(val id: String, val request: RideRequest, val quotedFare: Money) {

    private val current = AtomicReference<TripState>(TripState.Requested)

    // Drivers who let an offer lapse. A rematch skips them, otherwise the
    // nearest driver who ignored the offer is simply asked again.
    private val declined = ConcurrentHashMap.newKeySet<String>()

    val state: TripState get() = current.get()

    fun hasDeclined(driverId: String): Boolean = driverId in declined

    val driver: Driver? get() = state.driver

    // Push the offer to a driver the service has already claimed. False means
    // the trip is no longer waiting, which is to say the rider cancelled while
    // the claim was happening, and the caller hands the driver straight back.
    fun offerTo(driver: Driver): Boolean =
        current.compareAndSet(TripState.Requested, TripState.Offered(driver))

    // Only the driver the offer went to can accept it, and only while it is
    // still open. Returns the offer it closed, or null when nothing changed.
    fun accept(driverId: String): TripState.Offered? =
        swapOffer(driverId) { TripState.Assigned(it.driver) }

    // The timeout side of the same race. It succeeds only while the offer to
    // this driver is still open, so an accept that landed first wins.
    fun withdrawOffer(driverId: String): TripState.Offered? =
        swapOffer(driverId) { TripState.Requested }?.also { declined += it.driver.id }

    fun start(): TripState.Assigned =
        move("a trip must be assigned before it starts") { TripState.InProgress(it.driver) }

    fun complete(): TripState.InProgress =
        move("a trip must be running before it completes") { TripState.Completed(it.driver) }

    // Two cancellations at once both read an open state. Exactly one swap
    // succeeds, and the other throws instead of releasing the driver twice.
    fun cancel(reason: String): TripState {
        val before = current.get()
        val open = before is TripState.Requested || before is TripState.Offered || before is TripState.Assigned
        check(open && current.compareAndSet(before, TripState.Cancelled(reason))) {
            "a trip that has started or already ended cannot be cancelled"
        }
        return before
    }

    private inline fun swapOffer(driverId: String, next: (TripState.Offered) -> TripState): TripState.Offered? {
        val before = current.get() as? TripState.Offered ?: return null
        if (before.driver.id != driverId) return null
        return if (current.compareAndSet(before, next(before))) before else null
    }

    // Each move returns the state it left, so the service can publish where
    // the trip really came from rather than a second, racy read.
    private inline fun <reified S : TripState> move(message: String, next: (S) -> TripState): S {
        val before = current.get()
        check(before is S && current.compareAndSet(before, next(before))) { message }
        return before
    }
}

package com.androidinterview.uber.pricing

import com.androidinterview.uber.model.Location
import com.androidinterview.uber.model.Money
import com.androidinterview.uber.model.RideRequest
import kotlin.math.roundToLong

fun interface PricingStrategy {
    fun quote(request: RideRequest): Money
}

// Base plus distance plus time, at the rates carried by the ride type.
fun standardPricing(currency: String) = PricingStrategy { request ->
    val type = request.rideType
    val amount = type.baseFare +
        (type.perKm * request.estimatedKm).roundToLong() +
        type.perMinute * request.estimatedMinutes
    Money(currency, amount)
}

// Surge decorates pricing, it is not a sibling of it, and that distinction is
// the best small idea in this problem.
//
// As a sibling it would have to reimplement base plus distance plus time, and
// again for every future rule, airport fees, tolls, a promotion. As a wrapper it
// multiplies whatever came out of the rule underneath, so it composes with all
// of them and stays three lines forever.
fun PricingStrategy.withSurge(multiplierAt: (Location) -> Double) = PricingStrategy { request ->
    quote(request) * multiplierAt(request.pickup)
}

package com.androidinterview.uber.service

import com.androidinterview.uber.matching.DriverIndex
import com.androidinterview.uber.matching.MatchingStrategy
import com.androidinterview.uber.model.RideRequest
import com.androidinterview.uber.model.Trip
import com.androidinterview.uber.model.TripState
import com.androidinterview.uber.model.driver
import com.androidinterview.uber.pricing.PricingStrategy
import java.time.Clock
import java.time.Duration
import java.util.UUID
import java.util.concurrent.CopyOnWriteArrayList

// One event, several audiences. The observer gets the trip and the state it
// left, so a subscriber that cares about a transition rather than a state can
// be written.
typealias TripObserver = (trip: Trip, from: TripState) -> Unit

// The one class the apps talk to. It sequences the steps and owns nothing that
// varies. Matching policy, pricing and the driver index were all handed to it.
//
// The offer protocol is push and accept. One driver is claimed and asked, and a
// scheduler calls offerTimedOut after OFFER_WINDOW if the driver has not
// answered. The service never sleeps and never owns a timer, so a test can
// drive the whole protocol with plain calls.
class RideService(
    private val index: DriverIndex,
    private val matching: MatchingStrategy,
    private val pricing: PricingStrategy,
    private val clock: Clock,
) {
    private val observers = CopyOnWriteArrayList<TripObserver>()

    fun subscribe(observer: TripObserver) {
        observers += observer
    }

    // Quote once, then offer. The quote is stored on the trip, so a surge that
    // starts while the rider is still deciding cannot change a price they have
    // already seen.
    fun requestRide(request: RideRequest): Trip? {
        val trip = Trip(UUID.randomUUID().toString(), request, pricing.quote(request))
        return if (offer(trip)) trip else null
    }

    // Widen the circle rather than failing at the first empty ring. The claim is
    // the predicate of firstOrNull, so the first driver whose compareAndSet wins
    // is the driver we offer to, and a loser costs nothing but a step down the
    // list. The claim comes first because it is the contested step. If the trip
    // then refuses the offer, the rider cancelled while we were claiming, and
    // the driver goes straight back.
    private fun offer(trip: Trip): Boolean {
        for (radiusKm in SEARCH_RADII_KM) {
            val candidates =
                index.findNearby(trip.request.pickup, radiusKm, trip.request.rideType, clock.instant())
            val claimed = matching(trip.request, candidates)
                .firstOrNull { !trip.hasDeclined(it.id) && it.tryAssignToTrip(trip.id) }
                ?: continue
            if (!trip.offerTo(claimed)) {
                claimed.releaseIfOn(trip.id)
                return false
            }
            publish(trip, TripState.Requested)
            return true
        }
        return false
    }

    // The driver tapped accept. True means they now hold the trip. False means
    // the offer was not theirs or was no longer open, and nothing changed.
    fun acceptOffer(trip: Trip, driverId: String): Boolean {
        val from = trip.accept(driverId) ?: return false
        publish(trip, from)
        return true
    }

    // The window closed without an accept. Withdraw the offer on the trip first
    // and release the driver second. The other order opens a window in which an
    // accept lands on a trip whose driver has already been given away. The
    // withdrawal only succeeds while the offer to this driver is still open, so
    // an accept at fourteen point nine beats a timeout at fifteen.
    //
    // True means a fresh offer went out to somebody else. False means either
    // the driver accepted first, or nobody else is available and the trip is
    // back in Requested for the caller to retry or cancel.
    fun offerTimedOut(trip: Trip, driverId: String): Boolean {
        val from = trip.withdrawOffer(driverId) ?: return false
        from.driver.releaseIfOn(trip.id)
        publish(trip, from)
        return offer(trip)
    }

    fun startTrip(trip: Trip) = publish(trip, trip.start())

    fun completeTrip(trip: Trip) {
        val from = trip.complete()
        from.driver.releaseIfOn(trip.id)
        publish(trip, from)
    }

    // Either side can cancel and the driver goes back in the pool either way.
    // A second cancel throws on the swap before it reaches the release, which
    // is what stops two cancellations freeing the driver twice. Whether a fee
    // is charged is policy, and policy does not belong in the class that moves
    // cars around.
    fun cancelTrip(trip: Trip, reason: String) {
        val from = trip.cancel(reason)
        from.driver?.releaseIfOn(trip.id)
        publish(trip, from)
    }

    private fun publish(trip: Trip, from: TripState) = observers.forEach { it(trip, from) }

    companion object {
        val OFFER_WINDOW: Duration = Duration.ofSeconds(15)
        private val SEARCH_RADII_KM = listOf(2.0, 5.0, 10.0)
    }
}