How should I practice Piecewise Linear Interpolation and Extrapolation?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Citadel phone screen problems in FastPrep.

Is Piecewise Linear Interpolation and Extrapolation associated with Citadel?

FastPrep tags this as a Citadel phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Sorting

Piecewise Linear Interpolation and Extrapolation

Learn this problem

● Medium

CitadelFULLTIMEPHONE SCREEN

Problem statement

You are given two equal-length arrays xKnots and yKnots. Pair (xKnots[i], yKnots[i]) is a knot of a piecewise-linear function. The knots may be given in any order, and every x coordinate is distinct.

Sort the knots by increasing x coordinate and connect every adjacent pair with a straight line. Evaluate this function at queryX:

If queryX equals a knot's x, return that knot's y.
If queryX lies between two adjacent knots, interpolate on their line segment.
If queryX is smaller than every knot, extrapolate using the two leftmost knots.
If queryX is larger than every knot, extrapolate using the two rightmost knots.

For endpoints (x1, y1) and (x2, y2), evaluate their line as y1 + (y2 - y1) * (queryX - x1) / (x2 - x1).

Return the result as a double. Answers are compared with absolute or relative tolerance 10^-6. Do not use an interpolation library.

Function

evaluatePiecewiseLinear(xKnots: double[], yKnots: double[], queryX: double) → double

Examples

Example 1

xKnots = [2.0,0.0,1.0]yKnots = [4.0,0.0,1.0]queryX = 1.5return = 2.5

After sorting, 1.5 lies between (1, 1) and (2, 4). The segment slope is 3, so the result is 1 + 3 * 0.5 = 2.5.

Example 2

xKnots = [10.0,0.0,5.0]yKnots = [20.0,0.0,5.0]queryX = -2.0return = -2.0

The query is left of the knot range, so extrapolate with (0, 0) and (5, 5). Their line has slope 1.

Example 3

xKnots = [3.0,-1.0,1.0]yKnots = [2.0,4.0,0.0]queryX = 3.0return = 2.0

The query exactly equals the knot (3, 2), so return its y coordinate.

Constraints

2 <= xKnots.length = yKnots.length <= 200000
All values are finite, and every coordinate has absolute value at most 10^6.
All values in xKnots are distinct.
Answers are compared with absolute or relative tolerance 10^-6.