FastPrepPiecewise Linear Interpolation and Extrapolation

Piecewise Linear Interpolation and Extrapolation

Two Sigma logoTwo Sigma● MediumFULLTIMEOA
Learn

Problem statement

The function receives the full standard input payload as one string. The first line contains integers n and q. The next n lines contain points (x, y), and the next q lines contain query coordinates xq.

Sort the points by increasing x and connect consecutive points with straight line segments.

  • If xq lies between adjacent points, use linear interpolation on that segment.
  • If xq is smaller than the first point's x, extend the leftmost segment.
  • If xq is larger than the last point's x, extend the rightmost segment.
  • If xq equals a point's x, return that point's y.

For segment endpoints (xa, ya) and (xb, yb), compute y = ya + (yb - ya) * (xq - xa) / (xb - xa).

Return the query results in order as a double[]. Numeric answers are accepted within an absolute or relative tolerance of 1e-6.

Function

solvePiecewiseLinearInterpolation(input: String) → double[]

Examples

Example 1

input = "3 4\n2 2\n0 0\n1 1\n-1\n0.5\n2\n3"return = [-1.0,0.5,2.0,3.0]

After sorting, the points are (0, 0), (1, 1), and (2, 2). They lie on y = x, so the two extrapolated queries and two in-range queries return [-1.0, 0.5, 2.0, 3.0].

Constraints

  • 2 <= n <= 2 * 10^5
  • 1 <= q <= 2 * 10^5
  • After sorting, all point x coordinates are strictly increasing.
  • The target overall complexity is O((n + q) log n).

More Two Sigma problems

See Two Sigma hiring insights
public double[] solvePiecewiseLinearInterpolation(String input) {
    // write your code here
}
input"3 4\n2 2\n0 0\n1 1\n-1\n0.5\n2\n3"
expected[-1.0,0.5,2.0,3.0]
Checking account…