Practice/Amazon/Design a proximity service

Design a proximity service

Object Oriented DesignMust

Problem

You are building a location-based search engine that helps users discover businesses near their current position. Given a user's geographical coordinates and a collection of businesses with their locations, your task is to identify all businesses within a specified search radius and return them ordered by proximity.

Each business has an identifier, name, and coordinates (latitude and longitude). You need to calculate the distance between the user's location and each business, filter those within the radius, and sort the results by distance in ascending order.

Requirements

1. Accept a list of businesses where each business contains: id, name, latitude, and longitude
2. Accept a query location specified by latitude and longitude coordinates
3. Accept a search radius specified in kilometers
4. Calculate the distance between the query location and each business location
5. Filter businesses to include only those within the specified radius
6. Return results sorted by distance in ascending order (closest first)
7. Include the calculated distance (in kilometers, rounded to 2 decimal places) in the result for each business
8. Handle edge cases such as empty business lists or no businesses within range

Constraints

• Number of businesses: 0 ≤ n ≤ 10,000
• Latitude range: -90.0 to 90.0 degrees
• Longitude range: -180.0 to 180.0 degrees
• Search radius: 0.1 to 100.0 kilometers
• Distance calculations should use the Haversine formula for accuracy
• Results should be sorted by distance with ties broken by business id (lexicographically)

Examples

Example 1:

` Input: businesses = [ {"id": "cafe1", "name": "Java House", "lat": 37.7749, "lon": -122.4194}, {"id": "rest1", "name": "Pasta Palace", "lat": 37.7850, "lon": -122.4094} ] query_lat = 37.7749 query_lon = -122.4194 radius_km = 15.0

Output: [ {"id": "cafe1", "name": "Java House", "lat": 37.7749, "lon": -122.4194, "distance": 0.0}, {"id": "rest1", "name": "Pasta Palace", "lat": 37.7850, "lon": -122.4094, "distance": 1.52} ]

Explanation: The cafe is at the exact query location (distance 0), and the restaurant is approximately 1.52 km away. Both are within the 15 km radius. `

Example 2:

` Input: businesses = [ {"id": "gym1", "name": "Fitness Center", "lat": 40.7128, "lon": -74.0060} ] query_lat = 34.0522 query_lon = -118.2437 radius_km = 5.0

Output: []

Explanation: The gym is over 3,900 km away (New York to Los Angeles), far beyond the 5 km search radius. `

Example 3:

` Input: businesses = [ {"id": "shop1", "name": "Store A", "lat": 51.5074, "lon": -0.1278}, {"id": "shop2", "name": "Store B", "lat": 51.5084, "lon": -0.1268}, {"id": "shop3", "name": "Store C", "lat": 51.5064, "lon": -0.1288} ] query_lat = 51.5074 query_lon = -0.1278 radius_km = 0.5

Output: [ {"id": "shop1", "name": "Store A", "lat": 51.5074, "lon": -0.1278, "distance": 0.0}, {"id": "shop3", "name": "Store C", "lat": 51.5064, "lon": -0.1288, "distance": 0.14}, {"id": "shop2", "name": "Store B", "lat": 51.5084, "lon": -0.1268, "distance": 0.15} ]

Explanation: All three stores are within 0.5 km and are sorted by their distance from the query point. `