Find Moving Average of Last N numbers in a Stream.
You are given a stream of numbers, calculate moving average of last N numbers in a stream.
In other words,
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Lets see sample input and output for better understanding:
Algorithm
For calculating the average of window size numbers we need to store numbers equal to the size of window.
Example: Stream of data 3, 5, 2, 8, 1, 2, 9, 1.5, 7.5, 5.5 ....
Our window is of size 4,
1st number, 2nd number, 3rd number, 4th number
3 5 2 8
Storing four number should be enough to get the average as we are interested in average of last 4 numbers only.
Now, when the new element come in, oldest element from the window will be out and new element will come in,
-------------------------------------------------------------------------------
1st number, 2nd number, 3rd number, 4th number
3 5 2 8
-------------------------------------------------------------------------------
--> 1 came in.
1st number, 2nd number, 3rd number, 4th number
3 5 2 8 1
(3 is out from window)
-------------------------------------------------------------------------------
--> 2 came in,
1st number, 2nd number, 3rd number, 4th number
1 5 2 8 1 2
(5 is out from window)
-------------------------------------------------------------------------------
Which data structure do you think should help here, where we want to add the elements but also remove the oldest element read when the size of structure reaches window size?Queue operates in similar fashion(FIFO = first in first out)
We will use Queue and make sure the size of queue is equal to size of window, when the size exceeds, we will poll the element from the queue, which will remove the first entry and make space for new elements.
While adding and removing the element from the window, add(new element coming inside the window) and subtract(old element getting out of the window) element from the total sum of the window and we can get the average by (sum of the window / window size).
Note: Below program assume that sum of the elements present in Window will not cross Float.MAX_VALUE
Note: Below program assume that sum of the elements present in Window will not cross Float.MAX_VALUE
package com.javabypatel.misc;
/*
Input: Stream of numbers = 3, 5, 2, 8, 1, 2, 9, 1.5, 7.5, 5.5 ....
Window Size = 4
Output: Moving Average of the Given Array of Window size 4:
Average calculated after processing each number,
0.75, 2.0, 2.5, 4.5, 4.0, 3.25, 5.0, 3.375, 5.0, 5.875
Explanation:
Stream: 3 (Window Size = 4)
find Average ->
sum = 3
Average = 3/4 = 0.75
Stream: 3, 5 (Window Size = 4)
find Average ->
sum = 3 + 5 Average = 8/4 = 2.0
Stream: 3, 5, 2 (Window Size = 4)
find Average ->
sum = 3 + 5 + 2 Average = 10/4 = 2.5
Stream: 3, 5, 2, 8 (Window Size = 4)
find Average ->
sum = 3 + 5 + 2 + 8 Average = 18/4 = 4.5
Stream: 5, 2, 8, 1 (Window Size = 4)
find Average ->
sum = 5 + 2 + 8 + 1 Average = 16/4 = 4
Note: this time 3 is removed from window of size 4 because that was the oldest in the window and new
element 1 got added in its place, in fact adding any element from this point will remove oldest
element in the window as the window is full.
Stream: 2, 8, 1, 2 (Window Size = 4)
find Average ->
sum = 2 + 8 + 1 + 2 Average = 13/4 = 3.25
*/
public class MainApp {
public static void main(String[] args) {
MovingAverage movingAverage = new MovingAverageImpl(4);
movingAverage.addElement(3);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(5);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(2);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(8);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(1);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(2);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(9);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(1.5f);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(7.5f);
System.out.println(movingAverage.getAverage());
movingAverage.addElement(5.5f);
System.out.println(movingAverage.getAverage());
}
}
package com.javabypatel.misc;
import java.util.LinkedList;
import java.util.Queue;
public class MovingAverageImpl implements MovingAverage {
private Queue<Float> queue;
private float sum; //Assuming data will not exceed Float.MAX_VALUE
private int averageSize;
public MovingAverageImpl(int averageSize) {
queue = new LinkedList<>();
this.averageSize = averageSize;
}
@Override
public void addElement(float data) {
if (queue.size() >= averageSize) {
float dataToRemove = queue.poll();
sum -= dataToRemove;
}
queue.add(data);
sum += data;
}
@Override
public float getAverage() {
return sum / averageSize;
}
}
package com.javabypatel.misc;
public interface MovingAverage {
void addElement(float data);
float getAverage();
}
You may also like to see
Sort Linked list using Merge sort
Bubble Sort
Heap Sort
Selection Sort
Insertion Sort
How ConcurrentHashMap works and ConcurrentHashMap interview questions
How Much Water Can A Bar Graph with different heights can Hold
Interview Questions-Answer Bank
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment