Simple Moving Average over a Fixed-Size Sliding Window

Problem: Simple Moving Average over a Fixed-Size Sliding Window

Create a class named SMA that tracks integer samples in a fixed-capacity sliding window and reports the simple moving average for the samples currently retained.

Class API:

class SMA {
public:
    SMA(int windowSize);
    void add(int sample);
    double getAvg() const;
};

Requirements:

• N, the window capacity, is supplied when the object is constructed.
• Calling add(sample) appends one integer sample to the stream.
• Once the stream contains more than N samples, discard every sample except the newest N.
• getAvg() must return the arithmetic average of the retained samples as a double.
• Until N samples have arrived, calculate the average over all samples received to that point.
• The required time bounds are:
  • add(): O(1)
  • getAvg(): O(1)

Input/Output Format for Testing

Testing begins with two integers, N Q, where N specifies the window size and Q gives the number of operations.

Each of the following Q lines describes one operation:

• ADD x: insert x as the next sample.
• AVG: output the average of the current window with 6 digits after the decimal point.

Constraints

• 1 <= N <= 100000
• 1 <= Q <= 200000
• -10^9 <= sample <= 10^9
• The first AVG operation is guaranteed to occur after at least one ADD.

Example

The input sequence below first averages the progressively growing window, then averages the most recent three samples after 4 arrives:

Input:

3 8
ADD 1
AVG
ADD 2
AVG
ADD 3
AVG
ADD 4
AVG

Output:

1.000000
1.500000
2.000000
3.000000

window_size = 3
operations = 3 8
ADD 1
AVG
ADD 2
AVG
ADD 3
AVG
ADD 4
AVG

1.000000
1.500000
2.000000
3.000000