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 Take-home Project 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.

Compute Piecewise Linear Interpolation | Two Sigma Coding Question

Compute Piecewise Linear Interpolation

Company: Two Sigma

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given an unsorted list of distinct 2D points `(x_i, y_i)`. When the points are sorted by `x_i`, connecting adjacent points forms a polyline. Given a query value `x`, return the corresponding `y` value on this polyline: - If `x` exactly matches an existing point's x-coordinate, return that point's y-coordinate. - If `x` lies between two adjacent points, use linear interpolation. - If `x` is smaller than the minimum x-coordinate, extrapolate using the first two points after sorting. - If `x` is larger than the maximum x-coordinate, extrapolate using the last two points after sorting. Design an efficient algorithm. You may assume there are at least two points and all x-coordinates are distinct. Example: ```text points = [(0, 0), (10, 20), (20, 10)] x = 5 output = 10 ``` Explanation: `x = 5` lies halfway between `(0, 0)` and `(10, 20)`, so the interpolated y-value is `10`.

Quick Answer: This question evaluates skills in algorithm design and numerical interpolation, including sorting and searching among 2D points, handling boundary cases for extrapolation, and computing linear interpolation accurately and efficiently.

You are given an unsorted list of distinct 2D points `(x_i, y_i)`. If the points are sorted by `x_i` and adjacent points are connected, they form a polyline. Given a query value `x`, return the corresponding `y` value on this polyline: - If `x` exactly matches an existing point's x-coordinate, return that point's y-coordinate. - If `x` lies between two adjacent points, use linear interpolation. - If `x` is smaller than the minimum x-coordinate, extrapolate using the first two points after sorting. - If `x` is larger than the maximum x-coordinate, extrapolate using the last two points after sorting. Design an efficient algorithm. You may assume there are at least two points and all x-coordinates are distinct.

Constraints

2 <= len(points) <= 2 * 10^5
All x-coordinates in `points` are distinct
`x_i`, `y_i`, and query `x` are numeric values in the range [-10^9, 10^9]

Examples

Input: ([(5, 10), (1, 2), (3, 6)], 5)

Expected Output: 10.0

Explanation: After sorting, the points are (1,2), (3,6), (5,10). Since x = 5 exactly matches an existing point, return its y-value, 10.0.

Input: ([(5, 10), (1, 2), (3, 6)], 4)

Expected Output: 8.0

Explanation: After sorting, x = 4 lies between (3,6) and (5,10). The slope is (10-6)/(5-3) = 2, so y = 6 + 2*(4-3) = 8.0.

Input: ([(4, 8), (0, 0), (2, 4)], -1)

Expected Output: -2.0

Explanation: After sorting, x = -1 is smaller than the minimum x-value 0, so extrapolate using (0,0) and (2,4). The slope is 2, so y = 0 + 2*(-1-0) = -2.0.

Input: ([(-2, -4), (3, 6), (1, 2)], 5)

Expected Output: 10.0

Explanation: After sorting, x = 5 is larger than the maximum x-value 3, so extrapolate using the last two points (1,2) and (3,6). The slope is 2, so y = 6 + 2*(5-3) = 10.0.

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

Expected Output: 10.0

Explanation: There are only two points, so the whole polyline is one segment. Interpolating halfway between (0,0) and (10,20) gives y = 10.0.

Input: ([(5, 9), (0, 0), (2, 3)], 1)

Expected Output: 1.5

Explanation: After sorting, x = 1 lies between (0,0) and (2,3). The slope is 3/2 = 1.5, so y = 0 + 1.5*(1-0) = 1.5.

Hints

Sort the points by x-coordinate first; after that, only one segment can contain the query x.
Use binary search on the sorted x-values to find whether x matches a point or falls between two neighboring points.

Quick Overview

This question evaluates skills in algorithm design and numerical interpolation, including sorting and searching among 2D points, handling boundary cases for extrapolation, and computing linear interpolation accurately and efficiently.