FastPrep
Problem · Sorting

Piecewise Linear Interpolation and Extrapolation

Learn this problem
â—Ź MediumTwo Sigma logoTwo SigmaFULLTIMEOA

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

drafts saved locally
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