Implement monotonic-array linear interpolation
Company: Tradedesk
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
##### Question
Implement a function `interpolate(array_x, array_y, x)` that returns the linearly interpolated y-value for a query x-value, given paired data points.
You are given:
- `array_x`: a **strictly increasing** (monotonic, no duplicates) list/array of numbers, length `n >= 2`
- `array_y`: a list/array of numbers of the **same length** as `array_x`
- `x`: a query number that may be **inside or outside** the range `[array_x[0], array_x[n-1]]`
Assume both arrays fit in memory.
**Tasks**
1. Return the **piecewise-linear interpolation** of the y-value when `x` is within the domain.
- If `x == array_x[i]`, return `array_y[i]` exactly.
- Otherwise, find the two surrounding points `(x0, y0)` and `(x1, y1)` such that `x0 < x < x1` and return the linear interpolation between them.
2. Discuss and/or implement the behavior when `x` is **outside** `[array_x[0], array_x[-1]]`. Consider at least these options:
- **Option A:** raise an error (no extrapolation)
- **Option B:** clamp to the nearest boundary y-value
- **Option C:** extrapolate (extend the nearest segment linearly)
3. Analyze the **time complexity** of your approach and name at least one **alternative to a binary-search (`bisect`)** strategy for locating the interval.
**Follow-ups**
1. Instead of raising an error for out-of-range queries, what other values could be returned (e.g., `None`, `NaN`), and when is each appropriate?
2. In which real-world cases does each out-of-range behavior (error / clamp / extrapolate) make sense? Give pros and cons.
3. For `x = 100` and `array_x = [2, 4, 6, 8, 11]`, what is the safest behavior and why?
4. What edge cases must you handle (very small arrays, exact matches at endpoints or interior, float precision)?
**Constraints**
- Target time complexity: **O(log n)** for in-range queries (preferred).
- Handle edge cases robustly.
Quick Answer: This question evaluates proficiency with piecewise-linear interpolation on strictly increasing (monotonic) arrays, sound handling of out-of-range queries (error, clamp, extrapolate, or None/NaN), and efficient interval search over sorted data with a target of O(log n). It also probes real-world judgment about when each out-of-range policy is appropriate and which non-bisect strategies exist.
Implement solution(array_x, array_y, x, mode="error"). array_x is strictly increasing and array_y has the same length. Return the piecewise-linear y value. For out-of-range x, mode="error" returns None, mode="clamp" returns the nearest boundary y, and mode="extrapolate" extends the nearest segment.
Constraints
- len(array_x) >= 2 for valid interpolation
- array_x is strictly increasing
Examples
Input: ([0, 10], [0, 20], 5, 'error')
Expected Output: 10.0
Input: ([2, 4, 6, 8, 11], [10, 20, 30, 40, 70], 4, 'error')
Expected Output: 20
Input: ([2, 4, 6, 8, 11], [10, 20, 30, 40, 70], 5, 'error')
Expected Output: 25.0
Input: ([2, 4, 6], [10, 20, 30], 1, 'clamp')
Expected Output: 10
Input: ([2, 4, 6], [10, 20, 30], 8, 'extrapolate')
Expected Output: 40.0
Input: ([2], [10], 2, 'error')
Expected Output: None
Hints
- Use binary search to find the insertion point.
- Handle exact matches before computing a fraction.