Katkat
Back

Compute a moving average on a stream

AtlassianMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to maintain a running average over a sliding window of size K in a high-throughput streaming environment while managing numerical precision and memory efficiency.

Problem: Streaming Moving Average

You are tasked with building a MovingAverage class that processes a stream of numerical inputs and returns the average of the last K elements received. As a Machine Learning Engineer, you must ensure that your implementation is both time-efficient and numerically stable.

Requirements

Implement the following class interface:

class MovingAverage:
    def __init__(self, size: int):
        """Initialize with the window size K."""

    def next(self, val: float) -> float:
        """Add a new value and return the average of the last K values."""

Constraints

  • 1 <= K <= 10^6
  • The stream length can be much larger than K.
  • Your next method should ideally run in O(1) time complexity.
  • Consider the trade-off between using simple summation and maintaining higher precision during large streams of data.

Examples

Example 1:

m = MovingAverage(3)
m.next(1) # returns 1.0 (1/1)
m.next(10) # returns 5.5 ((1+10)/2)
m.next(3) # returns 4.666... ((1+10+3)/3)
m.next(5) # returns 6.0 ((10+3+5)/3)

Edge Cases

  • What happens when the stream has not yet reached K elements?
  • How does your implementation handle potential floating-point drift over millions of operations?
  • How would you handle a size that is extremely large?

Hints

Hint 1

Consider using a circular buffer (or a queue) to store the elements currently within the window to keep access time constant.

Hint 2

Instead of re-summing all elements in the window for every new value, maintain a running total variable that you update by subtracting the outgoing value and adding the incoming one.

Hint 3

If floating-point error becomes a concern over long streams, consider periodically recalculating the sum from scratch or using Kahan summation.

Follow-up questions

  • How would you modify your implementation to return the moving median instead of the moving average?
  • If this class is being called by multiple threads, how would you ensure thread safety without sacrificing too much performance?
  • How would you adapt this to calculate an Exponential Moving Average (EMA) where more recent values are given higher weight?