Google

  www.google.com
Work in HR? Unlock Free Profile

Google Software Engineer Interview Question

"Design a class where you can add elements, and return the mean of the latest N elements."
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 3,025 Google Interview Reviews

Answers & Comments

0
of 0
votes
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
5
of 5
votes
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
of 1
vote
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());
    }

}
- dux2 on May 17, 2014

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.