Katkat
Back

Design a Geolocation Search Service

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This question tests your ability to design a scalable spatial indexing system capable of performing range-based queries (e.g., 'find all points of interest within 5km') while maintaining high availability and low latency.

Problem Statement

Design a service that allows users to query for nearby Points of Interest (POIs) based on their current geographic coordinates (latitude, longitude). The system must support millions of POIs globally and handle a high volume of read requests.

Requirements

  • Functional:
    • Users can search for POIs within a specified radius (e.g., 5km) of a given location.
    • The service should return a list of POI names and their exact coordinates.
  • Non-functional:
    • Low latency for search queries (sub-100ms).
    • High availability.
    • The dataset is relatively static (POIs change infrequently).

Scale Assumptions

  • Total POIs: 10 million.
  • Daily Active Users: 1 million.
  • Read/Write Ratio: 1000:1.

What to Cover

  1. Data Model: How will you store latitude and longitude, and what indexing strategy will you use to make spatial queries efficient?
  2. API Design: Define the endpoint for a proximity search.
  3. Architecture: Describe the high-level components (load balancer, app servers, cache, database).
  4. Trade-offs: Discuss the pros and cons of your chosen approach (e.g., Geohashing vs. Quadtrees vs. PostGIS).

Hints

Hint 1

Consider how a simple database scan would perform for 10 million rows and why a spatial index is necessary.

Hint 2

Look into spatial hashing techniques like Geohashing, which convert 2D coordinates into a 1D string, allowing for prefix-based searches.

Hint 3

Evaluate whether to use a specialized database (like PostGIS with PostgreSQL) or build a custom indexing layer using a distributed cache (like Redis) with sorted sets.

Follow-up questions

  • How would you handle POIs that are clustered very densely in a single city versus sparse rural areas?
  • If you decide to use Geohashes, how do you handle search boundaries that span across the edge of a Geohash cell?
  • How would you implement a ranking system to prioritize POIs by popularity or user rating within the search results?