Katkat
Back

Design nearest-available-taxi lookup with updates

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This question assesses the ability to design a high-concurrency geospatial system that maintains real-time state for moving entities and supports low-latency queries.

Problem Statement

Design a backend service for a ride-sharing platform that allows users to find the 'nearest available taxi' within a given radius. The system must support thousands of updates per second (as taxi drivers report their GPS coordinates) and high-frequency read queries from passengers.

Functional Requirements

  1. UpdateLocation(taxi_id, lat, lon, status): Updates the current position and availability status of a taxi.
  2. FindNearest(user_lat, user_lon, radius): Returns the IDs of all available taxis within the specified radius of the user.

Non-Functional Requirements

  • Scale: Handle 100,000 active taxis and 50,000 requests per second.
  • Latency: FindNearest queries should return results within 100ms.
  • Consistency: Eventual consistency is acceptable, provided the user sees a valid taxi within a reasonable time frame.

Requirements for your Design

  • Propose a data storage schema and the underlying data structures for spatial indexing.
  • Explain how you handle high-frequency write updates versus read latency.
  • Describe a partitioning or sharding strategy for the geospatial data.
  • Discuss how the system handles service failures or node restarts.

Hints

Hint 1

Consider using geohashing or quadtrees to discretize the map into manageable spatial regions.

Hint 2

Decide whether to store taxi state in an in-memory database like Redis with geospatial capabilities versus a persistent relational database.

Hint 3

Think about how sharding the grid cells across multiple servers can distribute the load for both reads and writes.

Follow-up questions

  • How would you modify your design to handle a sudden surge in demand during a major public event?
  • What changes would be necessary if the 'nearest' requirement needs to account for road network distance rather than simple Euclidean (or Haversine) distance?
  • How do you resolve the boundary problem where a taxi is very close to a user but located in an adjacent grid cell?