Solution For Moving Average From Data Stream

Problem statement:

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1 // return 1.00000
m.next(10) = (1 + 10) / 2 // return 5.50000
m.next(3) = (1 + 10 + 3) / 3 // return 4.66667
m.next(5) = (10 + 3 + 5) / 3 // return 6.00000

Solution:

The problem requires us to keep track of a moving average of a stream of integers. We need to be able to add the incoming integers one by one, and calculate the average for each window.

We can solve the problem by using a queue to keep track of the window of integers. Whenever we add a new integer, we remove the oldest integer from the queue if the queue size exceeds the window size, and calculate the average of all integers in the queue.

To calculate the average, we need to keep track of the sum of all integers in the queue. Whenever we add or remove an integer, we update the sum and calculate the average.

We can implement the solution using a class MovingAverage that has two instance variables – a queue to keep track of the window of integers, and a sum to keep track of the sum of integers in the window, and a constructor that initializes the window size.

The next method should take an integer as input, add it to the queue, update the sum, remove the oldest integer if the window size exceeds the queue size and calculate the average.

The implementation is as follows:

“`
class MovingAverage:
def init(self, windowSize: int):
self.queue = [] self.sum = 0
self.windowSize = windowSize

def next(self, val: int) -> float:
    # add the incoming integer to the queue
    self.queue.append(val)

    # update the sum of integers in the queue
    self.sum += val

    # remove the oldest integer if the queue size exceeds the window size
    if len(self.queue) > self.windowSize:
        oldest = self.queue.pop(0)
        self.sum -= oldest

    # calculate the average of all integers in the queue
    return self.sum / len(self.queue)

“`

Time Complexity:

The time complexity of the solution is O(1) as the next method runs in constant time for each input integer, and we only perform basic arithmetic operations and append and pop operations on the queue.

Step by Step Implementation For Moving Average From Data Stream

/**
 * Initialize your data structure here.
 */
public class MovingAverage {
    private int size;
    private int[] window;
    private int count;
    private long sum;
    
    public MovingAverage(int size) {
        this.size = size;
        this.window = new int[size];
        this.count = 0;
        this.sum = 0;
    }
    
    public double next(int val) {
        if (count < size) {
            window[count] = val;
            sum += val;
            count++;
        } else {
            int head = count % size;
            sum -= window[head];
            sum += val;
            window[head] = val;
            count++;
        }
        return (double) sum / Math.min(count, size);
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

class MovingAverage:
    
    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.size = size
        self.sum = 0
        self.queue = []
        

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        if len(self.queue) == self.size:
            self.sum -= self.queue.pop(0)
        self.queue.append(val)
        self.sum += val
        return self.sum / len(self.queue)

/**
 * Initialize your data structure here.
 * @param {number} size
 */
var MovingAverage = function(size) {
    this.queue = [];
    this.size = size;
    this.sum = 0;
};

/**
 * @param {number} val
 * @return {number}
 */
MovingAverage.prototype.next = function(val) {
    if (this.queue.length < this.size) {
        this.queue.push(val);
        this.sum += val;
    } else {
        this.sum -= this.queue.shift();
        this.queue.push(val);
        this.sum += val;
    }
    return this.sum / this.queue.length;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * var obj = new MovingAverage(size)
 * var param_1 = obj.next(val)
 */

class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        
    }
    
    double next(int val) {
        
    }
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

public class MovingAverage {
   private int[] window;
   private int n, insert;
   private long sum;
 
   public MovingAverage(int size) {
     window = new int[size];
     insert = 0;
     sum = 0;
   }
 
   public double next(int val) {
     if (n < window.length)  n++;
     sum -= window[insert];
     sum += val;
     window[insert] = val;
     insert = (insert + 1) % window.length;
     return (double)sum / n;
   }
}