Evaluate piecewise linear function at x
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a polyline defined by **n** 2D points \((x_i, y_i)\). Connecting consecutive points with straight line segments forms a **piecewise linear function**.
### Task
Given a **target** value `x`, return the corresponding function value `y(x)`:
- If `x` equals some `x_i`, return `y_i`.
- If `x` lies strictly between `x_i` and `x_{i+1}`, linearly interpolate on the segment between \((x_i, y_i)\) and \((x_{i+1}, y_{i+1})\):
\[
y(x)=y_i + (y_{i+1}-y_i)\cdot\frac{x-x_i}{x_{i+1}-x_i}
\]
- If `x < x_0` or `x > x_{n-1}`, return `null` (or a sentinel) because the function is undefined outside the polyline.
### Input
- `points`: list of `n` pairs `(x, y)`
- `x`: target x-coordinate
### Assumptions / Constraints
- `n >= 2`
- Points are given sorted by strictly increasing `x` (i.e., `x0 < x1 < ... < x(n-1)`).
### Output
- A numeric value `y(x)` (float), or `null` if out of range.
Quick Answer: This question evaluates competency in numerical interpolation and handling of piecewise linear functions, including locating the correct segment in a sorted sequence of points and managing out-of-range inputs.
You are given a polyline defined by n 2D points (x_i, y_i). Connecting each consecutive pair of points creates a piecewise linear function. Given a target x-value, return the corresponding y-value on the function.
Rules:
- If x is exactly equal to some x_i, return y_i.
- If x lies strictly between x_i and x_{i+1}, compute the value using linear interpolation:
y(x) = y_i + (y_{i+1} - y_i) * (x - x_i) / (x_{i+1} - x_i)
- If x is outside the range [x_0, x_{n-1}], return None.
In this problem, use None as the sentinel for an undefined value.
Constraints
- 2 <= len(points) <= 100000
- points[i][0] < points[i+1][0] for all valid i
- Each coordinate and the target x is an integer or floating-point number in the range [-10^9, 10^9]
Examples
Input: ([(0, 0), (2, 4), (5, 1)], 2)
Expected Output: 4.0
Explanation: The target x matches an existing point (2, 4), so the answer is 4.0.
Input: ([(0, 0), (10, 10)], 5)
Expected Output: 5.0
Explanation: The target lies halfway between x=0 and x=10 on a line from y=0 to y=10, so the interpolated value is 5.0.
Hints
- Because the x-coordinates are sorted, you can use binary search to find the segment containing the target x.
- Handle the easy cases first: out-of-range values and exact matches to an existing point.