CareerCup

We can use a circular queue (size of n) with some modification. Modification is:
When the overflow condition arise we will remove the first element from the queue and put the newly come element in the queue. When the input stream ends the queue will contain just only last n elements. This will give O(n) time complexity.

Use a max-heap, then the first N elements are the last N values of the given data range. Extract these N values and average them. Insertion is O(lg N), Extract is also O(lg N). We can take care of duplicate while inserting new elements.

Use fix size queue (size = n), and push the data from one end pop the data from the other end when the queue is full. We want to maintain the total and update total as well so that it takes constant time to compute the average
if the average value is required everytime new element come (in the streamming applications)

template<typename T>
class AvgQueue {
	queue q;
	T         total;
public:
	AvgQueue(): total(0);
	void push(T v) {
		T old = 0;
		if (q.size() == n) {
			old = q.front();
			q.pop();
		}
		q.push(v);
		total += v - old;
	}
	T get() {
		return (q.empty()) ? 0 : total / q.size();
	}
}

Use stack for best perorformance. The last n values would be basically the the first n values in stack.. just pop..

The question apparently is not very clear here. If it is a static data, you just take the last n element and compute the average.

If the data is coming in a stream, and you always want to know the avg of the last n elements, you need to use a queue as eugene mentioned.

Once you have computed the avg of the n numbers, when a new number comes in:

1. De-queue the first element and compute the new average as: ((n*avg - value of first element) + value of new element)/n

2. En-queue the new element.

we may use doubly link list ... In this case we may access last n numbers by starting list from end till n-1 times...
and for avg just add them and avg=sum/n

I think the best data structure is simple an Array. Say the array is A.

public void printAvg(int N, in[] A) {
	int[] temp = new int[N];
	int sum = 0;
	int i = -1;
	for(i = 0; i < N && i < A.length; ++i) {
		temp[i] = A[i];
		sum += A[i];
	}
	if(i < N) {
		System.out.println((sum*1.0)/A.length);
		return;
	}
	else {
		System.out.println((sum*1.0)/N);
	}

	int idx = 0;
	for(int j = N; j <  A.length; ++j) {
		sum = sum-temp[idx]+A[j];
		System.out.println((sum*1.0)/N);
		temp[idx++] = A[j];
		if(idx == N)
			idx = 0;
	}
}

I think since the input is list, we need two pointers. Move 1st pointer to nth node and 2nd is at head. Now move both 1st and 2nd pointer one node at a time till 1st pointer reaches the tail. Now take the n nodes from the 2nd pointer till tail and calculate average

Why not an ArrayList

we can go for arraylist. Suppose the array length is 40 and when we call the function to calculate avg. We will subtract 15 from array.length which will be 25 and from 25 index we will go further and calculate the avg. This will also give O(n).

We can use a ArraList<Integer> which will take inputs dynamically , secondly we can use a HashMap <k,v> here the key will be numbers like 1,2 ,3 .... N and value will be the integer that is inputted . bothe ArraList and HashMap access is same 0(1) . Both works.

Queue of size n and a variable storing SUM. Queue[0 to (n-1)] elements will store the last numbers in FIFO order and when ever a number is entered SUM will be modified accordingly. In this way getting avg in O(1) operation