Compute statistics in data stream

Question

Design a data structure that supports computing the current max, mean, and mode for an unbounded integer data stream. Estimate the memory usage of your design; assume the integers lie in the range 1–1001. Modify the design to return the max, mean, and mode for only the most recent k elements using a sliding-window approach.

Streaming Statistics: Max, Mean, and Mode (Unbounded)

Design a data structure for an unbounded integer data stream that supports computing the current max, mean, and mode at any time. All integers lie in the range 1..1001.

To make the design executable, implement a single function that replays a list of operations against your structure and returns the result of every query operation, in order.

Each operation is a list:

• ['add', x] — push integer x (1 <= x <= 1001) into the stream. Produces no output.
• ['max'] — return the current maximum, or None if the stream is empty.
• ['mean'] — return the current mean as a float, or None if empty.
• ['mode'] — return the most frequent value so far; on a tie, return the smallest such value; None if empty.

Memory analysis (the interview's real ask): keep a fixed counts array of length 1002 (index = value, since values are 1..1001), a running sum, and a running count. That is O(1) extra space regardless of how many integers stream in — roughly 1002 * 8 bytes ≈ 8 KB for the counts array plus a few scalars. max is maintained incrementally on each add; mode is maintained by tracking the current best (value, frequency) on each add. No element history is stored.

Constraints

• 1 <= x <= 1001 for every added integer
• Queries on an empty stream return None
• Mode ties are broken by returning the smallest value
• The stream is unbounded; the design must not grow with the number of elements

Examples

Example 1

Input: ([['add', 3], ['add', 7], ['add', 3], ['max'], ['mean'], ['mode']],)
Output: [7, 4.333333333333333, 3]

Explanation: Stream is [3,7,3]. max=7, mean=13/3=4.333..., mode=3 (appears twice).

Example 2

Input: ([['max'], ['mean'], ['mode']],)
Output: [None, None, None]

Explanation: Empty stream: every query returns None.

Hints

1. Because values are bounded to 1..1001, a frequency array of size 1002 gives O(1) space no matter how long the stream is.
2. Maintain max, sum, and count incrementally on each add so queries are O(1).
3. Track the current best (value, frequency) on each add to answer mode in O(1); update best when an incoming value's new count beats it, or ties it with a smaller value.

Streaming Statistics over a Sliding Window of k Elements

Extend the previous design so that max, mean, and mode are computed over only the most recent k elements of the stream. When a new integer is added and the window already holds k elements, the oldest element is evicted first. Values are still in the range 1..1001.

Implement a function that takes the window size k and a list of operations, replays them, and returns the result of every query operation in order.

Operations:

• ['add', x] — push x (1 <= x <= 1001); evict the oldest if the window is full. No output.
• ['max'] — max over the current window, or None if empty.
• ['mean'] — mean over the current window as a float, or None if empty.
• ['mode'] — mode over the current window; on a tie, the smallest value; None if empty.

Memory: a ring buffer / deque of up to k elements for eviction order, plus the same counts array of size 1002. Space is O(k) (dominated by the window), independent of the total stream length. On eviction, decrement the evicted value's count; max is recomputed by scanning the bounded counts array downward from 1001, and mode by scanning the counts array — both O(1001) = O(1) with respect to k.

Constraints

• 1 <= k
• 1 <= x <= 1001 for every added integer
• Adding to a full window evicts the oldest element first (FIFO)
• Queries on an empty window return None
• Mode ties are broken by returning the smallest value

Examples

Example 1

Input: (3, [['add', 1], ['add', 2], ['add', 3], ['max'], ['mean'], ['mode']])
Output: [3, 2.0, 1]

Explanation: Window [1,2,3] (k=3, none evicted yet): max=3, mean=6/3=2.0, mode=1 (all tied, smallest wins).

Example 2

Input: (2, [['add', 5], ['add', 9], ['add', 4], ['max'], ['mean'], ['mode']])
Output: [9, 6.5, 4]

Explanation: k=2: adding 4 evicts 5, window becomes [9,4]. max=9, mean=13/2=6.5, mode=4 (tie, smallest).

Hints

1. Keep a FIFO deque of the window's elements so you know which value to evict, and a counts array of size 1002 for the value frequencies inside the window.
2. On eviction, decrement the evicted value's count and subtract it from the running sum; on add, increment and add.
3. Because values are bounded, recompute max by scanning the counts array downward from 1001, and mode by scanning it upward (first value with the highest count handles the smallest-on-tie rule). These scans are O(1) in k.