Design UberPool matching with zero Manhattan detour

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.