Practice/Perplexity/Rental Car Surge Area Navigation

Rental Car Surge Area Navigation

CodingMust

Problem Overview

You are building a rental car service API. Given a coordinate (longitude, latitude), you need to determine if it is within a surge pricing area and help users navigate out of it.

The problem is divided into two parts:

• Part 1 (Coding): Implement a navigation algorithm that finds paths to exit surge areas
• Part 2 (Design): Discuss fraud prevention and API abuse scenarios

You are provided with an API function:

def is_in_surge_area(longitude: float, latitude: float) -> bool: """Returns True if the coordinate is within a surge pricing area."""

Your task is to design and implement a function that:

• If inside a surge area: Returns a path (sequence of coordinates) to exit the surge area
• If outside a surge area: Returns a nearby coordinate that is also outside the surge area

Part 1: Path Finding Algorithm

Implement a function that takes a coordinate and returns either a path to exit or a safe point.

Requirements

` def find_exit_or_safe_point( longitude: float, latitude: float, is_in_surge_area: Callable[[float, float], bool] ) -> Union[List[Tuple[float, float]], Tuple[float, float]]: """ Find a path to exit surge area or return a safe coordinate.

Args:
    longitude: Current longitude
    latitude: Current latitude
    is_in_surge_area: API function to check if coordinate is in surge area

Returns:
    - List of coordinates representing path to exit (if currently in surge area)
    - Single coordinate outside surge area (if currently outside)
"""

`

The implementation should:

• Check if the current position is in a surge area
• Use BFS (Breadth-First Search) to explore outward in 8 directions
• Find the shortest path to exit the surge area
• Track visited coordinates to avoid cycles
• Handle floating-point precision issues by rounding coordinates

Example

`

Circular surge area centered at (0, 0) with radius 0.01

def is_in_surge_area(lon, lat): return math.sqrt(lon2 + lat2) < 0.01

Inside surge area - should return path

path = find_exit_or_safe_point(0.0, 0.0, is_in_surge_area)

Returns: [(0.0, 0.0), (0.001, 0.0), (0.002, 0.0), ..., (0.011, 0.0)]

Outside surge area - should return safe point

safe_point = find_exit_or_safe_point(0.05, 0.05, is_in_surge_area)

Returns: (0.05, 0.051) or similar nearby safe coordinate

`

Key Challenges

• Handling arbitrary surge area shapes (circular, rectangular, irregular polygons)
• Finding the shortest path using BFS
• Managing visited coordinates to prevent infinite loops
• Dealing with floating-point precision issues