Streaming Statistics: O(1) Max, Mean, and Mode
Problem statement
Implement a stream-statistics replay function supporting insert(value), max (running maximum), mean (running average), and mode (most frequent value). Insertion may be slower, but each query must be $O(1)$.
Write a function with the signature:
run_stats(events)
where events is a list of operations, each one of:
["insert", x]-- add valuexto the stream (produces no output)["max"]-- current running maximum["mean"]-- current running average (true division)["mode"]-- current most frequent value; ties break to the value that FIRST reached the current maximum count
Return a list of floats, one per query event (max/mean/mode), in the order the queries appear.
Follow-ups: (a) instead of over the whole stream, return the max/mean/mode of only the $k$ most recent values; (b) analyze memory use given that the values are integers in $[1, 1001]$ (a count array is small and bounded); (c) avoid a naive growing list if the interviewer pushes on efficiency.
Example
run_stats([["insert", 2], ["insert", 2], ["insert", 5], ["mode"], ["mean"]]) -> [2.0, 3.0] -- after inserting 2, 2, 5 the mode is 2 (count 2 beats 5's count 1) and the mean is (2+2+5)/3 = 3.0; the two inserts produce no output, so only the two query results appear.
Show hint
If every query has to be instant, where should the real work happen instead?
Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.