Compute nearest index within threshold after walking distances
Company: Tesla
Role: Machine Learning Engineer
Category: Data Manipulation (SQL/Python)
Difficulty: medium
Interview Round: Technical Screen
You are given:
(
1) points: a list of N 2D coordinates in miles, points[i] = [x_i, y_i], ordered;
(
2) distances: a list of M nonnegative floats (miles); and
(
3) a threshold t > 0 (miles). Starting at points[0], walk along the polyline connecting points[0] -> points[1] -> ... -> points[N-1]. For each step value d in distances, advance exactly d miles along this polyline from the current position, continuing across segments as needed; if the step would pass the final vertex, clamp the position to points[N-1]. After each step, determine whether there exists any index j such that the Euclidean distance between the current position and points[j] is <= t. If such points exist, output the index j of the nearest point (break ties by choosing the smallest index); otherwise output None. Return a list of length M with these results. Implement an efficient NumPy-based solution that handles large N and M (e.g., up to 1e
5), using cumulative segment lengths and within-segment interpolation; avoid naive O(N*M) scanning when possible. Specify time and space complexity and include tests for edge cases (d = 0, repeated points, zero-length segments, empty distances).
Overview: This question evaluates a candidate's proficiency in data manipulation, numerical computing with NumPy, spatial reasoning for Euclidean distance and interpolation along polylines, and designing time- and space-efficient algorithms for large-scale inputs.
You are given two tables:
1) points: an ordered list of 2D coordinates (in miles) that define a polyline.
2) distances: an ordered list of nonnegative step distances (in miles).
The polyline is defined by walking from the smallest point_idx to the largest:
points[0] -> points[1] -> ... -> points[N-1]. Consecutive points are connected by straight-line segments.
You start at points[0]. For each row in the distances table, ordered by step_id, you:
- Move forward along the polyline by exactly step_distance miles from your current position.
- If this movement would go past the final point, clamp your position to the last point in the polyline.
- After moving, compute the Euclidean distance from your current position to every point in the points table.
- If there is at least one point whose distance is less than or equal to a threshold t = 1.5 miles, choose the nearest such point; if there is a tie, choose the smallest point_idx. Otherwise, return NULL for that step.
Write a single SQL query that returns, for each step_id, the index of the nearest point within the threshold or NULL if no point is within 1.5 miles. Use window functions and set-based operations (no procedural loops).
Assume point_idx values are consecutive integers starting at 0 and define the walking order along the polyline.
Tables
points(point_idx INT, x DECIMAL(10,2), y DECIMAL(10,2))
distances(step_id INT, step_distance DECIMAL(10,2))
Hints
- First compute segment lengths and cumulative distances along the polyline using window functions so you can map each cumulative walked distance to a specific segment and an offset within it.
- Interpolate the (x, y) position for each step on the appropriate segment, then cross join to points and use a window function to pick the nearest point within the threshold for each step.