Two Sigma OA 面试真题解析：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.

这道 Two Sigma OA 题要求你手写一个线性插值函数：先按 x 坐标排序，再用相邻 knot points 连接成折线；如果查询点 x_input 落在范围外，则用最左边或最右边两点做线性外推。实现时要注意重复 x 坐标的处理规则：当 x_input 小于等于该 x 时取最小 y，当 x_input 大于该 x 时取最大 y。整体思路是先对点排序并按 x 分组，再根据查询位置选出对应的两个端点，最后用斜率公式计算结果。