Category:

Interview

moving average interview
Interview

Calculate Moving Average in C++ in O(1) – An Interview-Style Problem

by Clement Daubrenet

A classic interview question in quantitative finance or software engineering roles is:
“Design a data structure that calculates the moving average of a stock price stream in O(1) time per update.”.
How to calculate the moving average in C++ in an optimal way?

Let’s tackle this with a focus on Microsoft (MSFT) stock, although the solution is applicable to any time-series financial instrument. We’ll use C++ to build an efficient, clean implementation suitable for production-grade quant systems.

1. Problem Statement

Design a class that efficiently calculates the moving average of the last N stock prices.

Your class should support:

  • void addPrice(double price): Adds the latest price.
  • double getAverage(): Returns the average of the last N prices.

Constraints:

  • The moving average must be updated in O(1) time per price.
  • Handle the case where fewer than N prices have been added.

Implement this in C++.

You will need to complete the following code:

#include <vector>


class MovingAverage {
public:
    explicit MovingAverage(int size);
    void addPrice(double price);
    double getAverage() const;
private:
    std::vector<double> buffer;
    int maxSize;
    double sum = 0.0;
};

Imagine the following historical prices for Microsoft stocks:

DayPrice (USD)
1400.0
2402.5
3405.0
4410.0
5412.0
6415.5

And assume we want to calculate the moving average of prices on 3 days, everyday, as a test.

2. A Naive Implementation in O(N)

Let’s start with a first implementation using `std::accumulate`.

It’s defined as follow in the C++ documentation:
“std::accumulate Computes the sum of the given value init and the elements in the range [first, last)“. The last iterator is not included in the operation. This is a half-open interval, written as.

std::accumulate is O(N) in time complexity.

Let’s use it to calculate the MSTF stock price moving average in C++:

#include <iostream>
#include <vector>
#include <numeric>

class MovingAverage {
public:
    explicit MovingAverage(int size) : maxSize(size) {}

    void addPrice(double price) {
        buffer.push_back(price);
        if (buffer.size() > maxSize) {
            buffer.erase(buffer.begin()); // O(N)
        }
    }

    double getAverage() const {
        if (buffer.empty()) return 0.0;
        double sum = std::accumulate(buffer.begin(), buffer.end(), 0.0); // O(N)
        return sum / buffer.size();
    }

private:
    std::vector<double> buffer;
    int maxSize;
};

int main() {
    MovingAverage ma(3); // 3-day moving average
    std::vector<double> msftPrices = {400.0, 402.5, 405.0, 410.0, 412.0, 415.5};

    for (size_t i = 0; i < msftPrices.size(); ++i) {
        ma.addPrice(msftPrices[i]);
        std::cout << "Day " << i + 1 << " - Price: " << msftPrices[i]
                  << ", 3-day MA: " << ma.getAverage() << std::endl;
    }

    return 0;
}

Every new day the moving average is re-calculated from scratch, not ideal! But it gives the right results:

➜  build ./movingaverage 
Day 1 - Price: 400, 3-day MA: 400
Day 2 - Price: 402.5, 3-day MA: 401.25
Day 3 - Price: 405, 3-day MA: 402.5
Day 4 - Price: 410, 3-day MA: 405.833
Day 5 - Price: 412, 3-day MA: 409
Day 6 - Price: 415.5, 3-day MA: 412.5

3. An optimal Implementation in O(1)

Let’s now do it in an iterative way and just add the value to the former sum to calculate a performant moving average in C++:

#include <iostream>
#include <vector>

class MovingAverage {
public:
    explicit MovingAverage(int size)
        : buffer(size, 0.0), maxSize(size) {}

    void addPrice(double price) {
        sum -= buffer[index];        // Subtract the value being overwritten
        sum += price;                // Add the new value
        buffer[index] = price;       // Overwrite the old value
        index = (index + 1) % maxSize;

        if (count < maxSize) count++;
    }

    double getAverage() const {
        return count == 0 ? 0.0 : sum / count;
    }

private:
    std::vector<double> buffer;
    int maxSize;
    int index = 0;
    int count = 0;
    double sum = 0.0;
};

int main() {
    // Example: 3-day moving average for Microsoft stock prices
    MovingAverage ma(3);
    std::vector<double> msftPrices = {400.0, 402.5, 405.0, 410.0, 412.0, 415.5};

    for (size_t i = 0; i < msftPrices.size(); ++i) {
        ma.addPrice(msftPrices[i]);
        std::cout << "Day " << i + 1
                  << " - Price: " << msftPrices[i]
                  << ", 3-day MA: " << ma.getAverage()
                  << std::endl;
    }

    return 0;
}

This time, no re-calculation, each time a new price gets in, we add it and average it on the fly.

It’s O(1).

Let’s run it:

➜  build ./movingaverage
Day 1 - Price: 400, 3-day MA: 400
Day 2 - Price: 402.5, 3-day MA: 401.25
Day 3 - Price: 405, 3-day MA: 402.5
Day 4 - Price: 410, 3-day MA: 405.833
Day 5 - Price: 412, 3-day MA: 409
Day 6 - Price: 415.5, 3-day MA: 412.5

The same results but way faster!

And you pass your interview to calculate the moving average in C++ in the most performant way.

4. Common STL Container Member Functions & Tips Learned

Syntax / FunctionDescriptionNotes / Gotchas
container.begin()Returns iterator to the first elementUse in loops and STL algorithms like accumulate or sort
container.end()Returns iterator past the last elementNot included in iteration ([begin, end))
container.size()Returns number of elementsType is size_t (unsigned) — be careful when comparing with int
container.empty()Returns true if container has no elementsSafer than checking size() == 0
container.front()Accesses the first elementUndefined behavior if the container is empty
container.back()Accesses the last elementAlso undefined on empty containers
container.push_back(x)Appends x to the endO(1) amortized for vector, always O(1) for deque
container.pop_back()Removes last elementUnsafe if empty
container.erase(it)Removes element at iterator itO(N) for vector, O(1) for deque
std::accumulate(begin, end, init)Computes sum (or custom op) over rangeDefined in <numeric>; use for totals or averages
std::vector<T> v(n, init)Creates a vector of size n with all elements initialized to initUseful for fixed-size buffers
std::deque<T>Double-ended queue: fast push_front and pop_frontSlower than vector for random access, but great for sliding windows

🧠 Bonus Tips:

  • Use auto in range-based loops to avoid type headaches: cppCopierModifierfor (auto val : vec) { ... }
  • Use v[i] only when you’re sure i < v.size() — or you’ll hit UB (undefined behavior).
  • Avoid vector.erase(begin()) in performance-critical code — it’s O(N).
  • Prefer std::vector::reserve() if you’re going to fill it all at once (not needed in circular buffer use).
0 comments