Design nearby place search and friend discovery

01Choose the nearby-search contract

Build a service that returns the nearest twenty open cafés within a requested radius. A place has coordinates, category, name and reviews; a separate nearby-friends feature returns consenting contacts' recent positions. Exclude driving routes, advertising and reservations. Straight-line distance is not driving time, so the API must name which it returns.

Use a concrete query throughout: Maya stands at local coordinate x=990 and asks for cafés within 50 meters. Café P12 is at x=1010 with the same y coordinate. It is twenty meters away even though a grid boundary at x=1000 separates them. This is the simplest test of whether the search actually works.

Target public-place edits becoming searchable within five seconds for 99% of accepted edits under normal operation. A successful edit means the source record is durable, not that every search replica already contains it. Return a searchable timestamp or generation when useful. For the first page, promise the closest eligible results in the selected searchable snapshot, up to the requested limit. Do not silently widen the radius when fewer than twenty exist. Current private authorization has a stronger requirement than slightly delayed public-place indexing.

Clarify the ranking and audience first: does nearby mean straight-line distance or travel time, and are we searching public places or currently consenting friends? Confirm the maximum radius and acceptable update delay. This answer uses nearest-by-distance place search and a separate permission-checked friend lookup.

02Functional requirements

1. Search nearby places. Return up to twenty open places matching category and radius, ordered by geographic distance with a stable tie-breaker.

2. View place details. Return names, coordinates, review summaries and photo references for selected places.

3. Maintain places. Let authorized owners create and update place records, recover retried writes and reject conflicting edits.

4. Find nearby friends. Accept authenticated position updates and return nearby contacts who currently permit sharing, including the age of each observation.

03Non-functional requirements

These are illustrative interview assumptions, not product facts or measured benchmarks. Confirm them before choosing components, then validate the completed design under the stated workload. Here p95 means the 95th-percentile latency: 95% of measured requests take no longer than that value. Report errors and rejected work alongside latency; a fast failure is not a successful outcome.

1. Workload and response time. Plan for 500 million places and 100,000 peak searches/s. For admitted requests returning at most twenty results within a maximum 5 km radius, target 200 ms p95 API latency; count timeouts as misses and measure dense cities separately.

2. Freshness. Target public-place changes becoming searchable within five seconds for 99% of accepted edits under normal load. Friends publish every five seconds; label points older than fifteen seconds stale and exclude them after thirty seconds.

3. Result correctness. Return the closest eligible results in the selected searchable snapshot. Cover the whole radius; never silently skip a required region or substitute travel time for distance.

4. Recovery and failure behavior. Preserve committed source edits across application restarts and rebuild lost indexes from the source plus changes. If a required search region is unavailable, fail an exact query or explicitly label incomplete coverage; the index is not the only copy of places.

5. Location privacy. Check current sharing permission and presence validity before disclosure. Reject unauthorized edits and omit private positions when their permission cannot be established.

04Start with a spatial database and one complete request

The first implementation needs an API service, a relational database with a spatial index, and object storage for photos. A spatial index organizes records by geometry so the database can discard distant regions without scanning every place. It narrows the candidates; the exact distance predicate determines which candidates are truly within the radius.

For Maya’s search:

1. Send the coordinate, radius and category.

2. Validate units and limits, then ask the database for matching open cafés.

3. Compute geographic distances, sort by distance and place ID, and select up to twenty results. The stable ID breaks equal-distance ties.

4. Fetch review summaries and photo references in batches after selection rather than executing one query per café, then return the selected results.

Use a geography-aware implementation that accepts meters. Raw longitude differences do not have the same ground distance at every latitude. A bounding rectangle can efficiently find candidates, but its corners extend outside a circular search, so a final distance test remains necessary. The mature database implementation handles geometric edge cases; the interview should explain the contract rather than invent spherical mathematics.

An owner edit updates the authoritative place record transactionally. At modest scale the same indexed database can serve both writes and searches, avoiding asynchronous-index complexity entirely.

05Estimate the work per search

Assume 500 million places and 100,000 searches per second at peak. At 800 bytes per place, source records occupy about 400 GB before indexes, replicas, reviews and photos. An index payload consisting only of an 8-byte ID and 16-byte coordinates is 24 bytes, or 12 GB for 500 million places; real index structures require more space.

Twenty results of 1 KB each produce roughly 2 GB/s of response payload at the stated peak. Deliver photos separately through an edge cache. Three copies of source records require about 1.2 TB before overhead; replication is not a backup against an accidental deletion applied to all copies.

The decisive search cost is often candidate count. If a dense-city query examines 5,000 points at an illustrative two microseconds of CPU each, it spends ten milliseconds of CPU before fetching details. At 100,000 such queries per second, that stage alone requires approximately 1,000 CPU-seconds each second. Actual hardware sizing needs measurements, especially because rural and downtown workloads differ greatly.

Measure candidates examined, cells visited and returned records by radius and city. Use the agreed 5 km maximum radius and twenty-result bound; a country-wide best-rated search is a different workload from a local nearest-café request.

06Make units, ownership and freshness visible

Interfaces

Example radius request

GET /places?lat=40.741&lon=-73.989&radiusMeters=50&limit=20

Fields of a version-checked place update

expectedVersion: 4 (the version being replaced)
place fields: the intended changes to the authorized place

Stored records

The cursor binds the original point, radius, filters, ordering and searchable generation. Reusing it after moving the query point would no longer mean “the next page of the same search.” If retaining a snapshot across pages is too expensive, explicitly offer best-effort pagination with possible movement-related changes.

Derive editor and presence-owner identity from authentication. Version checks prevent one editor overwriting another's change. Place creation uses a request identity so retrying a lost response does not create another place. Ratings can be updated less frequently than coordinates if their separate freshness promises are clear. Neither review averages nor spatial membership determine who may see a private location.

07Explain why the search finds the nearest results

A grid assigns each point to a cell. For Maya's 50-meter query, cover every cell intersecting the query region, including the cell beyond x=1000. Then check exact distance and eligibility. Searching only Maya's own cell misses P12 despite its twenty-meter distance.

The simplest correct bounded-radius algorithm collects all eligible candidates in the radius, sorts them and takes twenty. That is a defensible interview baseline. A large candidate set motivates pruning: each unvisited region has a lower bound on how close any point in it could be. Visit promising regions first and retain the best twenty eligible results.

For a two-result example, the first region yields cafés at 30 and 40 meters. A neighboring region can contain a point ten meters away, so inspect it. Finding P12 at twenty changes the best results to twenty and thirty. A remaining region whose closest possible point is 35 meters away cannot improve them. Continue equal-distance bounds when the ID tie-breaker could still matter.

The bounds must never overstate a region’s minimum distance, and must use the same geography and snapshot as its indexed points. Delegating it to a proven spatial implementation is preferable to improvising a custom distributed tree during a 45-minute answer.

08Add read capacity before distributing ownership

First cache place details and add spatial read replicas. Details are repeatedly requested, whereas exact query coordinates vary, so a cache of complete responses may have fewer useful hits. Measure cache hit rate before treating it as the main solution. Replicas add capacity but also introduce update lag and consume index memory.

When one index cannot meet storage or rebuild targets, partition it geographically. A routing manifest maps regions to owners. The query computes all intersecting regions, contacts those owners, merges candidates and deduplicates place IDs. Dense regions can split or receive more replicas. Smaller regions reduce local candidate counts but increase routing and boundary work.

Hashing by place ID offers another tradeoff: records distribute evenly, but a proximity query must ask every index partition. Geographic ownership is attractive when most queries are local; either layout still needs capacity for a popular city.

During a split, copy records and catch up changes before routing new queries exclusively to the replacement owners. Use one consistent version of the region map for each bounded query. If a required owner fails, fail an exact query or label its result incomplete; twenty results from other regions do not establish that no closer result was omitted.

09Move and delete places without claiming instant search

When place storage and the search index are separate, a saved edit can still fail to reach the index. Commit each place change together with an outbox record: a durable instruction describing the change. A worker relays that instruction to the index and retries after failure. The place version lets the index reject an older update delivered after a newer one.

Suppose P12 moves from region A to B as version 5. The worker adds the version-5 entry to B and removes or marks the old entry in A. These may be separate operations. Temporary duplicates can be merged by ID; a temporarily missing new entry means B's queries may omit the café until indexing catches up.

Reading current details can reject the old position but cannot discover a record absent from the candidate list. Therefore the ordinary API retains its stated indexing delay. A strict read-after-edit search must wait for a caught-up index or include a complete set of recent changes before selection. Checking returned records cannot find a café missing from the index.

Keep geometry and distance ranking consistent with the selected searchable snapshot. If current coordinates differ, restart against compatible data or disclose incompleteness rather than substitute them into an old pruning decision. Deletions likewise need versioned removal so delayed events cannot revive a closed place.

10Treat nearby friends as a private presence feature

For a user sharing with a few hundred contacts, begin with a simpler approach: load the authorized contact set, fetch their latest positions in a batch, discard expired observations and compute distances. This avoids maintaining a global private spatial index before the audience size warrants one. Public place search and private presence can share distance utilities without sharing permissions or caches.

Each publishing session receives a generation and sends increasing sequence numbers. The server rejects older generations or sequences, preventing delayed packets from moving a friend back to an old point. A new authenticated session can restart numbering without letting the previous session overwrite it. Keep receipt time separately from the phone's asserted observation time.

As an assumption, devices publish every five seconds, the interface labels observations older than fifteen seconds stale, and records expire after thirty seconds. Those values are product choices, not proof that GPS is accurate. Return location age and avoid displaying a stale point as a live position.

Before returning a private point, read current sharing permission and the corresponding presence version from a consistent authority, or revalidate their versions together. Revocation must affect subsequent authorization decisions even if a candidate remains in an old index. If permission cannot be established, omit the point or fail the private query.

11Test missing results as well as slow requests

Monitor search latency by city and radius, index-update lag, candidates per result, region fanout and rebuild duration. Add synthetic places on cell edges and corners; compare sampled answers with a trusted spatial database. Include antimeridian crossings and coincident points, which can defeat careless custom subdivision.

Recover an index from a source snapshot plus versioned changes. A routing map alone does not contain the places it routes to. Record the snapshot’s change-log position so replay neither skips changes nor restores older values. Limit rebuild bandwidth to protect serving traffic, and verify the new generation before switching queries.

For private presence, test revocation during a request, delayed location packets, device restart and expiry-worker failure. Eligibility must check the deadline even when physical cleanup is delayed. Keep precise coordinates out of general analytics logs and restrict administrative access.

Overload should reduce optional detail fetching or reject excessively expensive queries. Silently skipping a region changes the correctness promise. Public browsing can continue when private presence is unavailable, because the two features have separate state and authorization paths.

12Check the design against its requirements

Use the numbered requirements to check the final design. FR refers to the functional list; NFR refers to the non-functional list. Performance rows specify tests still required, not achieved benchmark results.

13Rapid revision

Remember: A nearby place can cross a cell boundary. Cover the whole radius before choosing the nearest results.

In an interview, spend the opening minutes on radius, ranking, freshness and privacy, then trace Maya's boundary café. Introduce distribution only after showing the correct single-database query. Close with the two residual limits: search can lag accepted edits, and geographic proximity does not establish travel time or access permission.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.