Moving Average from Data Stream

The problem is about calculating the moving average of the last size values in a stream of integers. We can implement the MovingAverage class by utilizing a queue (FIFO) data structure to maintain the window of the last size values and compute the moving average efficiently.

Here’s a guide to implementing this class:

1. Initialize the Class Variables: The constructor will initialize the size and a queue to keep track of the integers in the current window. You can also maintain the sum of the numbers in the window for efficient calculation.

2. Implement the next Method:

   • Add the Value to the Queue: Add the incoming value to the queue.
   • Update the Sum: Add the value to the sum of the window.
   • Check Window Size: If the window size exceeds size, remove the oldest value from the queue and subtract it from the sum.
   • Calculate and Return the Average: Return the sum divided by the current window size.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.window_sum = 0

    def next(self, val: int) -> float:
        # Add the new value to the queue
        self.queue.append(val)
        # Update the sum with the new value
        self.window_sum += val

        # If the window size exceeds the given size, remove the oldest value
        if len(self.queue) > self.size:
            removed_val = self.queue.popleft()
            self.window_sum -= removed_val

        return self.window_sum / len(self.queue)

Explanation:

• The deque data structure ensures efficient addition and removal of elements from both ends.
• The window_sum variable keeps track of the sum of the elements in the current window, allowing for quick average calculation.
• When a new value is added to the queue and the window size exceeds the given size, the oldest value is removed from the queue and subtracted from window_sum.
• The moving average is returned by dividing window_sum by the current window size.

This solution meets the constraints and provides an efficient way to calculate the moving average in a sliding window.

1. Given: stream of integers and window size Unknown: Moving Average

2. What is moving average?

   • summation of the elements within the window size / window size

3. Invariant - Cannot exceed the window size window size <= size

Time: O(N) Space: O(M)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class MovingAverage

=begin
    Initialize your data structure here.
    :type size: Integer

    What should we keep track of to have sliding windwo
      For sliding window, for evicting the left element leaving the window
         - start index
         - end index
     - window_sum
     - what is the left element we need to subtract - popleft, shift
     
=end
    def initialize(size)        
        @size = size
        @stream = []
        @window_sum = 0
        @count = 0
    end

=begin
    :type val: Integer
    :rtype: Float
=end
    def next(val)
        @count += 1
        @stream << val
        left = 0.0

        if @count > @size
           left = @stream.shift 
        end

        @window_sum = @window_sum - left + val

        return @window_sum / [@size, @count].min
    end
end

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