Implement piecewise linear interpolation for time-to-empty

Q: Implement piecewise linear interpolation for time-to-empty

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

Q: What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Google during technical interviews.

Question

Time-to-Empty from a Discharge Curve (Piecewise Linear Interpolation)

Implement a function time_to_empty(checkpoints, current_soc) that returns the number of minutes until the battery's state of charge (SOC) reaches 0. Use piecewise linear interpolation on a discharge curve built from time-stamped SOC measurements.

Inputs

checkpoints: a list of (t_min, soc_percent) tuples sorted by time (ascending). All points are from a single session.
current_soc: the current SOC percentage in [0, 100].

Rules and Edge Cases

Discharge-only assumption: SOC is nonincreasing during discharge.
- Skip any charging segments (i.e., where SOC increases).
- Handle duplicate SOC levels (flat segments) by collapsing them into a single point.
Interpolation and extrapolation:
- If there is no exact soc = 0 point in the data, linearly extrapolate using the last valid decreasing segment.
- If current_soc falls between two SOC levels, interpolate within the bracketing segment.
- If current_soc falls outside the observed SOC range after cleaning (above the max or below the min), extrapolate using the first/last valid decreasing segment, respectively.
Performance: O(n) time and O(1) extra space after sorting.

Output

Minutes (float) until SOC reaches 0 from current_soc.

Tests to Satisfy

checkpoints = [(0, 100), (60, 50), (120, 0)], current_soc = 25 → expected 30 minutes.

Explain

Explain how your function maintains monotonicity of the estimated remaining time with respect to current_soc and why it is numerically stable.