Linear Interpolator
Two Sigma● MediumNEW GRADINTERNFULLTIMEOAProblem statement
You are given n knot points on a two-dimensional coordinate system.
Sort the points by their x-coordinates and connect adjacent points with straight lines. These segments define the piecewise-linear function LI(x). When x is outside the knot range, extrapolate using the two nearest knot points.
Complete linear_interpolate. Arrays x_knots and y_knots contain the coordinates, and the function must return LI(x_input).
For the sample, the knot points are (-2, 0), (-1, 10), (0, 15), (1, 0), and (2, 5). At x_input = -0.3, the result is 13.5.
If multiple knot points have the same x-coordinate x, use the smallest corresponding y when x_input <= x, and use the largest corresponding y when x_input > x. Apply the same tie rule during extrapolation.
Function
linear_interpolate(n: int, x_knots: float[], y_knots: float[], x_input: float) → floatExamples
Example 1
n = 5x_knots = [-2, -1, 0, 1, 2]y_knots = [0, 10, 15, 0, 5]x_input = -0.3return = 13.5The input lies between -1 and 0, so use the segment from (-1, 10) to (0, 15).
Its slope is (15 - 10) / (0 - (-1)) = 5, so LI(-0.3) = 10 + 5 * 0.7 = 13.5. The runnable values were transcribed from the supplied source graph.
Constraints
1 < n <= 100000x_knotsandy_knotshave the same length.