Trending (Moving) Average on Integer Stream

Given an integer N and an infinite stream of integers, implement a data structure/class that supports ingesting the next integer and returning the average of the most recent N integers (if fewer than N numbers have been seen, average over all seen so far). Requirements Operation: next(x): ingest a new integer x and return the current trending average. Expected time: O(1) per next. Expected space: O(N). Follow-up If the user wants more recent numbers to have higher weight, design a weighted average computation without storing the entire history (e.g., EWMA) and provide the update formula. Constraints 1 <= N <= 1e5 Stream length can be large (e.g., up to 1e6 events) Integers fit in 32-bit signed range. Example N = 3, stream: 1, 10, 3, 5 next(1) = 1.0 next(10) = (1+10)/2 = 5.5 next(3) = (1+10+3)/3 = 4.6666667 next(5) = (10+3+5)/3 = 6.0 Example Input 3 4 1 10 3 5 Output 1.0 5.5 4.6666666667 6.0