Moving Average from Data Stream

Problem (restated)

Given window size, stream integers via next(val). Return the average of the last at most size values.

Intuition

Queue holds the window; maintain running sum; drop oldest when full.

Approaches

export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

Template connection

Queue / deque rolling window aggregate.

Reflection

• Once the window is full, drop the oldest value from the sum. Do you divide by size, or by how many values you have actually seen?
• The first calls are shorter than the window. Dividing by size makes those averages too small.
• Negative values stay in the sum. This average is not an integer division.