Implement sliding-window timestamped average
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Implement a class that maintains a time-based sliding window of records and can return the average score within the current window.
### Requirements
- The class is initialized with an integer `window_size` (a duration in the same units as `timestamp`, e.g., seconds).
- Each record is a pair `(timestamp, score)`.
- The class exposes two methods:
1. `insert_record(timestamp, score)`: insert a new record.
2. `get_average(current_time)`: return the average of all `score` values whose `timestamp` is within the current window.
### Window definition
At any operation time `T` (i.e., during `insert_record` or `get_average`), records are considered **valid** if:
- `timestamp` is in the range `[T - window_size, T]` (inclusive), and
- any record older than `T - window_size` must be evicted before proceeding.
### Additional notes / assumptions
- `get_average` should return a sensible value when there are no valid records (define behavior, e.g., return `0` or `null`).
- Timestamps may be non-decreasing across calls (state and use this assumption if needed), or you may design to handle out-of-order timestamps.
### Deliverables
Describe/implement the class and its methods with appropriate time and space complexity considerations.
Quick Answer: This question evaluates understanding of time-based sliding-window data structures, streaming aggregation, and the handling of timestamped records with efficient incremental updates and evictions.
Implement the behavior of a class that maintains a time-based sliding window of records. Each record is a pair (timestamp, score). On this platform, instead of writing a class directly, implement a function solution(window_size, operations) that processes operations in order and returns the results of all average queries.\n\nEach operation is one of:\n- ("insert", timestamp, score): Before inserting, evict every record with timestamp < timestamp - window_size. Then insert the new record.\n- ("get", current_time): Before answering, evict every record with timestamp < current_time - window_size. Then return the average of all scores whose timestamps are in [current_time - window_size, current_time].\n\nIf no records are valid during a get operation, return 0 for that query.\n\nAssume operation times are non-decreasing across the entire operations list.
Constraints
- 0 <= len(operations) <= 2 * 10^5
- 0 <= window_size <= 10^9
- Operation times are non-decreasing across all operations
- -10^9 <= score <= 10^9
- All timestamps and current_time values are integers
Examples
Input: (10, [('insert', 1, 4), ('insert', 5, 8), ('get', 5), ('insert', 12, 6), ('get', 12)])
Expected Output: [6.0, 7.0]
Explanation: At time 5, both records 4 and 8 are inside the window, so the average is 6.0. Before inserting at time 12, the record at time 1 is evicted because 1 < 12 - 10. The remaining scores are 8 and 6, so the average at time 12 is 7.0.
Input: (3, [('insert', 1, 5), ('insert', 3, 7), ('get', 3), ('insert', 6, 9), ('get', 6)])
Expected Output: [6.0, 8.0]
Explanation: At time 3, both scores 5 and 7 are valid, so the average is 6.0. Before inserting at time 6, the score at time 1 is evicted because 1 < 6 - 3. Then scores 7 and 9 remain, giving an average of 8.0.
Hints
- Because operation times never go backward, once a record expires it will never become valid again.
- Use a FIFO structure to store active records and keep a running sum so each get query can be answered in O(1) amortized time after evictions.