Evaluate Piecewise Linear Function
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given a list of 2D points `[(x1, y1), (x2, y2), ..., (xn, yn)]`, where the points are ordered by strictly increasing `x`, connect each consecutive pair of points with a straight line segment to form a piecewise linear function.
Write a function that returns the function value at a target `x`.
Assumptions:
- `target_x` is guaranteed to lie within the range `[x1, xn]`.
- If `target_x` is exactly equal to one of the input `x` coordinates, return the corresponding `y` value.
- Otherwise, find the segment that contains `target_x` and use linear interpolation to compute the result.
Your function should take:
- `points`: a list of `(x, y)` pairs
- `target_x`: a numeric value
and return:
- the interpolated `y` value at `target_x`
Quick Answer: This question evaluates understanding of piecewise linear interpolation, numerical reasoning, and the ability to handle ordered 2D point data and edge cases such as exact-coordinate matches.
Given points sorted by x, linearly interpolate the y-value at target_x.
Constraints
- points are ordered by strictly increasing x
- target_x is within range
Examples
Input: ([(0, 0), (10, 10)], 5)
Expected Output: 5.0
Explanation: Midpoint interpolation.
Input: ([(0, 2), (3, 8), (5, 8)], 3)
Expected Output: 8
Explanation: Exact point returns its y.
Input: ([(-1, 1), (1, 5)], 0)
Expected Output: 3.0
Explanation: Negative x range.
Input: ([(0, 0), (2, 3), (4, 0)], 3)
Expected Output: 1.5
Explanation: Interior segment.
Hints
- Binary-search the first point with x >= target_x.