Two Sigma OA Interview Problem: Linear Interpolator

You are asked to implement a linear interpolator. You are given n points on a 2-dimensional coordinate system (known as the knot points).

When these points are sorted by their x coordinates and then connected together using straight lines in that sorting order, they define a piecewise-linear function L(x) known as the linear interpolation.

When x is outside the range of all knot points, L(x) is defined by extrapolation, i.e. extending the straight line connecting its two nearest knot points.

You have to complete a function:

linear_interpolate(n: int, x_knots: List[float], y_knots: List[float], x_input: float) -> float

Here, n represents the number of knot points, while x_knots and y_knots provide the x- and y-coordinates of these knot points, respectively.

Your function should return L(x_input).

If multiple knot points share the same x-coordinate, use the smallest y-coordinate when x_input <= x, and the largest y-coordinate when x_input > x.

Sample Input

n = 5
x_knots = [-2.0, -1.0, 0.0, 1.0, 2.0]
y_knots = [0.0, 10.0, 15.0, 0.0, 5.0]
x_input = -0.3

Sample Output

13.5

Explanation

x_input = -0.3 lies between -1.0 and 0.0. The interpolated value is 13.5.

This Two Sigma OA problem asks you to implement linear interpolation with extrapolation outside the knot range. The key steps are sorting the knot points by x, handling duplicate x-values with the specified tie-breaking rule, selecting the correct segment or boundary pair, and applying the straight-line formula to compute the result.