Design Uber/Lyft - Ride-Sharing System

public class DriverMatchingService {
    private QuadTree driverQuadTree;
    private RedisCache cache;
    /**
     * Finds the nearest available driver for a ride request.
     * Uses QuadTree for efficient spatial search.
     */
    public Driver findNearestDriver(double lat, double lng, String rideType) {
        // 1. Search within increasing radius until we find drivers
        double[] radiusSteps = {1.0, 2.0, 5.0, 10.0}; // in km
        for (double radius : radiusSteps) {
            List<Driver> nearbyDrivers = driverQuadTree.searchRadius(lat, lng, radius);
            // 2. Filter by availability and vehicle type
            List<Driver> availableDrivers = nearbyDrivers.stream()
                .filter(d -> d.isAvailable())
                .filter(d -> d.getVehicleType().equals(rideType))
                .collect(Collectors.toList());
            if (!availableDrivers.isEmpty()) {
                // 3. Sort by distance and return closest
                return availableDrivers.stream()
                    .min(Comparator.comparingDouble(d ->
                        calculateDistance(lat, lng, d.getLatitude(), d.getLongitude())
                    ))
                    .orElse(null);
            }
        }
        return null; // No drivers found
    }
    /**
     * Calculate distance between two points using Haversine formula.
     */
    private double calculateDistance(double lat1, double lng1,
                                      double lat2, double lng2) {
        double earthRadius = 6371; // km
        double dLat = Math.toRadians(lat2 - lat1);
        double dLng = Math.toRadians(lng2 - lng1);
        double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
                   Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
                   Math.sin(dLng/2) * Math.sin(dLng/2);
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
        return earthRadius * c;
    }
    public static void main(String[] args) {
        DriverMatchingService service = new DriverMatchingService();
        // Example: Find driver near San Francisco
        Driver nearestDriver = service.findNearestDriver(37.7749, -122.4194, "uberX");
        if (nearestDriver != null) {
            System.out.println("Found driver: " + nearestDriver.getName());
        } else {
            System.out.println("No drivers available");
        }
    }
}

public class LocationTrackingService {
    private WebSocketServer wsServer;
    private RedisCache redis;
    private QuadTree driverQuadTree;
    private KafkaProducer kafkaProducer;
    /**
     * Handles incoming location updates from drivers.
     * Updates QuadTree and broadcasts to riders tracking this driver.
     */
    public void handleLocationUpdate(LocationUpdate update) {
        long driverId = update.getDriverId();
        double lat = update.getLatitude();
        double lng = update.getLongitude();
        // 1. Update driver location in Redis (fast cache)
        String cacheKey = "driver:location:" + driverId;
        redis.setWithExpiry(cacheKey, update, 10); // 10 seconds TTL
        // 2. Update QuadTree for spatial queries
        driverQuadTree.updateLocation(driverId, lat, lng);
        // 3. Find all riders tracking this driver (active rides)
        List<Long> trackingRiders = getActiveRidersForDriver(driverId);
        // 4. Broadcast location to tracking riders via WebSocket
        for (Long riderId : trackingRiders) {
            wsServer.sendToClient(riderId, new LocationBroadcast(
                driverId, lat, lng, update.getTimestamp()
            ));
        }
        // 5. Store in Kafka for analytics and trip history
        kafkaProducer.send("location-updates", update);
    }
    /**
     * WebSocket connection handler for riders and drivers.
     */
    public void onClientConnect(WebSocketConnection conn, long userId, String userType) {
        System.out.println(userType + " " + userId + " connected");
        if (userType.equals("driver")) {
            // Start receiving location updates
            conn.onMessage(message -> {
                LocationUpdate update = parseLocationUpdate(message);
                handleLocationUpdate(update);
            });
        } else if (userType.equals("rider")) {
            // Send initial driver location if ride is active
            Ride activeRide = getActiveRide(userId);
            if (activeRide != null && activeRide.getDriverId() != null) {
                String cacheKey = "driver:location:" + activeRide.getDriverId();
                LocationUpdate lastLocation = redis.get(cacheKey);
                if (lastLocation != null) {
                    conn.send(new LocationBroadcast(
                        activeRide.getDriverId(),
                        lastLocation.getLatitude(),
                        lastLocation.getLongitude(),
                        lastLocation.getTimestamp()
                    ));
                }
            }
        }
    }
    private List<Long> getActiveRidersForDriver(long driverId) {
        // Query rides with status 'driver_assigned' or 'in_progress'
        return rideRepository.findActiveRidersByDriver(driverId);
    }
}

public class PricingService {
    private static final double BASE_FARE = 2.50;
    private static final double COST_PER_KM = 1.50;
    private static final double COST_PER_MINUTE = 0.30;
    private static final double MIN_FARE = 5.00;
    /**
     * Calculates fare with surge pricing based on supply-demand ratio.
     */
    public double calculateFare(double distanceKm, int durationMinutes,
                                 double pickupLat, double pickupLng) {
        // 1. Base fare calculation
        double baseFare = BASE_FARE +
                          (distanceKm * COST_PER_KM) +
                          (durationMinutes * COST_PER_MINUTE);
        // 2. Apply minimum fare
        baseFare = Math.max(baseFare, MIN_FARE);
        // 3. Calculate surge multiplier based on demand
        double surgeMultiplier = calculateSurgeMultiplier(pickupLat, pickupLng);
        // 4. Apply surge pricing
        double finalFare = baseFare * surgeMultiplier;
        // 5. Round to 2 decimal places
        return Math.round(finalFare * 100.0) / 100.0;
    }
    /**
     * Calculates surge multiplier based on supply-demand ratio in the area.
     * Returns 1.0 (no surge) to 3.0 (3x surge).
     */
    private double calculateSurgeMultiplier(double lat, double lng) {
        // 1. Get demand: number of ride requests in last 5 minutes
        int demand = getDemandInArea(lat, lng, 5.0); // 5km radius
        // 2. Get supply: number of available drivers in area
        int supply = getAvailableDriversInArea(lat, lng, 5.0);
        // 3. Calculate demand/supply ratio
        if (supply == 0) {
            return 3.0; // Maximum surge if no drivers
        }
        double ratio = (double) demand / supply;
        // 4. Map ratio to surge multiplier
        if (ratio < 1.0) {
            return 1.0; // No surge: more supply than demand
        } else if (ratio < 2.0) {
            return 1.0 + (ratio - 1.0) * 0.5; // 1.0x to 1.5x
        } else if (ratio < 4.0) {
            return 1.5 + (ratio - 2.0) * 0.5; // 1.5x to 2.5x
        } else {
            return Math.min(3.0, 2.5 + (ratio - 4.0) * 0.1); // 2.5x to 3.0x
        }
    }
    /**
     * Gets the number of ride requests in the area in last N minutes.
     */
    private int getDemandInArea(double lat, double lng, double radiusKm) {
        String cacheKey = "demand:" + lat + ":" + lng + ":" + radiusKm;
        Integer cached = redis.get(cacheKey);
        if (cached != null) {
            return cached;
        }
        // Query recent ride requests from database
        int demand = rideRepository.countRecentRequestsInArea(
            lat, lng, radiusKm, 5 // last 5 minutes
        );
        redis.setWithExpiry(cacheKey, demand, 60); // Cache for 1 minute
        return demand;
    }
    /**
     * Gets the number of available drivers in the area.
     */
    private int getAvailableDriversInArea(double lat, double lng, double radiusKm) {
        List<Driver> drivers = driverQuadTree.searchRadius(lat, lng, radiusKm);
        return (int) drivers.stream()
            .filter(Driver::isAvailable)
            .count();
    }
    public static void main(String[] args) {
        PricingService service = new PricingService();
        // Example: 10km trip, 20 minutes, from downtown SF
        double fare = service.calculateFare(10.0, 20, 37.7749, -122.4194);
        System.out.println("Estimated fare: $" + fare);
    }
}