InterviewDB
Experience
Lane Segment: Compute the Segment a Point Belongs to on a Road Lane
Onsite
Interview Experience
Problem
You are given a sequence of 2D waypoints that define a road lane as a polyline. Given a query point P, determine which segment of the polyline it belongs to (i.e., which consecutive pair of waypoints (W[i], W[i+1]) is closest to P), and return the index i.
python
def find_lane_segment(waypoints: list[tuple[float, float]], point: tuple[float, float]) -> int:
# waypoints: [(x0,y0), (x1,y1), ...], len >= 2
**Returns** index i such that segment (waypoints[i], waypoints[i+1]) is closest to point
pass
Example:
waypoints = [(0,0), (10,0), (10,10), (20,10)]
point = (11, 3)
-> 1 # closest to segment (10,0)-(10,10)
point = (5, 2)
-> 0 # closest to segment (0,0)-(10,0)
Follow-ups
- How do you compute the perpendicular (orthogonal) distance from a point to a finite line segment vs. an infinite line?
- What if multiple segments are equidistant? How do you break ties?
- How would you extend this to 3D waypoints for autonomous vehicle path tracking?
- If you need to handle thousands of query points per second, what spatial index structure would you use to speed up segment lookup?
Full Details
Problem
You are given a sequence of 2D waypoints that define a road lane as a polyline. Given a query point P, determine which segment of the polyline it belongs to (i.e., which consecutive pair of waypoints (W[i], W[i+1]) is closest to P), and return the index i.
python
def find_lane_segment(waypoints: list[tuple[float, float]], point: tuple[float, float]) -> int:
# waypoints: [(x0,y0), (x1,y1), ...], len >= 2
**Returns** index i such that segment (waypoints[i], waypoints[i+1]) is closest to point
pass
Example:
waypoints = [(0,0), (10,0), (10,10), (20,10)]
point = (11, 3)
-> 1 # closest to segment (10,0)-(10,10)
point = (5, 2)
-> 0 # closest to segment (0,0)-(10,0)
Follow-ups
- How do you compute the perpendicular (orthogonal) distance from a point to a finite line segment vs. an infinite line?
- What if multiple segments are equidistant? How do you break ties?
- How would you extend this to 3D waypoints for autonomous vehicle path tracking?
- If you need to handle thousands of query points per second, what spatial index structure would you use to speed up segment lookup?
Free preview. Unlock all Applied Intuition questions →
About This Question
This is a candidate experience report from a applied intuition interview during the onsite round.
More Applied Intuition Interview Questions
InterviewDB
Big Data Design: Architect a Scalable Pipeline for Petabyte-Scale Log Processing
InterviewDB
Campsite Booking: Find Available Campsites Given Reservation Intervals
InterviewDB
Applied Intuition SWE Phone - Encode String (Strings/Encoding)
InterviewDB
Applied Intuition SWE Phone - Formula Evaluation (Stack/Parsing)
InterviewDB
Group Coordinates: Cluster 2D Points by Proximity