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 lastNprices.
Constraints:
- The moving average must be updated in O(1) time per price.
- Handle the case where fewer than
Nprices 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:
| Day | Price (USD) |
|---|---|
| 1 | 400.0 |
| 2 | 402.5 |
| 3 | 405.0 |
| 4 | 410.0 |
| 5 | 412.0 |
| 6 | 415.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.53. 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.5The 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 / Function | Description | Notes / Gotchas |
|---|---|---|
container.begin() | Returns iterator to the first element | Use in loops and STL algorithms like accumulate or sort |
container.end() | Returns iterator past the last element | Not included in iteration ([begin, end)) |
container.size() | Returns number of elements | Type is size_t (unsigned) — be careful when comparing with int |
container.empty() | Returns true if container has no elements | Safer than checking size() == 0 |
container.front() | Accesses the first element | Undefined behavior if the container is empty |
container.back() | Accesses the last element | Also undefined on empty containers |
container.push_back(x) | Appends x to the end | O(1) amortized for vector, always O(1) for deque |
container.pop_back() | Removes last element | Unsafe if empty |
container.erase(it) | Removes element at iterator it | O(N) for vector, O(1) for deque |
std::accumulate(begin, end, init) | Computes sum (or custom op) over range | Defined in <numeric>; use for totals or averages |
std::vector<T> v(n, init) | Creates a vector of size n with all elements initialized to init | Useful for fixed-size buffers |
std::deque<T> | Double-ended queue: fast push_front and pop_front | Slower than vector for random access, but great for sliding windows |
🧠 Bonus Tips:
- Use
autoin range-based loops to avoid type headaches: cppCopierModifierfor (auto val : vec) { ... } - Use
v[i]only when you’re surei < 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).
