FastPrep
Problem · Array

Linear Interpolator

Learn this problem
● MediumTwo SigmaOA

Problem statement

You are asked to implement a linear interpolator. Namely, 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 their sorting order, they define a piecewise-linear function LI(x) known as the linear interpolation.

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

Complete the function linear_interpolate. 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 LI(x_input).

Below is a graph of this calculation for the sample case.

xy
-0.313.5(-2, 0)(-1, 10)(0, 15)(1, 0)(2, 5)
Blue: knot points
Orange: linear interpolation
x_input: -0.3
output: 13.5

In case multiple knot points share the same x-coordinate x, when x_input <= x, break the tie by using the smallest y-coordinate among those points. When x_input > x, break the tie by using the largest y-coordinate among those points.

You should follow the same logic in the case of extrapolation. When x_input < x, use the smallest y-coordinate among those points; when x_input > x, use the largest y-coordinate among those points.

Function

linear_interpolate(n: int, x_knots: float[], y_knots: float[], x_input: float) → float

Examples

Example 1

n = 5x_knots = [-2, -1, 0, 1, 2]y_knots = [0, 10, 15, 0, 5]x_input = -0.3return = 13.5

The sample graph has knot points (-2, 0), (-1, 10), (0, 15), (1, 0), and (2, 5). Since x_input = -0.3 lies between -1 and 0, use the segment from (-1, 10) to (0, 15).

The slope is (15 - 10) / (0 - (-1)) = 5, so LI(-0.3) = 10 + 5 * 0.7 = 13.5.

Note: This runnable example was converted from the source graph. The graph labels the knot points (-2, 0), (-1, 10), (0, 15), (1, 0), and (2, 5), with x_input = -0.3 and output 13.5. 🐬

Constraints

  • 1 < n <= 100,000
  • x_knots and y_knots are guaranteed to have the same length

More Two Sigma problems

drafts saved locally
public float linear_interpolate(int n, float[] x_knots, float[] y_knots, float x_input) {
  // write your code here
}
n5
x_knots[-2, -1, 0, 1, 2]
y_knots[0, 10, 15, 0, 5]
x_input-0.3
expected13.5
checking account