Nearest Lane Segment Algorithm | Dataford Interview Questions

Given a set of 2D coordinates representing GPS waypoints, write an algorithm to find the nearest lane segment in a vectorized map.

Implement nearest_lane_segments(waypoints, lane_segments). Each waypoint is [x, y], each lane segment is [[x1, y1], [x2, y2]], and the result must contain the zero-based index of the closest segment for every waypoint. Use squared Euclidean distance, handle zero-length segments, and return the lowest segment index when distances tie.

Constraints

1 <= len(waypoints) <= 5000
1 <= len(lane_segments) <= 5000
Each waypoint contains exactly two finite numeric coordinates
Each segment contains exactly two endpoints, each with two finite numeric coordinates
If multiple segments have the same minimum distance, return the smallest index

Function Signature

def nearest_lane_segments(waypoints, lane_segments):

Your question is Nearest Lane Segment Algorithm. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Given a set of 2D coordinates representing GPS waypoints, write an algorithm to find the nearest lane segment in a vectorized map.

Constraints

1 <= len(waypoints) <= 5000
1 <= len(lane_segments) <= 5000
Each waypoint contains exactly two finite numeric coordinates
Each segment contains exactly two endpoints, each with two finite numeric coordinates
If multiple segments have the same minimum distance, return the smallest index

Function Signature

def nearest_lane_segments(waypoints, lane_segments):

Your question is Nearest Lane Segment Algorithm. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.