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.

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.

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.

What difficulty level is this interview question?

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

What role is this question designed for?

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

Implement piecewise linear interpolation for time-to-empty

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.

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.

Implement piecewise linear interpolation for time-to-empty

Quick Overview

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

Inputs

Rules and Edge Cases

Output

Tests to Satisfy

Explain

Solution

Submit Your Answer to Earn 20XP

Implement piecewise linear interpolation for time-to-empty

Quick Overview

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

Inputs

Rules and Edge Cases

Output

Tests to Satisfy

Explain

Solution

Submit Your Answer to Earn 20XP