Compute statistics in data stream
Company: Akuna Capital
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### 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.
Quick Answer: This question evaluates understanding of streaming data structures and statistical aggregation, specifically maintaining max, mean, and mode for an unbounded integer stream.
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
Input: ([['add', 3], ['add', 7], ['add', 3], ['max'], ['mean'], ['mode']],)
Expected Output: [7, 4.333333333333333, 3]
Explanation: Stream is [3,7,3]. max=7, mean=13/3=4.333..., mode=3 (appears twice).
Input: ([['max'], ['mean'], ['mode']],)
Expected Output: [None, None, None]
Explanation: Empty stream: every query returns None.
Hints
- Because values are bounded to 1..1001, a frequency array of size 1002 gives O(1) space no matter how long the stream is.
- Maintain max, sum, and count incrementally on each add so queries are O(1).
- 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
Input: (3, [['add', 1], ['add', 2], ['add', 3], ['max'], ['mean'], ['mode']])
Expected 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).
Input: (2, [['add', 5], ['add', 9], ['add', 4], ['max'], ['mean'], ['mode']])
Expected 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
- 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.
- On eviction, decrement the evicted value's count and subtract it from the running sum; on add, increment and add.
- 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.