Design CPU-Cycle Window Alignment for Misaligned Time Series
Company: Gimlet Labs
Role: Member of Technical Staff, ML Systems
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
## 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?
Overview: Define and implement a precise windowing contract for two misaligned CPU-cycle time series using piecewise-linear interpolation, monotone scanning, explicit boundary behavior, and optional interval integration.