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. Although it looks better, the vector data structure in that case is not ideal.
Another approach is to use a double-entry queue: std::deque.
It perfectly suits the sliding window use case as we can pop and add elements both sides of the data structure in a very easy way (push_back/pop_front):
#include <iostream>
#include <deque>
/**
* MovingAverage maintains a fixed-size sliding window of the most recent prices
* and efficiently computes their average.
*/
class MovingAverage {
public:
explicit MovingAverage(int windowSize) : size_(windowSize), sum_(0.0) {}
// Adds a new price to the window and updates the sum accordingly
void addPrice(double price) {
prices_.push_back(price);
sum_ += price;
// Remove the oldest price if the window is too big
if (prices_.size() > size_) {
sum_ -= prices_.front();
prices_.pop_front();
}
}
// Returns the current moving average
double getMovingAverage() const {
if (prices_.empty()) return 0.0;
return sum_ / prices_.size();
}
private:
std::deque<double> prices_;
double sum_;
int size_;
};
int main() {
MovingAverage ma(3); // 3-day moving average
// Historical Microsoft stock prices
std::vector<double> msftPrices = {400.0, 402.5, 405.0, 410.0, 412.0, 415.5};
std::cout << "Microsoft 3-day Moving Average Calculation:\n" << std::endl;
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.getMovingAverage() << std::endl;
}
return 0;
}
It only adds/pops elements, then updates the sum, then the average.
In other terms: the time complexity 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 (with Vector vs Deque)
✅ Applies to Both std::vector<T> and std::deque<T>
| Syntax | Description | Notes / Gotchas |
|---|---|---|
container.begin() | Iterator to first element | Used in range-based loops and STL algorithms ([begin, end)) |
container.end() | Iterator past the last element | Non-inclusive range end |
container.size() | Number of elements | Type is size_t — beware of unsigned vs signed int bugs |
container.empty() | true if container is empty | Safer than size() == 0 |
container.front() | First element | ⚠️ Undefined if container is empty |
container.back() | Last element | ⚠️ Undefined if container is empty |
container.push_back(x) | Add x to the end | O(1) amortized for vector, always O(1) for deque |
container.pop_back() | Remove last element | ⚠️ Undefined if empty |
std::accumulate(begin, end, init) | Sum or fold values over range | From <numeric> — works on both vector and deque |
🟦 std::deque<T> Specific
| Syntax | Description | Notes / Gotchas |
|---|---|---|
container.push_front(x) | Add x to front | O(1); ideal for queues and sliding windows |
container.pop_front() | Remove first element | O(1); ⚠️ Undefined if empty |
container.erase(it) | Remove element at iterator | O(1) when removing from front/back |
✅ Random access ([i]) | Supported | Slightly slower than vector (more overhead under the hood) |
