Implement a Constant-Time Simple Moving Average
Company: Chicago
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Implement a Constant-Time Simple Moving Average
Implement a top-level operation runner for a simple moving average over a fixed-size window of the most recent integer samples.
```python
def run_sma(window_size: int, operations: list[list]) -> list:
...
```
Each operation is exactly one of:
- `["add", sample]`: add an integer sample and append `None` to the result list.
- `["get_avg"]`: append the current floating-point average. If no sample has been added, append the string `"ValueError"` and leave state unchanged.
For any malformed or unknown operation, append `"ValueError"` and leave state unchanged. When fewer than `window_size` valid samples have arrived, average all valid samples received so far. Once the window is full, a valid add evicts the oldest sample. Processing each valid operation must take `O(1)` time.
### Example
```text
Input:
window_size = 3
operations = [
["add", 1], ["get_avg"],
["add", 2], ["get_avg"],
["add", 3], ["add", 4], ["get_avg"]
]
Output: [None, 1.0, None, 1.5, None, None, 3.0]
```
### Constraints
- `1 <= window_size <= 200_000`
- Each sample fits in a signed 64-bit integer.
- The active-window sum fits in a signed 64-bit integer.
- Operation records use only literal strings and integers.
### Clarifications
- A successful `add` is represented by `None` in the output list.
- The result is ordinary floating-point division of the active sum by the active count.
### Hints
- Recomputing the sum on every query violates the target complexity.
- Keep only the information needed to add the newest value and remove the oldest one.
Quick Answer: Implement a fixed-window simple moving average with O(1) processing for every valid add and query. Maintain a rolling sum and bounded queue, average the samples available before the window fills, and return deterministic results for empty, malformed, or unknown operations.
Run add and get_avg operations over a fixed-size window of the most recent integer samples. Return None for each valid add, a floating-point average for a nonempty window, and the string 'ValueError' for empty queries or malformed operations without changing state.
Constraints
- window_size is between 1 and 200,000.
- Valid samples are integers but not booleans.
- Each valid operation must take O(1) time.
- Malformed operations append 'ValueError' and leave the window unchanged.
- The active-window sum fits in signed 64-bit range.
Examples
Input: (3, [["add", 1], ["get_avg"], ["add", 2], ["get_avg"], ["add", 3], ["add", 4], ["get_avg"]])
Expected Output: [None, 1.0, None, 1.5, None, None, 3.0]
Explanation: The average grows initially and then uses only the latest three samples.
Input: (2, [["get_avg"]])
Expected Output: ["ValueError"]
Explanation: An empty-window query is serialized as ValueError.
Hints
- Maintain a running sum along with a bounded queue.
- Subtract the oldest sample only when adding beyond capacity.
- Validate an operation fully before updating either structure.