Design Google Employee Cab Transportation

Google's "Design Google Employee Cab Transportation" is a classic system design interview question focused on backend architecture for routing, scheduling, and optimization of employee shuttle services, often tagged under System Design, Routing, and Scheduling.

Problem Statement

Design a scalable system to manage cab/shuttle transportation for Google employees across multiple offices (e.g., Mountain View campus with 50k+ employees). The system must handle employee ride requests, efficient vehicle routing, dynamic scheduling, and real-time tracking while minimizing wait times, costs, and environmental impact. Key goals include pooling riders into shared cabs for efficiency, handling peak commute hours (e.g., 8-10 AM), and integrating with Google Maps for routing.[2][4]

Functional Requirements

• Employees submit ride requests via app/web with pickup location (e.g., home or office), destination, preferred time, and vehicle type (sedan, van).
• System matches riders into pools (2-8 per cab) based on proximity, timing, and route compatibility.
• Assign cabs/drivers, compute optimal routes, and provide ETAs.
• Real-time updates for delays, cancellations, and location tracking.
• Handle one-way commutes, returns, and ad-hoc requests.[2]

Non-Functional Requirements

• Scale to 100k+ daily requests across global offices.
• Low latency (<2s for matching/ETA).
• 99.99% availability; fault-tolerant.
• Support 10x traffic spikes (e.g., company events).
• Data privacy for employee locations.[6][8]

Constraints

• Scale: 50k employees; 20k daily rides; peak 5k concurrent requests.
• Geographic: Urban areas, 10-50km trips; traffic varies.
• Time: Requests up to 24h in advance; dynamic matching every 30s.
• Capacity: Cabs seat 4-7; max detour 10-15% of direct route.
• Assumptions: No payments (free service); GPS accurate to 10m; 80% rides during commute windows.[4][2]

Input/Output Examples

No official I/O formats exist as it's open-ended, but typical pseudocode examples from prep sites:

Input (Ride Request): { "request_id": "req_123", "employee_id": "emp_456", "pickup": {"lat": 37.4216, "lng": -122.0841}, // Home "destination": {"lat": 37.3894, "lng": -122.0825}, // Office "time_window": "2026-02-02T08:00:00Z ± 15min", "vehicle_prefs": ["sedan", "van"] }

Output (Assignment): { "request_id": "req_123", "cab_id": "cab_789", "driver_id": "drv_101", "route": [ {"stop": 1, "lat": 37.4216, "lng": -122.0841, "eta": "08:05"}, {"stop": 2, "lat": 37.4150, "lng": -122.0800}, // Pool pickup {"stop": 3, "lat": 37.3894, "lng": -122.0825, "eta": "08:20"} // Dropoff ], "eta": "08:20", "cost_estimate": "Free (pooled)" }

Batch Scheduling Input (Daily): Peak rides: 10k from Zone A to HQ; 70% predictable home-office. Constraints: 500 cabs; avg speed 40km/h with traffic.

These are synthesized from common interview mocks; actual interviews emphasize high-level design over rigid I/O.[6][2]