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.

Evaluate piecewise linear function at x | Two Sigma Coding Question

Q: Evaluate piecewise linear function at x

This question evaluates competency in numerical interpolation and handling of piecewise linear functions, including locating the correct segment in a sorted sequence of points and managing out-of-range inputs.

Evaluate piecewise linear function at x

Company: Two Sigma

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a polyline defined by **n** 2D points \((x_i, y_i)\). Connecting consecutive points with straight line segments forms a **piecewise linear function**. ### Task Given a **target** value `x`, return the corresponding function value `y(x)`: - If `x` equals some `x_i`, return `y_i`. - If `x` lies strictly between `x_i` and `x_{i+1}`, linearly interpolate on the segment between \((x_i, y_i)\) and \((x_{i+1}, y_{i+1})\): \[ y(x)=y_i + (y_{i+1}-y_i)\cdot\frac{x-x_i}{x_{i+1}-x_i} \] - If `x < x_0` or `x > x_{n-1}`, return `null` (or a sentinel) because the function is undefined outside the polyline. ### Input - `points`: list of `n` pairs `(x, y)` - `x`: target x-coordinate ### Assumptions / Constraints - `n >= 2` - Points are given sorted by strictly increasing `x` (i.e., `x0 < x1 < ... < x(n-1)`). ### Output - A numeric value `y(x)` (float), or `null` if out of range.

Quick Answer: This question evaluates competency in numerical interpolation and handling of piecewise linear functions, including locating the correct segment in a sorted sequence of points and managing out-of-range inputs.

You are given a polyline defined by n 2D points (x_i, y_i). Connecting each consecutive pair of points creates a piecewise linear function. Given a target x-value, return the corresponding y-value on the function. Rules: - If x is exactly equal to some x_i, return y_i. - If x lies strictly between x_i and x_{i+1}, compute the value using linear interpolation: y(x) = y_i + (y_{i+1} - y_i) * (x - x_i) / (x_{i+1} - x_i) - If x is outside the range [x_0, x_{n-1}], return None. In this problem, use None as the sentinel for an undefined value.

Constraints

2 <= len(points) <= 100000
points[i][0] < points[i+1][0] for all valid i
Each coordinate and the target x is an integer or floating-point number in the range [-10^9, 10^9]

Examples

Input: ([(0, 0), (2, 4), (5, 1)], 2)

Expected Output: 4.0

Explanation: The target x matches an existing point (2, 4), so the answer is 4.0.

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

Expected Output: 5.0

Explanation: The target lies halfway between x=0 and x=10 on a line from y=0 to y=10, so the interpolated value is 5.0.

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

Expected Output: -2.0

Explanation: The target lies between (-3, -6) and (1, 2). Interpolating gives -6 + (2 - (-6)) * ((-1 - (-3)) / (1 - (-3))) = -2.0.

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

Expected Output: -6.0

Explanation: The target x matches the first point exactly, so return its y-value.

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

Expected Output: None

Explanation: The target x is greater than the last x-coordinate, so the function is undefined there.

Hints

Because the x-coordinates are sorted, you can use binary search to find the segment containing the target x.
Handle the easy cases first: out-of-range values and exact matches to an existing point.

Quick Overview

This question evaluates competency in numerical interpolation and handling of piecewise linear functions, including locating the correct segment in a sorted sequence of points and managing out-of-range inputs.