Practice/Meta/Design a Newsfeed API

Design a Newsfeed API

Product DesignMust

Problem Statement

You've been asked to design the core matching engine for a ride-sharing platform similar to Uber or Lyft. When a passenger requests a ride, the system must quickly identify suitable drivers nearby, rank them based on multiple criteria, and dispatch ride requests in real-time. The system should handle high concurrency as thousands of riders and drivers interact simultaneously across a metropolitan area.

Your design should account for the inherent challenges of a two-sided marketplace: drivers are mobile entities whose locations constantly change, riders expect sub-second matching, and both parties need updates on match status. Consider that major cities may have 10,000+ active drivers and 50,000+ ride requests per hour during peak times.

Key Requirements

Functional

• Real-time driver discovery -- Find available drivers within a configurable search radius of the pickup location
• Intelligent matching -- Rank and select the best driver based on distance, rating, vehicle type, and estimated arrival time
• Concurrent request handling -- Prevent the same driver from receiving multiple simultaneous ride requests
• Match lifecycle management -- Handle driver acceptance, rejection, timeout scenarios, and automatic fallback to next-best drivers
• Location tracking -- Continuously update and query driver positions as they move through the city

Non-Functional

• Latency -- Match riders to drivers within 2-3 seconds; location updates processed within 500ms
• Scalability -- Support 100,000+ concurrent active users per geographic region with horizontal scaling
• Availability -- 99.99% uptime for matching service; graceful degradation during partial failures
• Consistency -- Ensure exactly-once ride assignments; tolerate eventual consistency for non-critical data like driver ratings

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Geospatial Indexing and Query Performance

Efficiently querying nearby drivers is the most critical technical challenge. Naive approaches using latitude/longitude range queries don't scale well and fail to account for Earth's curvature. Your approach to spatial indexing directly impacts both latency and system capacity.

Hints to consider:

• Explore geohashing or S2 geometry for dividing the map into hierarchical cells
• Discuss tradeoffs between precision and query performance when choosing cell sizes
• Consider how to handle boundary cases when riders are near cell edges
• Explain strategies for rebalancing or repartitioning as driver density shifts throughout the day

2. Concurrency Control and Race Conditions

Multiple riders may see the same driver as their closest option simultaneously. Without proper locking mechanisms, you risk double-booking drivers or creating poor user experiences where drivers reject multiple requests.

Hints to consider:

• Compare optimistic locking (version numbers) versus pessimistic locking (distributed locks) for driver state
• Discuss timeout durations and what happens when drivers don't respond within the acceptance window
• Consider using a queue-based approach where drivers can only process one request at a time
• Explain how to handle the "phantom driver" problem where location data is stale

3. Matching Algorithm and Ranking Logic

Simple distance-based matching isn't sufficient for a production system. Interviewers want to see how you balance multiple competing factors and make the algorithm configurable as business needs evolve.

Hints to consider:

• Design a scoring function that weighs distance, ETA, driver rating, acceptance rate, and vehicle type
• Consider surge pricing zones and how to incentivize drivers to move toward high-demand areas
• Discuss machine learning model integration for predicting driver acceptance likelihood
• Explain how to A/B test different matching strategies without disrupting production

4. Real-Time State Management

Driver locations change every few seconds, and the system must maintain an accurate view of who's available, who's on a trip, and who's going offline. This state management challenge becomes complex at scale.

Hints to consider:

• Compare push-based (WebSocket) versus pull-based (polling) location updates from driver apps
• Discuss how to detect and handle offline drivers whose apps crashed or lost connectivity
• Consider using in-memory data stores like Redis for hot driver state versus persistent databases
• Explain strategies for geographic partitioning to reduce cross-region query latency