Program Linear Interpolation | Dataford Interview Questions

Two Sigma research workflows may represent a signal as values sampled at irregular x-coordinates. Given these samples, evaluate the signal at multiple query coordinates using piecewise linear interpolation.

Implement linear_interpolate(x_values, y_values, queries). For each query q, find the two neighboring sample points (x_i, y_i) and (x_{i+1}, y_{i+1}) such that x_i <= q <= x_{i+1}, then return:

y_i + (q - x_i) * (y_{i+1} - y_i) / (x_{i+1} - x_i)

A query equal to a sample coordinate must return the corresponding sample value. Queries are guaranteed to lie within the range of the sample coordinates, so extrapolation is not required. Return results in the same order as queries.

Formal Specification

x_values: a strictly increasing list of n numbers.
y_values: a list of n numbers corresponding to x_values.
queries: a list of m numbers to evaluate.
Return a list of m floating-point numbers.

Constraints

2 <= len(x_values) <= 10^5
len(x_values) == len(y_values)
0 <= len(queries) <= 10^5
x_values is strictly increasing
Every query is between x_values[0] and x_values[-1]
All coordinates and values are finite numbers

Function Signature

def linear_interpolate(x_values, y_values, queries):

Your question is Program Linear Interpolation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem