Sign in to track progress, unlock prep layers, and browse your pipeline.Sign in
Design Sliding-Window Average Tracker
Problem Description
Design a class that efficiently tracks records within a sliding time window and provides their average value.
API
The class must implement the following methods:
init(time_window): Initializes the tracker with a specified window size.insert(record_id, value, timestamp): Inserts a new record into the tracker.get_avg(timestamp): Returns the averagevalueof all records whose timestamps fall within the most recenttime_windowending at the providedtimestamp.
Assumptions and Requirements
- Each
record_idis unique. - Timestamps are integers.
- Calls to
insert(...)andget_avg(...)will always arrive with non-decreasing timestamps. - A record is considered active at time
tif its timestamptssatisfiest - time_window + 1 <= ts <= t. - If no records are active within the specified window, the
get_avgmethod should return0. - The implementation should be specifically optimized to leverage the monotonic-timestamp constraint.
Follow-up Questions
- How would you support an
update(record_id, new_timestamp)method, which changes the timestamp of an existing record while keeping its original value unchanged? - Explain how your design would need to change if inserts and queries could arrive with out-of-order timestamps.
AI interview prep
Core dilemma
Efficiently maintaining a sum and count of values within a dynamically shifting time window, leveraging monotonic timestamps for optimization, and then adapting the design for non-monotonic updates and out-of-order data arrival.
Mid-level signals3
Senior signals3
Red flags3
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design Sliding-Window Average Tracker
Problem Description
Design a class that efficiently tracks records within a sliding time window and provides their average value.
API
The class must implement the following methods:
init(time_window): Initializes the tracker with a specified window size.insert(record_id, value, timestamp): Inserts a new record into the tracker.get_avg(timestamp): Returns the averagevalueof all records whose timestamps fall within the most recenttime_windowending at the providedtimestamp.
Assumptions and Requirements
- Each
record_idis unique. - Timestamps are integers.
- Calls to
insert(...)andget_avg(...)will always arrive with non-decreasing timestamps. - A record is considered active at time
tif its timestamptssatisfiest - time_window + 1 <= ts <= t. - If no records are active within the specified window, the
get_avgmethod should return0. - The implementation should be specifically optimized to leverage the monotonic-timestamp constraint.
Follow-up Questions
- How would you support an
update(record_id, new_timestamp)method, which changes the timestamp of an existing record while keeping its original value unchanged? - Explain how your design would need to change if inserts and queries could arrive with out-of-order timestamps.