Applovin·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

May 2026

Summary

System design round at Applovin where the whole thing was basically a deep dive into Uber Pool. Lots of moving parts and the matching algorithm piece got pretty hairy toward the end.

Questions Asked (1)

Design the Uber Pool feature with the goal of maximizing passengers picked up per ride, without increasing the detour distance for existing passengers. Cover request matching, driver dispatch, route updates, ETA calculations, and matching algorithm trade-offs at scale.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This one is deceptively wide.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the core constraint: no increase in detour for existing passengers, which means new pickups must fit within the current route's slack. Then design a system that matches ride requests to existing trips using a spatial-temporal index, dispatches drivers with minimal added distance, and updates routes and ETAs in real time. Finally, discuss trade-offs between matching optimality and scalability, such as greedy vs. batch matching and the use of geohashing or graph partitioning.

Pro tip: Emphasize that the 'no detour' constraint is a hard filter, not a soft penalty—this simplifies the matching problem and avoids complex multi-objective optimization. Also, mention that in practice, you'd use a combination of precomputed routes and dynamic re-optimization to balance latency and optimality.

1. Clarify Requirements and Constraints

Confirm the goal: maximize passengers per ride while ensuring zero additional detour for existing passengers. Define metrics like pickup rate, detour tolerance, and system scale (e.g., requests per second, city size).

2. Design Request Matching and Driver Dispatch

Use a spatial index (e.g., geohash, Quadtree) to find nearby drivers and passengers. Match new requests to existing trips only if the pickup and drop-off points lie on or very close to the current route without increasing its length.

3. Handle Route Updates and ETA Calculations

When a match is found, update the route by inserting the new pickup/drop-off at the optimal position (e.g., using insertion heuristics). Recalculate ETAs for all passengers using real-time traffic data and inform them of any changes (though detour is zero, ETAs may shift slightly due to added stops).

4. Discuss Matching Algorithm Trade-offs at Scale

Compare greedy (match immediately) vs. batch (wait and match multiple) approaches. Greedy is low-latency but suboptimal; batch improves matching quality but adds delay. Consider distributed matching using consistent hashing or graph partitioning to scale across cities.

5. Address Failure and Edge Cases

Handle cases like no available matches, driver cancellations, or sudden traffic changes. Ensure the system can gracefully fall back to solo rides or re-route without violating the no-detour constraint.

Key Points to Mention

Spatial indexing (geohash, Quadtree) for efficient nearest-neighbor search of drivers and passengers.
Route insertion algorithms (e.g., cheapest insertion) that respect the no-detour constraint by checking if new stops lie on the existing path.
Real-time ETA calculation using traffic APIs and historical data, with incremental updates to avoid full recomputation.
Trade-offs between greedy matching (low latency, suboptimal) and batch matching (higher latency, better utilization).
Scalability techniques: sharding by city/region, using message queues for asynchronous matching, and caching frequent routes.
Monitoring and metrics: pickup rate, average detour (should be zero), matching latency, and system throughput.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.