Design UberPool matching with zero Manhattan detour
Company: Applovin
Role: Software Engineer
Category: System Design
Difficulty: hard
Interview Round: Technical Screen
Design a ride-sharing (UberPool-like) system focused on **matching and routing**.
You are operating on a grid where travel distance is **Manhattan distance**:
\(d((x_1,y_1),(x_2,y_2)) = |x_1-x_2| + |y_1-y_2|\).
A driver starts at `S` and wants to go to destination `T`. The driver is willing to pick up additional riders **only if doing so does not increase the driver’s total travel distance**, i.e., the final driven distance must remain exactly \(d(S,T)\).
### Goal
- Serve as many additional riders as possible while respecting the “zero extra Manhattan distance” constraint.
### What to cover
1. Clarify product requirements and constraints.
2. Core APIs (request ride, accept match, updates).
3. High-level architecture and key components.
4. Data model and storage choices.
5. Matching strategy/algorithm under the zero-detour Manhattan constraint.
6. Scalability, latency, consistency, and failure handling.
7. Metrics and edge cases.
Overview: This question evaluates system design and algorithmic reasoning for constrained spatio-temporal matching and routing, covering Manhattan-distance geometry, matching algorithms, API and data model design, and scalability/consistency considerations.