Problem: Moving Average

Let’s look at a problem where we build a class around a queue.

A sensor reports a reading every second: a temperature, a stock price, the number of requests arriving at a server. Individual readings are noisy, and one spike does not tell us much. So instead of reporting each reading on its own, we report the average of the last k readings every time a new reading comes in. That is called a moving average, and a queue is a good fit for it. The last k readings form a window. The newest reading goes in at one end, and the oldest one comes out at the other.

Here is the skeleton of the class:

public class MovingAverage {
  // your fields here

  public MovingAverage(int k) {
    // ...
  }

  public double add(int reading) {
    // record the reading and return the current average
  }
}

The constructor takes the window size k and throws an IllegalArgumentException if k is less than 1. Each call to add records the reading and returns the average of the last k readings. Until k readings have arrived, the window is not full yet, and add returns the average of all the readings so far.

Here is a sequence of calls with k = 3 and what add must return after each one. The window is written oldest first.

The window is already full when 3 arrives in the fourth row, so the oldest reading, 6, must leave. The readings leave in the order they arrived, which is FIFO order.

Each call to add must run in $O(1)$ time.

Let’s think of some special or edge cases as well:

• With k = 1, the average is always just the latest reading.
• The first few calls return the average of fewer than k readings, so the divisor is not always k.