Axon Software Engineer Phone Screen Questions

The interviewer was Chinese. We started by discussing the information on my resume and asking some basic technical questions. Then came a data structure design question, similar to one from LeetCode's

## Problem Build a `GPSRecorder` that records a sequence of GPS coordinates `(lat, lon, timestamp)` during a trip. Implement: (1) recording with deduplication (skip a point if it is within 5 meters of the previous one), (2) Douglas-Peucker simplification to compress the track to at most `N` points while preserving shape, and (3) replay at a given speed multiplier. ```python class GPSRecorder: def record(self, lat: float, lon: float, timestamp: int) -> None: ... def compress(self, max_points: int) -> list[tuple]: ... def replay(self, speed: float) -> Iterator[tuple]: ... # yields (lat, lon, adjusted_timestamp) in real-time scaled by speed ``` **Example:** ``` recorder.record(43.651, -79.347, 0) recorder.record(43.651, -79.347, 5) # skipped, same location recorder.record(43.652, -79.348, 10) recorder.compress(max_points=100) # returns simplified track ``` ## Follow-ups 1. How do you compute distance between two GPS coordinates — Haversine formula? 2. Describe the Douglas-Peucker algorithm. What is its time complexity? 3. If the recorder runs on a mobile device with intermittent connectivity, how do you batch-upload recorded segments? 4. How would you detect stops (user stationary for > 2 minutes) within the track?

## Problem You have a `locations` table storing points of interest with latitude and longitude. Write queries to: (1) find all locations within 10 km of a given point, (2) return the 5 nearest locations to a given point, and (3) for each user in a `users` table, find the nearest location of each category. ```sql -- Schema locations(location_id, name, category, lat FLOAT, lon FLOAT) users(user_id, home_lat FLOAT, home_lon FLOAT) ``` **Distance approximation (flat-earth for small areas):** ```sql -- distance_km ~= sqrt(power((lat2-lat1)*111, 2) + power((lon2-lon1)*111*cos(radians(lat1)), 2)) ``` **Example:** ```sql -- Q1: Locations within 10km of (43.65, -79.38) SELECT name, category, sqrt(power((lat-43.65)*111,2) + power((lon+79.38)*111*cos(radians(43.65)),2)) AS dist_km FROM locations HAVING dist_km < 10 ORDER BY dist_km; ``` ## Follow-ups 1. What is wrong with using a distance function in WHERE vs. HAVING? Does it affect index usage? 2. How do PostGIS extensions change this query — what index type does it use? 3. For Q3 (nearest per user per category), write the SQL using LATERAL JOIN or ROW_NUMBER(). 4. At 50M locations globally, how do you avoid a full table scan for every proximity query?

## Problem A security guard must patrol `n` zones connected by corridors (a weighted undirected graph). Each zone must be visited at least once. The guard starts at zone 0. Find the minimum total travel time to visit all zones and optionally return to the start. ```python def min_patrol_time( n: int, edges: list[tuple[int, int, int]], # (zone_a, zone_b, travel_time) return_to_start: bool ) -> int: pass ``` **Example:** ``` n=4, edges=[(0,1,2),(1,2,3),(2,3,1),(0,3,8)], return_to_start=False # Optimal path: 0->1->2->3, total time = 2+3+1 = 6 Output: 6 ``` ## Approach For small `n` (n <= 20): bitmask DP on visited set. `dp[mask][v]` = min time to have visited exactly the zones in `mask`, ending at zone `v`. Precompute all-pairs shortest paths with Floyd-Warshall. ## Follow-ups 1. What is the time complexity of the bitmask DP solution? What is the limit on `n`? 2. How does precomputing all-pairs shortest paths simplify the DP transitions? 3. If some zones have mandatory visit windows (must arrive between time `a` and `b`), how does the state space change? 4. For large `n` where exact DP is infeasible, what approximation algorithms exist for TSP-like problems?

## Round 1 - Coding ## Problem You are given a list of events. Each event is either `"START"` or `"END"`. A trip begins on a `START` event and ends on the next `END` event. Implement a `TripCounter` class that processes events one at a time and returns the number of completed trips at any point. ```python class TripCounter: def __init__(self): pass def process(self, event: str) -> int: # Returns total completed trips after processing this event pass def active_trips(self) -> int: # Returns number of currently open (unfinished) trips pass ``` ## Example ``` events = ["START", "START", "END", "END", "START", "END"] After "START" -> completed=0, active=1 After "START" -> completed=0, active=2 After "END" -> completed=1, active=1 After "END" -> completed=2, active=0 After "START" -> completed=2, active=1 After "END" -> completed=3, active=0 ``` ## Follow-ups 1. What if events include a trip ID and you need to match START/END by ID? How does your data structure change? 2. How would you handle an `END` event with no matching `START`? Should it throw, return -1, or be silently ignored? 3. If trips have timestamps, how do you compute average trip duration? 4. At scale (millions of events/sec), how would you process this in a distributed stream?