Design streaming stats with sliding window

Q: Design streaming stats with sliding window

This question evaluates skills in streaming algorithms, online data-structure design, statistical aggregation (max, mean, mode), and probabilistic approximation techniques for memory-constrained scenarios.

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

Design a data structure that ingests an integer stream and supports online queries for maximum, mean, and mode.

Describe your update and query operations and their time/space complexity.
If values are guaranteed to be in the range [1, 1001], propose an exact solution and compute the memory required to maintain the mode.
If the value domain is unbounded or memory is constrained, describe how you would approximate the mode, including the accuracy trade-offs.
Extend your design to support returning the max, mean, and mode over only the most recent k elements (a sliding window). Explain how you maintain these statistics as the window slides, analyze the complexity, and discuss how you handle ties and empty-window cases.

Design streaming stats with sliding window

Overview

Comments (0)