Linear Interpolator with Extrapolation
Company: Two Sigma
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Linear Interpolator with Extrapolation
You are given `n` knot points in a 2D coordinate system, where `knots[i] = [x_i, y_i]`. All x-coordinates are distinct, but the points are given in no particular order.
After sorting the knots by x-coordinate, connecting each consecutive pair of knots with a straight line segment defines a piecewise linear function `L(x)` — a **linear interpolator** — on the interval `[x_min, x_max]`, where `x_min` and `x_max` are the smallest and largest knot x-coordinates.
Outside that interval, `L(x)` is defined by **linear extrapolation**:
- For `x < x_min`, extend the straight line that passes through the two leftmost knots.
- For `x > x_max`, extend the straight line that passes through the two rightmost knots.
Write a function:
```
interpolate(knots, queries) -> answers
```
that returns an array `answers` of the same length as `queries`, where `answers[j] = L(queries[j])`.
## Example 1
```
Input: knots = [[0, 0], [10, 10], [20, 0]]
queries = [5, 10, 15]
Output: [5.0, 10.0, 5.0]
```
Explanation: The segment from `(0, 0)` to `(10, 10)` has slope 1, so `L(5) = 5`. `x = 10` is exactly a knot, so `L(10) = 10`. The segment from `(10, 10)` to `(20, 0)` has slope -1, so `L(15) = 5`.
## Example 2
```
Input: knots = [[10, 10], [0, 0], [20, 0]]
queries = [-5, 25]
Output: [-5.0, -5.0]
```
Explanation: The knots are unsorted; after sorting by x they are `(0, 0), (10, 10), (20, 0)`. For `x = -5 < x_min = 0`, extrapolate the line through the two leftmost knots `(0, 0)` and `(10, 10)` (slope 1): `L(-5) = -5`. For `x = 25 > x_max = 20`, extrapolate the line through the two rightmost knots `(10, 10)` and `(20, 0)` (slope -1): `L(25) = 0 + (-1) * (25 - 20) = -5`.
## Constraints
- `2 <= n <= 100,000`
- `1 <= len(queries) <= 100,000`
- `-10^9 <= x_i, y_i, queries[j] <= 10^9`, real numbers with at most 6 digits after the decimal point
- All `x_i` are distinct
- A query may fall exactly on a knot, between knots, or outside the knot range
- Answers are accepted within an absolute or relative error of `10^-6`
Your solution should sort the knots once and locate each query's segment efficiently — an `O((n + q) log n)` approach is expected, where `q` is the number of queries.
Overview: This question evaluates understanding of piecewise linear interpolation and extrapolation, numerical robustness with floating-point values, and algorithmic competencies such as sorting and efficient query location for large datasets.
Read the full Two Sigma Quantitative Researcher interview experience this question came from
You are given `n` knot points in a 2D plane, `knots[i] = [x_i, y_i]`, with all x-coordinates distinct and given in no particular order.
After sorting the knots by x-coordinate, connecting each consecutive pair with a straight segment defines a piecewise-linear function `L(x)` on `[x_min, x_max]`. Outside that interval, `L(x)` is defined by linear extrapolation:
- For `x < x_min`, extend the line through the two leftmost knots.
- For `x > x_max`, extend the line through the two rightmost knots.
Implement `solution(knots, queries)` returning an array `answers` where `answers[j] = L(queries[j])`.
Example 1: knots = [[0,0],[10,10],[20,0]], queries = [5,10,15] -> [5.0, 10.0, 5.0].
Example 2 (unsorted): knots = [[10,10],[0,0],[20,0]], queries = [-5,25] -> [-5.0, -5.0].
Sort the knots once and locate each query's segment with binary search for an O((n + q) log n) solution. Answers are accepted within 1e-6 absolute or relative error.
Constraints
- 2 <= n <= 100000
- 1 <= len(queries) <= 100000
- -1e9 <= x_i, y_i, queries[j] <= 1e9 (real, up to 6 decimals)
- All x_i are distinct
- A query may fall on a knot, between knots, or outside the knot range
- Answers accepted within 1e-6 absolute or relative error
Examples
Input: ([[0, 0], [10, 10], [20, 0]], [5, 10, 15])
Expected Output: [5.0, 10.0, 5.0]
Explanation: Segment (0,0)-(10,10) slope 1 gives L(5)=5; x=10 is a knot so L(10)=10; segment (10,10)-(20,0) slope -1 gives L(15)=5.
Input: ([[10, 10], [0, 0], [20, 0]], [-5, 25])
Expected Output: [-5.0, -5.0]
Explanation: Knots sort to (0,0),(10,10),(20,0). x=-5 extrapolates the leftmost line (slope 1): -5. x=25 extrapolates the rightmost line (slope -1): 0 + -1*(25-20) = -5.
Hints
- Sort the knots by x once, then binary-search (bisect) each query to find its enclosing segment.
- For x <= x_min use the two leftmost knots; for x >= x_max use the two rightmost knots. A query exactly on a boundary knot is handled correctly by these same two-knot lines.
- On each chosen segment (x0,y0)-(x1,y1), L(x) = y0 + (y1-y0)/(x1-x0) * (x - x0). The same formula does interpolation and extrapolation.