Katkat
Back

Design Nearby Search for Autonomous Vehicles

ZooxSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

Design a real-time geospatial search and filtering system for an autonomous vehicle fleet. The service must index streaming vehicle telemetry, handle out-of-order updates, and query nearby eligible vehicles with strict latency bounds.

Scenario

An autonomous mobility service operates a large-scale fleet of robotaxis in several metropolitan regions. Dispatch engines, remote assistance operators, and routing coordinators need to query the fleet to identify nearby vehicles matching specific operational criteria (e.g., passenger capacity, battery state of charge, hardware health, autonomous driving readiness, or cleaning status).

Design a Nearby Vehicle Search Service that continuously ingests real-time telemetry from moving autonomous vehicles and serves low-latency geospatial queries filtered by vehicle eligibility.

Requirements

Functional Requirements

  • Telemetry Ingestion: Ingest location updates (latitude, longitude, heading, speed, timestamp) and operational state (battery level, vehicle status, passenger occupancy, hardware faults) from the fleet at 1–2 second intervals per vehicle.
  • Nearby Query: Support search queries specifying a center coordinate, search radius (e.g., up to 5 km), maximum result count k, and filtering predicates (e.g., status == IDLE, battery_level >= 30%, wheelchair_accessible == true).
  • Staleness Tracking: Return freshness metadata with each vehicle match (e.g., last update timestamp, estimated location confidence) and drop or flag vehicles whose telemetry is older than a configurable threshold (e.g., > 10 seconds).
  • Out-of-Order Handling: Reliably discard or reconcile delayed or out-of-order telemetry packets caused by cellular network variability without corrupting vehicle state.

Non-Functional Requirements

  • Scale: 50,000 active autonomous vehicles globally, with up to 10,000 vehicles concentrated in a single dense urban area.
  • Throughput: Ingestion rate of ~50,000 updates/sec; query rate of ~5,000 queries/sec.
  • Latency: Query p95 response time < 30 ms; telemetry propagation delay (event generation to searchable index) < 500 ms.
  • Availability & Consistency: 99.99% availability for queries. Eventual consistency is acceptable for spatial index propagation, but vehicle update monotonically increasing timestamps must prevent regression.
  • Privacy & Security: Telemetry and passenger presence must be protected with role-based access control (RBAC), and internal identifiers must be masked where appropriate.

What Your Design Should Cover

  1. API Design: Endpoints for streaming telemetry ingestion and querying nearby eligible vehicles.
  2. Geospatial Indexing & Storage: In-memory geospatial indexing strategies (e.g., S2, H3, QuadTree, or geohash-partitioned Redis) versus long-term persistence.
  3. Architecture: End-to-end data pipeline from vehicle telemetry gateways to the query serving layer.
  4. Edge Cases & Resilience: Handling hot spots (e.g., airport pickup queues), cellular connection drops, node failover, and network partitions.

Hints

Hint 1

Consider using discrete global grid systems like Uber H3 or Google S2 to map coordinates into cell IDs, allowing multi-attribute filtering via in-memory inverted indices or key-value stores.

Hint 2

To handle out-of-order or late telemetry packets, store a monotonic sequence number or high-resolution GPS timestamp per vehicle and reject updates with timestamps older than the last-applied state.

Hint 3

For dense hotspots, pre-aggregate cell density or partition queries by cell ID rather than broadcasting bounding box queries to avoid hot-partition bottlenecks.

Follow-up questions

  • How would you evolve this service to rank vehicles by estimated road-network arrival time (ETA) rather than straight-line Euclidean or Haversine distance without blowing up latency?
  • If a vehicle loses cellular coverage inside a tunnel for 45 seconds, how should the service represent the vehicle's position and eligibility to dispatchers during that window?
  • How would you ensure zero downtime and minimal index rebuild latency if a spatial indexing node crashes under peak load?