Premium-Zone Escape Path

Given a longitude / latitude coordinate and an API or predicate for whether the coordinate is in a premium rental-car zone, return a path out of the premium area or one coordinate outside it. Problem Statement You are building a system for a rental car service. You have a specific coordinate (longitude and latitude). You need to check if this location is inside a "surge pricing" area (where prices are higher). If it is, you need to help the user navigate out of it. The API provided to you: def is_in_surge_area(longitude: float, latitude: float) -> bool: """Returns True if the coordinate is within a surge pricing area.""" pass Your Goal: Write a function that takes a coordinate and returns: If inside a surge area: A list of coordinates (a path) to leave the area. If outside a surge area: A nearby coordinate that is safe (outside the surge area). Main Challenges: Coding: Write the logic to find the exit path. System Design: Stop users from cheating or attacking the API. Part 1: Coding Challenge Function Requirements You need to write this function: 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) """ pass Solution 1: Breadth-First Search (BFS) This method looks in all directions at once. It expands outward like a ripple in water to find the shortest path to safety. from typing import Callable, List, Tuple, Union, Set from collections import deque import math 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 path to exit surge area using BFS.""" # If already outside, return a nearby safe point if not is_in_surge_area(longitude, latitude): return _find_nearby_safe_point(longitude, latitude, is_in_surge_area) # Otherwise, find path to exit using BFS return _find_exit_path_bfs(longitude, latitude, is_in_surge_area) def _find_nearby_safe_point( lon: float, lat: float, is_in_surge_area: Callable ) -> Tuple[float, float]: """Return a nearby point that's also outside surge area.""" # Simple strategy: try moving slightly north # In a real app, you should check more directions step_size = 0.001 # ~111 meters for direction in [(0, step_size), (step_size, 0), (0, -step_size), (-step_size, 0)]: candidate = (lon + direction[0], lat + direction[1]) if not is_in_surge_area(candidate[0], candidate[1]): return candidate # If everything nearby is bad, just return the starting point return (lon, lat) def _find_exit_path_bfs( start_lon: float, start_lat: float, is_in_surge_area: Callable, max_iterations: int = 1000, step_size: float = 0.001 # ~111 meters per step ) -> List[Tuple[float, float]]: """ Use BFS to find shortest path out of surge area. Plan: - Check 8 directions (N, S, E, W, diagonals) - Remember where we have been to avoid circles - Stop as soon as we find a point outside the area """ # 8 directional movements (lon_delta, lat_delta) directions = [ (0, step_size), # North (0, -step_size), # South (step_size, 0), # East (-step_size, 0), # West (step_size, step_size), # Northeast (step_size, -step_size), # Southeast (-step_size, step_size), # Northwest (-step_size, -step_size), # Southwest ] # BFS queue: (longitude, latitude, path_to_this_point) queue = deque([(start_lon, start_lat, [(start_lon, start_lat)])]) # Track visited coordinates (rounded to avoid math errors) visited = set() visited.add(_round_coord(start_lon, start_lat)) iterations = 0 while queue and iterations < max_iterations: iterations += 1 current_lon, current_lat, path = queue.popleft() # Explore all 8 directions for d_lon, d_lat in directions: new_lon = current_lon + d_lon new_lat = current_lat + d_lat # Check if we've been here before coord_key = _round_coord(new_lon, new_lat) if coord_key in visited: continue visited.add(coord_key) new_path = path + [(new_lon, new_lat)] # Check if we are safe now if not is_in_surge_area(new_lon, new_lat): return new_path # Still in surge area, add to queue to keep searching queue.append((new_lon, new_lat, new_path)) # Fallback: return path with just the starting point # In a real app, you might raise an error here return [(start_lon, start_lat)] def _round_coord(lon: float, lat: float, precision: int = 6) -> Tuple[float, float]: """Round coordinates to avoid floating point comparison issues.""" return (round(lon, precision), round(lat, precision)) Solution 2: Gradient Descent This method guesses the best direction. It assumes there is a boundary and tries to move toward it. def _find_exit_path_gradient( start_lon: float, start_lat: float, is_in_surge_area: Callable, max_steps: int = 100, step_size: float = 0.001 ) -> List[Tuple[float, float]]: """ Use gradient-based approach to find exit. Plan: - Look around in all directions - Move toward the spot that seems "closer" to the edge - Heuristic: Move to spots that have fewer surge neighbors """ path = [(start_lon, start_lat)] current_lon, current_lat = start_lon, start_lat for _ in range(max_steps): # Check if we are out if not is_in_surge_area(current_lon, current_lat): return path # Sample 8 directions and count bad neighbors directions = [ (0, step_size), (0, -step_size), (step_size, 0), (-step_size, 0), (step_size, step_size), (step_size, -step_size), (-step_size, step_size), (-step_size, -step_size), ] best_direction = None min_surge_neighbors = float('inf') for d_lon, d_lat in directions: test_lon = current_lon + d_lon test_lat = current_lat + d_lat # Count how many neighbors of this point are also in surge area surge_count = _count_surge_neighbors( test_lon, test_lat, is_in_surge_area, step_size ) # Pick direction with fewer surge neighbors (closer to edge) if surge_count < min_surge_neighbors: min_surge_neighbors = surge_count best_direction = (d_lon, d_lat) # Move in best direction if best_direction: current_lon += best_direction[0] current_lat += best_direction[1] path.append((current_lon, current_lat)) else: # Stuck, return what we have break return path def _count_surge_neighbors( lon: float, lat: float, is_in_surge_area: Callable, step_size: float ) -> int: """Count how many neighboring points are in surge area.""" directions = [ (0, step_size), (0, -step_size), (step_size, 0), (-step_size, 0), ] count = 0 for d_lon, d_lat in directions: if is_in_surge_area(lon + d_lon, lat + d_lat): count += 1 return count Testing the Code def test_surge_area_navigation(): # Mock surge area: a circle at (0, 0) with size 0.01 def is_in_surge_area_circular(lon: float, lat: float) -> bool: return math.sqrt(lon**2 + lat**2) < 0.01 # Test Case 1: Start inside the area path = find_exit_or_safe_point(0.0, 0.0, is_in_surge_area_circular) assert isinstance(path, list), "Should return a path" assert len(path) > 1, "Path should have multiple points" last_point = path[-1] assert not is_in_surge_area_circular(last_point[0], last_point[1]), \ "Last point should be outside surge area" print(f"✓ Test 1 passed: Found path with {len(path)} steps") # Test Case 2: Start outside the area result = find_exit_or_safe_point(0.05, 0.05, is_in_surge_area_circular) assert isinstance(result, tuple), "Should return a single coordinate" assert not is_in_surge_area_circular(result[0], result[1]), \ "Result should be outside surge area" print(f"✓ Test 2 passed: Returned safe point {result}") # Test Case 3: A rectangular area def is_in_surge_area_polygon(lon: float, lat: float) -> bool: # Simple rectangle: -0.01 <= lon <= 0.01, -0.01 <= lat <= 0.01 return -0.01 <= lon <= 0.01 and -0.01 <= lat <= 0.01 path = find_exit_or_safe_point(0.0, 0.0, is_in_surge_area_polygon) assert len(path) > 0, "Should return a path" last_point = path[-1] assert not is_in_surge_area_polygon(last_point[0], last_point[1]), \ "Should exit rectangle" print(f"✓ Test 3 passed: Exited polygon surge area") # test_surge_area_navigation() Part 2: System Design - Security & Fraud Security Risks When you put this system online, you need to worry about: API Abuse: Users calling the API thousands of times to draw a map of your prices. Fraud: Users trying to dodge fair prices. Gaming the System: Finding the exact inch where the surge pricing stops. Cost: Too many calls cost you money. Prevention Strategies 1. Limiting Requests (Rate Limiting) The Problem: Users spam the API to map your data. The Solution: Token Bucket Algorithm: Give users a "budget" of requests per minute. Example: 10 requests per minute max. Allow a small burst (like 5 requests at once). Multi-layer Limits: Limit by User ID (for logged-in users). Limit by IP address (for guests). Limit by Device ID (to catch bots). Trade-offs: Too strict: Normal users get annoyed. Too loose: Hackers steal your data. Tip: Start with 10 requests/minute. Implementation: Use Redis to count requests. Send a 429 Too Many Requests error when they hit the limit. 2. Pricing Models The Problem: If it's free and unlimited, people will abuse it. The Solution: Freemium: First 5 requests/day are free. Charge money for requests after that. Subscriptions: Basic users get limited access. Premium users get more access. Trade-offs: Might scare away new users. Requires a payment system. 3. Hiding Exact Details (Obfuscation) The Problem: If you give an exact path, hackers can find the exact surge boundary. The Solution: Simplify the Path: Don't show every step. Just show 5-10 key points. Round Coordinates: Round numbers to the nearest 100 meters. Add Noise: Add a tiny random number to the coordinates (±50m). Use Text: Say "Head North" instead of giving a coordinate. Example: Bad (Too precise): [(37.7749, -122.4194), (37.7750, -122.4193)...] Good (Safer): Direction: "Head northeast for 0.5km" Trade-offs: Less accurate means harder for users to navigate. More accurate means easier to cheat. 4. Detecting Weird Behavior The Problem: Smart hackers can trick simple limits. What to look for: Pattern Description Action Grid Scanning Checking points in a perfect square grid Block the account Teleporting User jumps between distant cities instantly Block temporarily Repeated Checks Checking the same spot 50 times Send cached data Bot Timing Requests happen exactly every 2 seconds Limit them more Machine Learning: Train a model to spot fake users vs real users. Give users a "Risk Score" (0 to 100). If the score is high, block them. 5. Checking Location Rules: Distance Check: You can only check prices near where you actually are (e.g., within 10km). This stops someone in New York from mapping prices in London. Speed Check: If you were in location A 1 minute ago, you can't be 50km away now. Surge Times: Be stricter when prices are high. Normal time: 10 requests/min. Surge time: 3 requests/min. 6. Traps (Honeypots) The Idea: Let attackers hack a fake system to catch them. Tactics: Fake Surge Areas: Put invisible surge areas on the map. If someone finds them, they are a bot. Slow Responses: If a user looks suspicious, make the API reply slowly. This breaks their scraping scripts. High-Level Architecture ┌─────────────┐ │ Client │ │ (Mobile) │ └──────┬──────┘ │ ▼ ┌──────────────────────┐ │ Load Balancer │ │ (AWS ALB/NLB) │ └──────────┬───────────┘ │ ┌──────────────────────┼──────────────────────┐ ▼ ▼ ▼ ┌───────────────┐ ┌───────────────┐ ┌───────────────┐ │ API Gateway │ │ API Gateway │ │ API Gateway │ │ Instance 1 │ │ Instance 2 │ │ Instance 3 │ └───────┬───────┘ └───────┬───────┘ └────────┬──────┘ │ │ │ └──────────────────────┼──────────────────────┘ ▼ ┌──────────────────────────────┐ │ Request Processing Layer │ ├──────────────────────────────┤ │ • Authentication (JWT) │ │ • Rate Limiting (Redis) │ │ • Input Validation │ │ • Location Verification │ └──────────┬───────────────────┘ │ ┌──────────────────┼──────────────────┐ ▼ ▼ ▼ ┌──────────────┐ ┌─────────────────┐ ┌──────────────┐ │ Fraud │ │ Path Finding │ │ Surge │ │ Detection │ │ Service │ │ Service │ │ │ │ │ │ │ │ • Pattern │ │ • BFS Algorithm │ │ • Polygon │ │ Analysis │ │ • Caching │ │ Check │ │ • ML Models │ │ • Obfuscation │ │ • Real-time │ │ • Risk Score │ │ │ │ Updates │ └──────┬───────┘ └────────┬────────┘ └───────┬──────┘ │ │ │ └───────────────────┼───────────────────┘ ▼ ┌───────────────────────┐ │ Data Layer │ ├───────────────────────┤ │ • Redis (Cache) │ │ • PostgreSQL (Users) │ │ • TimescaleDB (Logs) │ │ • S3 (Surge Maps) │ └───────────────────────┘ ┌─────────────────────────────────────┐ │ Analytics & Monitoring │ ├─────────────────────────────────────┤ │ • Kafka (Event Stream) │ │ • Spark (Batch Analysis) │ │ • Grafana (Dashboards) │ │ • PagerDuty (Alerts) │ └─────────────────────────────────────┘ How Data Moves Client sends a request with location and user ID. Load Balancer sends it to an API Gateway. Gateway checks if the user is logged in and hasn't hit the rate limit (checks Redis). Fraud Detection gives the request a risk score. If safe, Path Finding Service runs: Check cache (did we already solve this?). If not, run the BFS code. Simplify/Obfuscate the result. Save to cache for 5-10 minutes. Send the safe path back to the client. Scaling the System Adding Power (Horizontal Scaling): API Gateways: You can add hundreds of these easily. Path Finding: This uses a lot of CPU, so add more servers as traffic grows. Saving Results (Caching): L1 Cache (Memory): Quickest access on the server itself. L2 Cache (Redis): Shared memory for all servers. Expire data every 5-10 minutes because surge areas change. Pre-calculating: Calculate paths for popular spots before users even ask. Tracking System Health What to measure: Requests per second. Cache hit ratio (Aim for >80%). How long it takes to calculate a path. Error rates. Alerts: If one user makes a sudden spike of requests. If the cache hit ratio drops (means surge areas changed significantly). If path calculation gets slow. Big O Analysis Time Complexity BFS Approach: Best Case: O(k)O(k)O(k) — We find the exit immediately. Worst Case: O(n×m)O(n \times m)O(n×m) — We have to search the whole area. nnn is the radius, mmm is the 8 directions. Typical: O(d×8)O(d \times 8)O(d×8) — Depends on distance ddd to the edge. Gradient Approach: Best Case: O(d)O(d)O(d) — Walks straight to the edge. Worst Case: O(max_steps)O(max_steps)O(max_steps) — Gets stuck. Comparison: Faster than BFS for simple shapes. Space Complexity BFS Approach: O(n)O(n)O(n) — The queue can get big if the area is large. Gradient Approach: O(1)O(1)O(1) — Uses almost no memory. Pros and Cons 1. Accuracy vs. Speed BFS (Accurate): ✅ Finds the absolute best path. ❌ Slower and uses more CPU. Gradient (Fast): ✅ Very fast. ❌ Might fail on weirdly shaped areas (like a crescent moon shape). Advice: Use BFS in production, but use caching to make it fast. 2. Security vs. User Experience More Hiding (Obfuscation): ✅ Safer against hackers. ❌ Harder for real users to follow. Less Hiding: ✅ Great for users. ❌ Easy to cheat. Advice: Use simple paths (less hiding) but rely on strict rate limits to stop hackers. Common Mistakes Coding Mistakes: Infinite Loops: Forgetting to track where you've been. Fix: Use a visited set and a max loop limit. Math Errors: Computers are bad at decimals (0.1 + 0.2 != 0.3). Fix: Round numbers before checking if you've visited them. Edge Cases: What if the user is already safe? What if there is no way out? Design Mistakes: Forgetting Security: Adding security later is very hard. Do it first. Too Much Hiding: Making the map so blurry that users can't use it. Ignoring Costs: If 1 million users call your BFS function, your server bills will be huge. Use caching! Stale Data: Surge areas change fast. Don't cache data for too long (keep it under 10 mins). Interview Follow-Up Questions Coding Questions: How would you make it faster? Use caching. Run searches in parallel. What if the surge area is huge? Increase the step size (jump 1km instead of 100m). Use the A* algorithm (it's smarter than BFS). What if the area has a weird shape (like a U-shape)? Gradient descent will get stuck. BFS handles this better. System Design Questions: How would you handle millions of users? Use Load Balancers and a Redis Cluster. How do you catch smart bots? Use Machine Learning to analyze patterns. How do you balance privacy? Don't store exact user locations for long. Round the data.