Katkat
Back

Implement monotonic-array linear interpolation

The Trade DeskData Scientist · Technical Screen
EasyData ScientistTechnical ScreenCoding & Algorithms

Last updated

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.

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.
  1. 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)
  1. 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.