Moving Average from Data Stream
Given a stream of integers and a window size k, calculate the moving average of the last k values each time a new value arrives.
You will receive the window size and a sequence of values. For each value, output the moving average with 2 decimal places.
Example:
3 1,10,3,5
1.00 5.50 4.67 6.00
- Initially, the window size
kis set to 3, and the first value 1 arrives, so the moving average is 1.00=11​. - When the second value 10 arrives, the window contains [1, 10], so the moving average is 21+10​=5.50.
- The third value 3 arrives, and the window becomes [1, 10, 3], so the moving average is 31+10+3​=4.67.
- Finally, the fourth value 5 arrives, and the window updates to [10, 3, 5], so the moving average is 310+3+5​=6.00.
Constraints:
- 1 <= k <= 1000
- -10^5 <= val <= 10^5
- At most 10^4 calls to next
Background Knowledge
The moving average is a widely used concept in data analysis and signal processing. It involves calculating the average of a set of values over a fixed-size window, which moves over the data stream. In this problem, we are dealing with a stream of integers and a window size k. The moving average is calculated by summing up the last k values and dividing by k. This technique is useful for smoothing out noise in data and highlighting trends.
To understand the moving average, it's essential to grasp the concept of a queue data structure. A queue is a First-In-First-Out (FIFO) data structure, where elements are added to the end and removed from the front. In the context of the moving average, a queue can be used to store the last k values. When a new value arrives, it is added to the end of the queue, and the oldest value is removed from the front. This ensures that the queue always contains the last k values.
The time complexity of calculating the moving average is crucial in this problem. Since we need to calculate the average for each new value, the time complexity should be efficient enough to handle a large stream of data. We can achieve this by using a data structure that allows us to efficiently add and remove elements, such as a queue.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.