Time Series Sum: Compute Rolling and Cumulative Aggregates Over a Time Series

Question

## Problem

You receive a stream of `(timestamp, value)` events. Implement a class that supports two queries efficiently: (1) the sum of all values in the last `w` seconds, and (2) the cumulative sum from the beginning up to a given timestamp.

```python
class TimeSeries:
    def __init__(self): ...

def record(self, timestamp: int, value: float) -> None:
        """Record a new event. Timestamps are non-decreasing."""

def rolling_sum(self, timestamp: int, window: int) -> float:
        """Return sum of values in [timestamp - window, timestamp]."""

def cumulative_sum(self, timestamp: int) -> float:
        """Return sum of all values with timestamp <= given timestamp."""
```

**Example:**
```
ts = TimeSeries()
ts.record(1, 10); ts.record(3, 20); ts.record(5, 15)
ts.rolling_sum(5, 3)  # -> 35 (events at t=3 and t=5)
ts.cumulative_sum(3)  # -> 30
```

## Follow-ups

1. What data structure backs your rolling sum? What is the time complexity per query?
2. How would you handle out-of-order timestamps?
3. Extend to support rolling average and rolling max in O(1) per query.
4. If events arrive at 100K/sec, what are the memory implications of your approach?

Time Series Sum: Compute Rolling and Cumulative Aggregates Over a Time Series

Question Details

Full Details

Topics

More from Uber