## Interview Question

## Interview Answer

3 Answers

Start the class with a list with 0 in it. Each time the user adds an element, store the addition of that element plus the previous element in your list. So basically each element in your list is the sum of all the previously added elements. For instance if the user adds these elements [1,2,5,3,9,10] Your class would store: [0,1,3,8,11,20,30]. Now getting the average of the last n elements is just (the last element in your list minus the k-th element in your list where k = length of the list - n - 1) all divided by n. For instance, if n was 4 for the above list, the average would be (30 - 3) / 4 = 6.75 = (10 + 9 + 3 + 5) / 4. This would be O(1) insert O(1) mean, and O(n) for space complexity. It works because there is a simple equation for mean (sum of all numbers/how many numbers). So if you keep storing the sum of all the previous numbers, then the sum of the last n numbers is just the sum of all the numbers minus the sum of all the numbers that came before the n-th number.

public class AverageCalculator { int N; int sum = 0; int itemCount = 0; LinkedList<Integer> items = new LinkedList<>(); public AverageCalculator(int N) { this.N = N; } public void add(int num) { items.addLast(num); sum += num; if (items.size() > N) { int popped = items.removeFirst(); sum -= popped; } } public double getAverage() { if (items.size() == 0) throw new RuntimeException(); return (double)sum / items.size(); } public static void main(String[] args) { AverageCalculator avg = new AverageCalculator(4); avg.add(1); avg.add(2); avg.add(3); avg.add(4); System.out.println(avg.getAverage()); avg.add(5); System.out.println(avg.getAverage()); } }

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

O(logN) solution for add, remove, find and mean ops: Augment red-black tree so that each node x contains the size of its subtree (including x). This allows to determine the smallest i-th element by traversing the tree from root downwards (by looking at the subtree sizes). the mean elements is the N/2-th smallest element