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.

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

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.

Implement a Constant-Time Simple Moving Average

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.

Hints

1. Maintain a running sum along with a bounded queue.
2. Subtract the oldest sample only when adding beyond capacity.
3. Validate an operation fully before updating either structure.

Approach

A deque stores only active samples and a running sum tracks their total. Adding at capacity removes and subtracts the oldest item before appending the new sample. Queries divide the maintained sum by the active count.

• Time complexity: O(number of operations), with O(1) time per operation.
• Space complexity: O(window_size).