Implement piecewise linear interpolation for time-to-empty
Company: Google
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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.
Estimate minutes until SOC reaches zero using a cleaned monotone discharge curve and piecewise-linear interpolation/extrapolation.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([(0,100),(60,50),(120,0)], 25)
Expected Output: 30.0
Explanation: Current 25 percent occurs at minute 90, so 30 minutes remain.
Input: ([(0,100),(10,100),(70,40)], 70)
Expected Output: 70.0
Explanation: Flat duplicate SOC is collapsed to the later time.
Hints
- Skip charging increases and collapse flat SOC segments.
- Compute the time at current SOC and at zero SOC, then subtract.