GPS Recorder: Design a GPS Track Recorder With Compression and Replay
Question Details
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
- How do you compute distance between two GPS coordinates — Haversine formula?
- Describe the Douglas-Peucker algorithm. What is its time complexity?
- If the recorder runs on a mobile device with intermittent connectivity, how do you batch-upload recorded segments?
- How would you detect stops (user stationary for > 2 minutes) within the track?
Full Details
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
- How do you compute distance between two GPS coordinates — Haversine formula?
- Describe the Douglas-Peucker algorithm. What is its time complexity?
- If the recorder runs on a mobile device with intermittent connectivity, how do you batch-upload recorded segments?
- How would you detect stops (user stationary for > 2 minutes) within the track?
About This Question
This is a reported interview question from a axon interview during the phone round.