Implement sliding-window timestamped average

Q: Implement sliding-window timestamped average

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.

Q: 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.

Question

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.