Requirements
Given n points in a two-dimensional coordinate system, sorted or sortable by x-coordinate, connect adjacent knot points with straight line segments to define a piecewise linear function L(x).
Implement an evaluator for query x-values:
- If the query lies between two neighboring knot points, return the linearly interpolated y-value.
- If the query lies outside the smallest or largest knot point, extrapolate by extending the nearest segment.
- Sort and pack the points as needed before lookup.
- Use binary search or an equivalent indexed lookup so repeated queries do not scan all points.
- Handle duplicate x-coordinates explicitly; the prompt calls this out as an edge case.
Notes
- Multiple candidates describe this as the first QR OA task and as one of the stable rotations.
- The usual implementation path is: normalize points, sort by x, resolve or define duplicate-x behavior, find the bracketing pair with binary search, then apply the two-point line formula.
- The most common failure mode is spending too long on later regression tasks and leaving edge-case cleanup here incomplete.
Preparation
- Write the interpolation / extrapolation helper once using only the two-point slope formula.
- Practice duplicate-x handling as a clarifying question: identical x with identical y is harmless; identical x with conflicting y needs a stated policy.
- Drill a binary-search bracketing helper that returns the segment index for both in-range and out-of-range queries.