Google Interview Question: Design a class where you can ... | Glassdoor

## Interview Question

Software Engineer Interview

# Design a class where you can add elements, and return the

mean of the latest N elements.

0

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

Konst on Apr 18, 2014
6

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.

Aaron on Apr 24, 2014
0

public class AverageCalculator {
int N;
int sum = 0;
int itemCount = 0;

public AverageCalculator(int N)
{
this.N = N;
}

sum += num;

if (items.size() &gt; 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);
System.out.println(avg.getAverage());
System.out.println(avg.getAverage());
}

}

dux2 on May 17, 2014