Interview

In quantitative developer interviews, you’re often tested not just on algorithms, but on how they apply to real-world financial systems. One common scenario: cleaning overlapping time intervals from noisy market data feeds. This challenge maps directly to LeetCode 435: Non-Overlapping Intervals. In this article, we’ll solve it in C++ and explore why it matters in quant finance from ensuring data integrity to preparing time series for model training. How to solve the problem of non-overlapping intervals in C++?

Let’s dive into a practical problem that tests both coding skill and quant context.

1. Problem Statement

You’re given a list of intervals, where each interval represents a time range during which a market data feed was active. Some intervals may overlap, resulting in duplicated or conflicting data.

Your task is to determine the minimum number of intervals to remove so that the remaining intervals do not overlap. The goal is to produce a clean, non-overlapping timeline: a common requirement in financial data preprocessing.

Input: intervals = {{1,3}, {2,4}, {3,5}, {6,8}}
Output: 1

Explanation: Removing {2,4} results in non-overlapping intervals: {{1,3}, {3,5}, {6,8}}.

2. The Solution Explained

To remove the fewest intervals and eliminate overlaps, we take a greedy approach: we always keep the interval that ends earliest, since this leaves the most room for future intervals.

By sorting all intervals by their end time, we can iterate through them and:

• Keep an interval if it doesn’t overlap with the last selected one.
• Remove it otherwise.

This strategy ensures we keep as many non-overlapping intervals as possible and thus remove the minimum necessary.

What is the time and space complexity for this approach?

Sorting dominates the time complexity. While the actual iteration through the intervals is linear (O(n)), sorting the n intervals takes O(nlogn), and that becomes the bottleneck.

Although we process all n intervals, we do so in place without allocating any extra data structures. We use just a few variables (last_end, removed), so the auxiliary space remains constant. That’s why the space complexity is O(1) assuming the input list is already given and we’re allowed to sort it directly.

Now, let’s implement it in C++.

3. A C++ Implementation

Here is a C++ implementation of the solution:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// Greedy function to compute the minimum number of overlapping intervals to remove
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    // Sort intervals by end time
    sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });

    int removed = 0;
    int last_end = INT_MIN;

    for (const auto& interval : intervals) {
        if (interval[0] < last_end) {
            // Overlapping — must remov.e this one
            removed++;
        } else {
            // No overlap — update last_end
            last_end = interval[1];
        }
    }

    return removed;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {2, 4}, {3, 5}, {6, 8}};
    int result = eraseOverlapIntervals(intervals);
    cout << "Minimum intervals to remove: " << result << endl;
    return 0;
}

Let’s compile:

mkdir build
cmake ..
make

And run the code:

➜  build git:(main) ✗ ./intervals
Minimum intervals to remove: 1

4. Do It Yourself

To do it yourself, you can clone my repository to solve non-overlapping intervals in C++here:

https://github.com/cppforquants/overlappingintervals

Just git clone and run the compilation/execution commands from the Readme:

# Overlapping Intervals

The overlapping intervals problem for quant interviews.

## Build

```bash
mkdir build
cd build
cmake ..
make
```

## Run
```
./intervals

In the article of today, we talk about an interview question, simple on the surface, that’s given quite a lot as interview question for quants positions: the two sum problem.

What is the two sum problem in C++?

🔍 Problem Statement

Given a list of prices and a target value, return all the indices of price pairs in the list that sum up to the target.

Example:

nums = {2, 7, 11, 15}, target = 9  

Output: [{0, 1}] 

// because nums[0] + nums[1] = 2 + 7 = 9

1. The Naive Implementation in [math] O(n^2) [/math] Time Complexity

The simple way of doing is to loop through the list of prices twice to test every possible sums:

std::vector<std::pair<int, int>> twoSum(const std::vector<int>& nums, int target) {
    std::vector<std::pair<int, int>> results = {};
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i]+nums[j] == target){
                results.push_back({i, j});
            };
        };
    };
    return results;
}

This can be used with the list of prices given in our introduction:

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    auto results = twoSum(nums, target);

    for (const auto& pair: results) {
        std::cout << "Indices: " << pair.first << ", " << pair.second << std::endl;
    };


    return 0;
}

Running the code above prints the solution:

➜  build git:(main) ✗ ./twosum
Indices: 0, 1

The time complexity is [math] O(n^2) [/math] because we’re looping twice over the list of prices.

And that’s it, we’ve nailed the two sum problem in C++!

But…. is it possible to do better?

2. The Optimal Implementation in [math] O(n) [/math] Time Complexity

The optimal way is to use a hash map to store previously seen numbers and their indices, allowing us to check in constant time whether the complement of the current number (i.e. target - current) has already been encountered.

This reduces the time complexity from O(n²) to O(n), making it highly efficient for large inputs.

std::vector<std::pair<int, int>> twoSumOptimized(const std::vector<int>& nums, int target) {
    std::vector<std::pair<int, int>> results = {};
    std::unordered_map<int, int> pricesMap;
    for (int i = 0; i < nums.size(); ++i) {

        int diff = target - nums[i];

        if (pricesMap.find(diff) != pricesMap.end()){
            results.push_back({pricesMap[diff], i});

        } 
        pricesMap[nums[i]] = i;

    };
    return results;
}

And we can run it on the exact same example but this time, it’s O(n) as we loop once and hash maps access/storing time complexity are O(1):

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    auto results = twoSumOptimized(nums, target);

    for (const auto& pair: results) {
        std::cout << "Indices: " << pair.first << ", " << pair.second << std::endl;
    };

    return 0;
}

3. A Zoom on Unordered Hash Maps in C++

In C++, std::unordered_map is the go-to data structure for constant-time lookups. Backed by a hash table, it allows you to insert, search, and delete key-value pairs in average O(1) time. For problems like Two Sum, where you’re checking for complements on the fly, unordered_map is the natural fit.

Here’s a quick comparison with std::map:

Use unordered_map when:

• You don’t need the keys to be sorted
• You want maximum performance for insert/lookup
• Hashing the key type is efficient and safe (e.g. int, std::string)

Let me know if you’d like to add performance tips, custom hash examples, or allocator benchmarks.

The code for the article is available here:

https://github.com/cppforquants/twosumprices

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:

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. 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.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 (with Vector vs Deque)

✅ Applies to Both std::vector<T> and std::deque<T>

🟦 std::deque<T> Specific