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.

Interview Answer

3 Answers


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

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

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

    LinkedList items = new LinkedList();

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

    public void add(int 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);


dux2 on May 17, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.