Implement a Constant-Time Simple Moving Average
Company: Chicago Trading Company
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.
Overview: 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.
Read the full Chicago Trading Company Software Engineer interview experience this question came from
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.