Katkat
Back

Implement piecewise linear interpolation for time-to-empty

GoogleData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This question evaluates numerical interpolation, time-series data cleaning, monotonicity preservation, extrapolation, and numerical stability skills applied to battery discharge curves, and falls under coding and algorithms within a data science domain.

Implement a function time_to_empty(checkpoints, current_soc) that returns minutes until SOC reaches 0, using piecewise linear interpolation on a discharge curve. Input:

  • checkpoints: a sorted list of (t_min, soc_percent) pairs from a single session.
  • current_soc: the current SOC percentage (0–100). Rules and edge cases:
  • Assume soc_percent is nonincreasing during discharge; skip any charging segments (soc increase) and handle duplicate SOC levels by collapsing segments.
  • If there is no exact soc=0 point, linearly extrapolate using the last valid segment; if there are gaps around current_soc, interpolate within the bracketing segment.
  • Must run in O(n) time and O(1) extra space after sorting. Tests to satisfy:
  • checkpoints = [(0,100),(60,50),(120,0)], current_soc = 25 → expected 30 minutes.
  • Explain how your function maintains monotonicity of estimated remaining time with respect to current_soc and why it is numerically stable.