Design Food-Delivery Proximity Search for Restaurants Within 10 km

Design a proximity search system for a food-delivery app: given a customer's location, find the restaurants within a 10 km radius. Expect several follow-up questions on your design. Before the interview ends, you will also hand-write the code for part of the design you proposed. ### Clarifying Questions - Is the 10 km radius a straight-line distance, or should it reflect road distance or travel time? - How should results be ordered, and how many are returned per request? - Besides distance, which filters apply, for example whether a restaurant is currently accepting orders? - Roughly how many restaurants and how many searches per second, and in which regions? - How quickly must a new, moved or closed restaurant be reflected in search results? ### Part 1 — Design the proximity search service Design the service end to end: how restaurant locations are stored and indexed, how a search request finds and ranks nearby restaurants, how changes to restaurants reach the index, and how the system scales and survives failures. ```hint Avoid measuring every distance Think about how to discard most restaurants cheaply before computing any exact distance. ``` ```hint Separate slow-changing from fast-changing data Consider which restaurant attributes are nearly static and which change during the day, and whether they belong in the same store. ``` #### What This Part Should Cover - A geospatial indexing scheme and why it suits a fixed 10 km radius - The read path from a customer location to ranked results, and the write path for restaurant changes - Storage, partitioning by geography, replication and caching - Handling of dense and sparse areas and of region boundaries ### Part 2 — Hand-write the core of the design Write the code for the heart of your design: an index that supports adding, moving and removing a restaurant, and that returns the restaurants within a given radius of a point, nearest first. Use any language, and state the distance formula you rely on. ```hint Size the buckets to the radius Relate the size of your index buckets to the 10 km radius so that one query touches only a few buckets. ``` ```hint Test the edges of the map Try points at high latitudes and near longitude 180, where simple coordinate arithmetic tends to break. ``` #### What This Part Should Cover - Bucketing that never misses a restaurant inside the radius - An exact distance check after the coarse filter, and nearest-first ordering - Updates that keep the index consistent when a restaurant moves or is removed - The time complexity of insert, update and query ### What a Strong Answer Covers - Requirements and scale pinned down before an index is chosen - A read-optimized design with a justified choice among grid or geohash cells, a quadtree, or a database geospatial index - A clean separation between the geographic filter and ranking or business filters - Freshness of restaurant data, failure handling and observability - Working code that matches the design ### Follow-up Questions - A dense downtown area puts thousands of restaurants inside the radius. How do you keep latency low and results useful? - How would the design change if each restaurant had its own delivery radius instead of a fixed 10 km? - How would you move from straight-line distance to estimated travel time without slowing every query? - How do you split the index across machines, and what happens to a query near a partition boundary?