Data Structures & Algorithms FAQ: Top Questions

Design a class to compute the moving average of the last k numbers in a stream.

How it Works:

1. Track a queue of the last k elements.
2. Keep a running sum to maintain the average efficiently.
3. Pop the oldest element if the queue exceeds size k .

Example Usage:

const m = new MovingAverage(3);
m.next(3); // returns 3.0
m.next(9); // returns 6.0
m.next(4); // returns 5.33
m.next(2); // returns 5.0

Solution (TypeScript):

class MovingAverage {
  private size: number;
  private queue: number[] = [];
  private sum: number = 0;

  constructor(size: number) {
    this.size = size;
  }

  next(val: number): number {
    if (this.queue.length === this.size) {
      const removed = this.queue.shift()!;
      this.sum -= removed;
    }
    this.queue.push(val);
    this.sum += val;
    return this.sum / this.queue.length;
  }
}