Design CPU-Cycle Window Alignment for Misaligned Time Series

## Interview Prompt Design and implement an algorithm that buckets two CPU-cycle time series whose timestamps do not align and produces time windows on a common basis. Treat every segment between adjacent samples as a linear function for interpolation. Before choosing data structures, make the missing contract explicit: window boundaries, endpoint inclusion, whether each window needs a point value or aggregate, behavior outside a series' sampled range, and the required output shape. ### Constraints & Assumptions - Each input series is ordered by CPU-cycle timestamp and adjacent samples define a piecewise-linear segment. - The two series may have no matching timestamps. - Window-aligned output must use one explicitly stated timestamp or interval convention for both series. - Do not silently assume union-of-sample timestamps, overlap-only output, or a particular row schema. ### Clarifying Questions to Ask - Are window boundaries supplied by the caller, fixed-width from an origin, or derived by another rule? - Does a bucket report a value at one representative timestamp or an average over the interval? - Should a window without bracketing samples be omitted, marked missing, or extrapolated? - Which side owns a sample that lands exactly on a boundary? ### What a Strong Answer Covers - A precise, stated window and output contract before algorithm details. - Correct linear interpolation within adjacent sample segments and explicit handling when no segment brackets a requested point. - A monotone scan or equivalent indexing strategy that avoids restarting from the first sample for every window. - If interval averages are required, integration of piecewise-linear segments rather than sampling one arbitrary point. - Numerical precision, boundary tests, empty windows, and complexity analysis. ### Follow-up Questions - How would the algorithm change if a bucket needs the time-weighted average rather than a boundary value? - How would you process streams online when a future sample is needed to close the current linear segment? - How would you detect counter reset or wraparound in CPU-cycle timestamps?