Compute Piecewise Linear Interpolation
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an unsorted list of distinct 2D points `(x_i, y_i)`. When the points are sorted by `x_i`, connecting adjacent points forms a polyline.
Given a query value `x`, return the corresponding `y` value on this polyline:
- If `x` exactly matches an existing point's x-coordinate, return that point's y-coordinate.
- If `x` lies between two adjacent points, use linear interpolation.
- If `x` is smaller than the minimum x-coordinate, extrapolate using the first two points after sorting.
- If `x` is larger than the maximum x-coordinate, extrapolate using the last two points after sorting.
Design an efficient algorithm. You may assume there are at least two points and all x-coordinates are distinct.
Example:
```text
points = [(0, 0), (10, 20), (20, 10)]
x = 5
output = 10
```
Explanation: `x = 5` lies halfway between `(0, 0)` and `(10, 20)`, so the interpolated y-value is `10`.
Quick Answer: This question evaluates skills in algorithm design and numerical interpolation, including sorting and searching among 2D points, handling boundary cases for extrapolation, and computing linear interpolation accurately and efficiently.
You are given an unsorted list of distinct 2D points `(x_i, y_i)`. If the points are sorted by `x_i` and adjacent points are connected, they form a polyline.
Given a query value `x`, return the corresponding `y` value on this polyline:
- If `x` exactly matches an existing point's x-coordinate, return that point's y-coordinate.
- If `x` lies between two adjacent points, use linear interpolation.
- If `x` is smaller than the minimum x-coordinate, extrapolate using the first two points after sorting.
- If `x` is larger than the maximum x-coordinate, extrapolate using the last two points after sorting.
Design an efficient algorithm. You may assume there are at least two points and all x-coordinates are distinct.
Constraints
- 2 <= len(points) <= 2 * 10^5
- All x-coordinates in `points` are distinct
- `x_i`, `y_i`, and query `x` are numeric values in the range [-10^9, 10^9]
Examples
Input: ([(5, 10), (1, 2), (3, 6)], 5)
Expected Output: 10.0
Explanation: After sorting, the points are (1,2), (3,6), (5,10). Since x = 5 exactly matches an existing point, return its y-value, 10.0.
Input: ([(5, 10), (1, 2), (3, 6)], 4)
Expected Output: 8.0
Explanation: After sorting, x = 4 lies between (3,6) and (5,10). The slope is (10-6)/(5-3) = 2, so y = 6 + 2*(4-3) = 8.0.
Hints
- Sort the points by x-coordinate first; after that, only one segment can contain the query x.
- Use binary search on the sorted x-values to find whether x matches a point or falls between two neighboring points.