Moving Average from Data Stream

This question is asked by Microsoft. Design a class, MovingAverage, which contains a method, next that is responsible for returning the moving average from a stream of integers.

Note: A moving average is the average of a subset of data at a given point in time.

Example(s)

Example 1:

MovingAverage m = new MovingAverage(3);
m.next(3) // returns 3.0
m.next(5) // returns 4.0
m.next(7) // returns 5.0
m.next(6) // returns 6.0

Solution

JavaScript Solution

/**
 * Moving Average class that maintains a sliding window average
 * @param {number} size - Size of the sliding window
 */
class MovingAverage {
  constructor(size) {
    this.capacity = size;
    this.queue = [];
    this.sum = 0;
  }
  
  /**
   * Add a new value and return the current moving average
   * @param {number} val - New value to add
   * @return {number} - Current moving average
   */
  next(val) {
    this.queue.push(val);
    this.sum += val;
    
    if (this.queue.length > this.capacity) {
      this.sum -= this.queue.shift();
    }
    
    return this.sum / this.queue.length;
  }
}

Python Solution

from collections import deque

class MovingAverage:
    """
    Moving Average class that maintains a sliding window average
    
    Args:
        size: Size of the sliding window
    """
    def __init__(self, size: int):
        self.capacity = size
        self.queue = deque()
        self.sum = 0
    
    def next(self, val: int) -> float:
        """
        Add a new value and return the current moving average
        
        Args:
            val: New value to add
            
        Returns:
            float: Current moving average
        """
        self.queue.append(val)
        self.sum += val
        
        if len(self.queue) > self.capacity:
            self.sum -= self.queue.popleft()
        
        return self.sum / len(self.queue)

Complexity

• Time Complexity: O(1) - Amortized constant time per next operation
• Space Complexity: O(n) - Where n is the window size

Interactive Code Runner

Test the Moving Average Implementation

JavaScript Solution

JavaScript Moving Average Checker

/**
* Moving Average class that maintains a sliding window average
* @param {number} size - Size of the sliding window
*/
class MovingAverage {
constructor(size) {
  this.capacity = size;
  this.queue = [];
  this.sum = 0;
}

/**
 * Add a new value and return the current moving average
 * @param {number} val - New value to add
 * @return {number} - Current moving average
 */
next(val) {
  this.queue.push(val);
  this.sum += val;
  
  if (this.queue.length > this.capacity) {
    this.sum -= this.queue.shift();
  }
  
  return this.sum / this.queue.length;
}
}

// Test the example sequence
const m = new MovingAverage(3);
console.log(m.next(3)); // returns 3.0
console.log(m.next(5)); // returns 4.0
console.log(m.next(7)); // returns 5.0
console.log(m.next(6)); // returns 6.0

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Moving Average Checker

from collections import deque

class MovingAverage:
  """
  Moving Average class that maintains a sliding window average
  
  Args:
      size: Size of the sliding window
  """
  def __init__(self, size: int):
      self.capacity = size
      self.queue = deque()
      self.sum = 0
  
  def next(self, val: int) -> float:
      """
      Add a new value and return the current moving average
      
      Args:
          val: New value to add
          
      Returns:
          float: Current moving average
      """
      self.queue.append(val)
      self.sum += val
      
      if len(self.queue) > self.capacity:
          self.sum -= self.queue.popleft()
      
      return self.sum / len(self.queue)

# Test the example sequence
m = MovingAverage(3)
print(m.next(3))  # returns 3.0
print(m.next(5))  # returns 4.0
print(m.next(7))  # returns 5.0
print(m.next(6))  # returns 6.0

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Takeaways

• Queue implementation efficiently manages the sliding window
• Running sum allows O(1) average computation
• Amortized O(1) operations since each element is added and removed once
• Handles partial windows when fewer elements than capacity
• Floating point return requires careful type casting in static languages