How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Two Sigma during technical interviews.

Linear Interpolator with Extrapolation | Two Sigma Coding Question

Linear Interpolator with Extrapolation

Company: Two Sigma

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

# Linear Interpolator with Extrapolation You are given `n` knot points in a 2D coordinate system, where `knots[i] = [x_i, y_i]`. All x-coordinates are distinct, but the points are given in no particular order. After sorting the knots by x-coordinate, connecting each consecutive pair of knots with a straight line segment defines a piecewise linear function `L(x)` — a **linear interpolator** — on the interval `[x_min, x_max]`, where `x_min` and `x_max` are the smallest and largest knot x-coordinates. Outside that interval, `L(x)` is defined by **linear extrapolation**: - For `x < x_min`, extend the straight line that passes through the two leftmost knots. - For `x > x_max`, extend the straight line that passes through the two rightmost knots. Write a function: ``` interpolate(knots, queries) -> answers ``` that returns an array `answers` of the same length as `queries`, where `answers[j] = L(queries[j])`. ## Example 1 ``` Input: knots = [[0, 0], [10, 10], [20, 0]] queries = [5, 10, 15] Output: [5.0, 10.0, 5.0] ``` Explanation: The segment from `(0, 0)` to `(10, 10)` has slope 1, so `L(5) = 5`. `x = 10` is exactly a knot, so `L(10) = 10`. The segment from `(10, 10)` to `(20, 0)` has slope -1, so `L(15) = 5`. ## Example 2 ``` Input: knots = [[10, 10], [0, 0], [20, 0]] queries = [-5, 25] Output: [-5.0, -5.0] ``` Explanation: The knots are unsorted; after sorting by x they are `(0, 0), (10, 10), (20, 0)`. For `x = -5 < x_min = 0`, extrapolate the line through the two leftmost knots `(0, 0)` and `(10, 10)` (slope 1): `L(-5) = -5`. For `x = 25 > x_max = 20`, extrapolate the line through the two rightmost knots `(10, 10)` and `(20, 0)` (slope -1): `L(25) = 0 + (-1) * (25 - 20) = -5`. ## Constraints - `2 <= n <= 100,000` - `1 <= len(queries) <= 100,000` - `-10^9 <= x_i, y_i, queries[j] <= 10^9`, real numbers with at most 6 digits after the decimal point - All `x_i` are distinct - A query may fall exactly on a knot, between knots, or outside the knot range - Answers are accepted within an absolute or relative error of `10^-6` Your solution should sort the knots once and locate each query's segment efficiently — an `O((n + q) log n)` approach is expected, where `q` is the number of queries.

Quick Answer: This question evaluates understanding of piecewise linear interpolation and extrapolation, numerical robustness with floating-point values, and algorithmic competencies such as sorting and efficient query location for large datasets.

You are given `n` knot points in a 2D plane, `knots[i] = [x_i, y_i]`, with all x-coordinates distinct and given in no particular order. After sorting the knots by x-coordinate, connecting each consecutive pair with a straight segment defines a piecewise-linear function `L(x)` on `[x_min, x_max]`. Outside that interval, `L(x)` is defined by linear extrapolation: - For `x < x_min`, extend the line through the two leftmost knots. - For `x > x_max`, extend the line through the two rightmost knots. Implement `solution(knots, queries)` returning an array `answers` where `answers[j] = L(queries[j])`. Example 1: knots = [[0,0],[10,10],[20,0]], queries = [5,10,15] -> [5.0, 10.0, 5.0]. Example 2 (unsorted): knots = [[10,10],[0,0],[20,0]], queries = [-5,25] -> [-5.0, -5.0]. Sort the knots once and locate each query's segment with binary search for an O((n + q) log n) solution. Answers are accepted within 1e-6 absolute or relative error.

Constraints

2 <= n <= 100000
1 <= len(queries) <= 100000
-1e9 <= x_i, y_i, queries[j] <= 1e9 (real, up to 6 decimals)
All x_i are distinct
A query may fall on a knot, between knots, or outside the knot range
Answers accepted within 1e-6 absolute or relative error

Examples

Input: ([[0, 0], [10, 10], [20, 0]], [5, 10, 15])

Expected Output: [5.0, 10.0, 5.0]

Explanation: Segment (0,0)-(10,10) slope 1 gives L(5)=5; x=10 is a knot so L(10)=10; segment (10,10)-(20,0) slope -1 gives L(15)=5.

Input: ([[10, 10], [0, 0], [20, 0]], [-5, 25])

Expected Output: [-5.0, -5.0]

Explanation: Knots sort to (0,0),(10,10),(20,0). x=-5 extrapolates the leftmost line (slope 1): -5. x=25 extrapolates the rightmost line (slope -1): 0 + -1*(25-20) = -5.

Hints

Sort the knots by x once, then binary-search (bisect) each query to find its enclosing segment.
For x <= x_min use the two leftmost knots; for x >= x_max use the two rightmost knots. A query exactly on a boundary knot is handled correctly by these same two-knot lines.
On each chosen segment (x0,y0)-(x1,y1), L(x) = y0 + (y1-y0)/(x1-x0) * (x - x0). The same formula does interpolation and extrapolation.

Quick Overview

This question evaluates understanding of piecewise linear interpolation and extrapolation, numerical robustness with floating-point values, and algorithmic competencies such as sorting and efficient query location for large datasets.