CareerCup

Use a ring buffer (circular queue) of type Message of size 5000*60*10 which is 3000000B or 3MB. The memory footprint will be 3MB*sizeof(Message) so that gives us upper limit of 100MB (string ticker are no more than 4B and fixed length for int64/double).
Maintain a rolling sum (type double) and every time adding a stock price, add it to sum and subtract the last purged value.
Simply return sum/Total entries

I think it will look something like this, please let me know if we can save memory further

public enum StockPriceMath {
    INSTANCE;
    private long INTERVAL = 600000000; // microseconds since each second we get 50000 updates, we can't do it in miliseconds
    private volatile HashMap<String, Queue> priceMap = new ConcurrentHashMap<String, Queue<Message>>();
    private volatile HashMap<String, Long> sumMap = new ConcurrentHashMap<String, Integer>();
    public void updatePrice(Message message) {
        Queue<Message> tickerQueue;
        // if we have seen the ticker before
        if priceMap.contains(message.ticker) {
            tickerQueue = priceMap.get(ticker);
        }
        else {
            // new ticker
            tickerQueue = new ConcurentLinkedQueue<Message>(600000000);
            tickerQueue.insert(message);
            priceMap.set(message.ticker, tickerQueue)
            sumMap.set(message.ticker, 0)
        }
        long sum = sumMap.get(message.ticker);
        while (message.timestamp - tickerQueue.peek().timestamp > INTERVAL) {
            sum = sum - tickerQueue.pop().price;
        }
        sum += message.price;
        sumMap.set(message.ticker, sum);
    }
    
    public long get10minuteAverage(String ticker) {
        Queue<Message> tickerQueue = priceMap.get(ticker);
        long sum = sumMap.get(message.ticker);
        return sum / tickerQueue.size();
    }
}

I used Enum istead of class to make it singleton since this will be used in a high frequency environment and singleton will help us to maintain concurrency.

Also I do not know if something like concurrentLinkedQueue exists, i just assumed it did.

Looks like the implementation of Observer design pattern

We can do a custom solution based on the average stock price for this symbol ie if the stock price is between $1-10
I would keep a longlong variable each time new price comes in multiple by 1000 so we keep four decimal places then add it to longlong variable. At the end divide it by 3M this will give us average with decimal place moved right by 4. Now divide it double 1000.0 this will give us average with correct decimal place.

You can use the observer pattern and bucketize the processed messages. And put these buckets in a Fixed length Map. The length of the Map depends on the time resolution. The key of the map is the time rounded off to time resolution. For example, if we take a time resolution of 1 minutes, then we will have a Map of size 10 and the key is number of minutes from epoch.

Processed_Message {
double priceSum;
int numMessage;
};

Map<Long, ProcessedMessage> eventMap;

void addEvent(Message msg) {
    long minute = getMinutes(msg.timeStamp);
    ProcessedMessage cur = eventMap.get(minute);
    if ( cur == null) {
        //check for size and remove element if greater then 10
       //Add the element as processedMessage
    }
    else {
       //Add this element to processMessage
   }
}

long getAverage() {
    //Get the max 10 elements from the map
    //Get the total price sum and total elements by adding them
    // Divide them and return averge
}

To get better results, increase the time resolution, say to seconds.

new_avg = (old_avg*n + number)/(n+1)

I don't know if I get it right. Basically, we can store the first value of the price we have, and for the rest, we can calculate p(i) - p(first) and cumulate them. Then we won't get a very large number. And the final result can be aquired by calculating first_price + total / times since the first price we get is used as the benchmark.

average = ((average * count) + price) / (count + 1);

no need to store all msg, just calculate average for each second and the number of counts for that second, store 600 of them. Way less memory

no need to store all msg, just calculate average for each second and the number of counts for that second, store 600 of them. Way less memory

Have a circular queue of size 600 slots so that we just store average values of per second in each slot ( or we can go very fine(5000*60*10) = 3 million) slots for each symbol.

And another buffer of all incoming messages for each symbol for 1 second.
Now every time a message comes for a particular symbol, then we just keep collecting the prices and count the number of times it has come in this second and store both. So store as a tuple:
(sum_price: sum(prices),
num_times: N )

After each second just take this tuple and put it in the circular queue for that symbol. And purge the last bucket (10mins + 1st sec).

When asked for the average price, just return the sum of all the sum_price values and divide that by sum of all the num_times value. That will give you the average price.

If we want better accuracy, then just make the circular queue of size 3 million rather than 600.