Uber Algorithm Interview Preparation

Approach: Implement a greedy matching algorithm with spatial indexing for efficiency. Consider using a min-heap to prioritize matches based on distance/ETA.

Key Considerations:

• Spatial efficiency (using quadtrees or similar for nearest-neighbor queries)
• Real-time constraints (algorithm must complete quickly)
• Fairness to both riders and drivers
• Edge cases like no available drivers or cancellations
• Scalability to handle thousands of concurrent matching operations

Implementation:

class Location {
  constructor(public latitude: number, public longitude: number) {}
  
  // Haversine formula for calculating distance between two points on Earth
  distanceTo(other: Location): number {
    const R = 6371; // Earth's radius in km
    const dLat = this.toRadians(other.latitude - this.latitude);
    const dLon = this.toRadians(other.longitude - this.longitude);
    
    const a = 
      Math.sin(dLat/2) * Math.sin(dLat/2) +
      Math.cos(this.toRadians(this.latitude)) * Math.cos(this.toRadians(other.latitude)) * 
      Math.sin(dLon/2) * Math.sin(dLon/2);
    
    const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
    return R * c; // Distance in km
  }
  
  private toRadians(degrees: number): number {
    return degrees * Math.PI / 180;
  }
}

class Driver {
  constructor(
    public id: string,
    public location: Location,
    public isAvailable: boolean = true
  ) {}
}

class Rider {
  constructor(
    public id: string,
    public location: Location,
    public destination: Location
  ) {}
}

class Match {
  constructor(
    public rider: Rider,
    public driver: Driver,
    public distance: number,
    public estimatedPickupTime: number
  ) {}
}

class RiderDriverMatcher {
  private drivers: Map = new Map();
  
  // Register a driver in the system
  addDriver(driver: Driver): void {
    this.drivers.set(driver.id, driver);
  }
  
  // Update driver's location
  updateDriverLocation(driverId: string, newLocation: Location): void {
    const driver = this.drivers.get(driverId);
    if (driver) {
      driver.location = newLocation;
    }
  }
  
  // Set driver availability
  setDriverAvailability(driverId: string, isAvailable: boolean): void {
    const driver = this.drivers.get(driverId);
    if (driver) {
      driver.isAvailable = isAvailable;
    }
  }
  
  // Find the best match for a rider
  findMatch(rider: Rider, maxDistance: number = 10): Match | null {
    let bestMatch: Match | null = null;
    let shortestDistance = Infinity;
    
    // In a real implementation, we would use a spatial index (quadtree, R-tree)
    // to efficiently find nearby drivers instead of iterating through all drivers
    for (const [_, driver] of this.drivers) {
      if (!driver.isAvailable) continue;
      
      const distance = rider.location.distanceTo(driver.location);
      
      // Skip drivers that are too far away
      if (distance > maxDistance) continue;
      
      // Estimate pickup time (simplified: 2 minutes per km)
      const estimatedPickupTime = distance * 2;
      
      // Find the driver with the shortest distance
      if (distance < shortestDistance) {
        shortestDistance = distance;
        bestMatch = new Match(rider, driver, distance, estimatedPickupTime);
      }
    }
    
    // If we found a match, mark the driver as unavailable
    if (bestMatch) {
      bestMatch.driver.isAvailable = false;
    }
    
    return bestMatch;
  }
  
  // Batch matching algorithm for multiple riders
  batchMatch(riders: Rider[], maxDistance: number = 10): Map {
    const matches = new Map();
    
    // Sort riders by some priority (could be waiting time, VIP status, etc.)
    // For simplicity, we'll just use the order they come in
    
    // For each rider, find the best available driver
    for (const rider of riders) {
      const match = this.findMatch(rider, maxDistance);
      if (match) {
        matches.set(rider.id, match);
      }
    }
    
    return matches;
  }
  
  // Advanced: Optimal matching using Hungarian algorithm
  // This would minimize the total pickup time across all rider-driver pairs
  optimalBatchMatch(riders: Rider[]): Map {
    // Implementation of Hungarian algorithm would go here
    // This is more complex but provides a globally optimal solution
    
    // For the interview, you could discuss the approach and tradeoffs
    return new Map();
  }
}

Key Points to Discuss:

• Time complexity: O(n) for finding a match for one rider where n is the number of drivers (with spatial indexing, this could be reduced to O(log n) or better)
• Space complexity: O(m + n) where m is the number of riders and n is the number of drivers
• Optimizations: Spatial indexing, caching, pre-computation of distances
• Real-world considerations: Traffic patterns, driver preferences, rider ratings
• Scaling: How this would work in a distributed system with millions of users