Solution: Moving Average from Data Stream

Statement

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Implement a class called MovingAverage that has the following methods:

• Constructor (int size): This constructor initializes the object with the specified window size.

• double next (int val): This method takes an integer value as input and returns the moving average of the last size values from the stream.

Constraints:

• $1 \leq$ size $\leq 100$

• $-10^3 \leq$ val $\leq 10^3$

• At most $10^2$ calls can be made to next.

Solution

The algorithm calculates the moving average of the most recent values within a fixed-size window. It employs a queue to store these values and maintains a running sum for efficient computation. Each time a new value is added to the window, it is appended to the queue, and the running sum is updated accordingly. If the queue exceeds the specified size (i.e., the window is full), the oldest value is removed from the queue, and the sum is adjusted by subtracting this value. The moving average is then calculated by dividing the running sum by the number of values in the queue. This approach ensures that the moving average is updated, achieving constant time complexity for each operation.

1. Constructor: The constructor initializes the following variables:

   1. size: This represents the window size, the maximum number of recent values for calculating the moving average.

   2. queue: A queue data structure stores the most recent values up to the specified window size. The queue supports efficient operations for adding new values to the end and removing the oldest value from the front, essential for maintaining the sliding window.

   3. window_sum: This keeps a running sum of the values currently in the window. This allows the moving average to be calculated efficiently without the need to sum all values repeatedly.

2. The next method: The next method calculates the moving average by following these steps:

   1. Enqueue the new value (val) to queue and add it to window_sum. This effectively extends the current sliding window to include the new value.

   2. If the number of elements in queue exceeds size (indicating the window is full), remove the oldest value from queue and update window_sum by subtracting this value. This ensures the queue size stays within the specified window size.

   3. Compute the moving average as window_sum / len(queue). Use floating-point division to ensure the result is a float.

Let’s look at the following illustration to get a better understanding of the solution: