Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Implement the MovingAverage class:
MovingAverage(int size) Initializes the object with the size of the window size.double next(int val) Returns the moving average of the last size values of the stream.Example 1:
Input [ "MovingAverage ", "next ", "next ", "next ", "next "] [[3], [1], [10], [3], [5]] Output [null, 1.0, 5.5, 4.66667, 6.0]
Explanation MovingAverage movingAverage = new MovingAverage(3); movingAverage.next(1); // return 1.0 = 1 / 1 movingAverage.next(10); // return 5.5 = (1 + 10) / 2 movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3 movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3
Constraints:
1 <= size <= 1000-105 <= val <= 105104 calls will be made to next.program main
use :: moving_average_mod
implicit none
type(MovingAverage) :: moving_average
integer :: i, n
integer, parameter :: size = 3
! Example 1
write (*, "(A)") "Example 1:"
write (*, "(A)") "Input:"
write (*, "(A)") "[ 'MovingAverage ', 'next ', 'next ', 'next ', 'next ']"
write (*, "(A)") "["
do i = 1, size
write (*, "(I0)", advance="no") i
if (i < size) then
write (*, "(A)", advance="no") ", "
end if
end do
write (*, *) "]"
write (*, "(A)") "Output:"
write (*, "(A)") "[null, 1.0, 5.5, 4.66667, 6.0]"
write (*, "(A)") ""
moving_average = MovingAverage(size)
do i = 1, size
call moving_average%next(i)
end do
write (*, "(F8.5)") moving_average%next(3)
write (*, "(F8.5)") moving_average%next(10)
write (*, "(F8.5)") moving_average%next(3)
write (*, "(F8.5)") moving_average%next(5)
! Example 2
write (*, "(A)") "Example 2:"
write (*, "(A)") "Input:"
write (*, "(A)") "[ 'MovingAverage ', 'next ', 'next ', 'next ', 'next ']"
write (*, "(A)") "["
do i = 1, size
write (*, "(I0)", advance="no") i
if (i < size) then
write (*, "(A)", advance="no") ", "
end if
end do
write (*, *) "]"
write (*, "(A)") "Output:"
write (*, "(A)") "[null, 1.0, 5.5, 4.66667, 6.0]"
write (*, "(A)") ""
moving_average = MovingAverage(size)
do i = 1, size
call moving_average%next(i)
end do
write (*, "(F8.5)") moving_average%next(3)
write (*, "(F8.5)") moving_average%next(10)
write (*, "(F8.5)") moving_average%next(3)
write (*, "(F8.5)") moving_average%next(5)
end program main
module moving_average_mod
implicit none
private
public :: MovingAverage
type :: MovingAverage
private
integer :: size
real, allocatable :: buffer(:)
contains
procedure :: next => next_moving_average
end type MovingAverage
contains
function next_moving_average(this, val) result(res)
class(MovingAverage), intent(inout) :: this
integer, value :: val
real :: res
if (.not. allocated(this%buffer)) then
allocate(this%buffer(this%size))
this%buffer = 0.0
end if
this%buffer(1:this%size-1) = this%buffer(2:this%size)
this%buffer(this%size) = val
res = sum(this%buffer) / real(this%size)
end function next_moving_average
end module moving_average_modtemp.f95:2:11:
2 | use :: moving_average_mod
| 1
Fatal Error: Cannot open module file āmoving_average_mod.modā for reading at (1): No such file or directory
compilation terminated.
module MovingAverage
implicit none
type :: MovingAverage
integer :: size
real(kind=8), allocatable :: values(:)
real(kind=8) :: sum
contains
procedure :: next
end type MovingAverage
interface MovingAverage
module procedure :: createMovingAverage
end interface MovingAverage
contains
function createMovingAverage(size) result(movingAverage)
integer, intent(in) :: size
type(MovingAverage) :: movingAverage
allocate(movingAverage%values(size))
movingAverage%size = size
movingAverage%sum = 0.0d0
end function createMovingAverage
function next(movingAverage, val) result(average)
class(MovingAverage), intent(inout) :: movingAverage
integer, intent(in) :: val
real(kind=8) :: average
integer :: i
movingAverage%sum = movingAverage%sum - movingAverage%values(1) + val
movingAverage%values(1:size-1) = movingAverage%values(2:size)
movingAverage%values(size) = val
average = movingAverage%sum / size
end function next
end module MovingAverage
program main
use MovingAverage
implicit none
integer :: i, n
integer, allocatable :: values(:)
type(MovingAverage) :: movingAverage
! read input
read(*,*) n
allocate(values(n))
do i = 1, n
read(*,*) values(i)
end do
! create moving average object
movingAverage = createMovingAverage(n)
! calculate moving average for each value
do i = 1, n
write(*,*) next(movingAverage, values(i))
end do
end program main
temp.f95:4:25:
4 | type :: MovingAverage
| 1
Error: MODULE attribute of āmovingaverageā conflicts with PROCEDURE attribute at (1)
temp.f95:10:7:
10 | end type MovingAverage
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:12:27:
12 | interface MovingAverage
| 1
Error: Unexpected INTERFACE statement in CONTAINS section at (1)
temp.f95:13:25:
13 | module procedure :: createMovingAverage
| 1
Error: MODULE PROCEDURE at (1) must be in a generic module interface
temp.f95:14:7:
14 | end interface MovingAverage
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:16:8:
16 | contains
| 1
Error: Unexpected CONTAINS statement in CONTAINS section at (1)
temp.f95:20:27:
20 | type(MovingAverage) :: movingAverage
| 1
Error: GENERIC attribute conflicts with RESULT attribute in āmovingaverageā at (1)
temp.f95:22:32:
22 | allocate(movingAverage%values(size))
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type
temp.f95:23:23:
23 | movingAverage%size = size
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type
temp.f95:24:23:
24 | movingAverage%sum = 0.0d0
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type
temp.f95:28:29:
28 | class(MovingAverage), intent(inout) :: movingAverage
| 1
Error: Derived type āmovingaverageā at (1) is being used before it is defined
temp.f95:33:23:
33 | movingAverage%sum = movingAverage%sum - movingAverage%values(1) + val
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type
temp.f95:34:23:
34 | movingAverage%values(1:size-1) = movingAverage%values(2:size)
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type
temp.f95:35:23:
35 | movingAverage%values(size) = val
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type
temp.f95:37:33:
37 | average = movingAverage%sum / size
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type
temp.f95:27:31:
27 | function next(movingAverage, val) result(average)
| 1
Error: Symbol āmovingaverageā at (1) has no IMPLICIT type; did you mean āaverageā?
temp.f95:18:60:
18 | function createMovingAverage(size) result(movingAverage)
| 1
Error: Result āmovingaverageā of contained function ācreatemovingaverageā at (1) has no IMPLICIT type
temp.f95:43:9:
43 | use MovingAverage
| 1
Fatal Error: Cannot open module file āmovingaverage.modā for reading at (1): No such file or directory
compilation terminated.
from collections import deque
class MovingAverage:
def __init__(self, size: int):
self.queue = deque()
self.maxSize = size
self.sum = 0.0
def next(self, val: int) -> float:
if len(self.queue) == self.maxSize:
self.sum -= self.queue.popleft()
self.queue.append(val)
self.sum += val
return self.sum / len(self.queue)
The algorithm uses a queue to maintain a sliding window of the last size values of the stream. When a new value is added, the algorithm checks the size of the queue. If it equals size, the oldest value is removed from the front of the queue by updating the sum and popping it. Then, the new value is added to the back of the queue, and the sum is updated. The average is returned by dividing the sum by the number of values currently in the queue. The time complexity of the next function is O(1).
#include <queue>
using namespace std;
class MovingAverage {
public:
queue<int> q;
int maxSize;
double sum;
MovingAverage(int size) {
maxSize = size;
sum = 0;
}
double next(int val) {
if (q.size() == maxSize) {
sum -= q.front();
q.pop();
}
q.push(val);
sum += val;
return sum / q.size();
}
};
The algorithm uses a queue to maintain a sliding window of the last size values of the stream. When a new value is added, the algorithm checks the size of the queue. If it equals size, the oldest value is removed from the front of the queue by updating the sum and popping it. Then, the new value is added to the back of the queue, and the sum is updated. The average is returned by dividing the sum by the number of values currently in the queue. The time complexity of the next function is O(1).