cppintermediate10 minutes

Build a Function to Calculate the Running Median of an Integer Stream

Write a function in C++ that processes a stream of integers and returns the median after each new number is added. The function should efficiently handle the insertion and calculation steps to provide medians dynamically.

Challenge prompt

Create a function named getRunningMedians that accepts a vector of integers representing a stream of incoming data. The function should return a vector of doubles representing the median of all the numbers seen so far after each insertion. Consider how to efficiently add new numbers and calculate medians when the data set is growing.

Guidance

• Use two heaps (a max heap and a min heap) to balance the lower and upper halves of the stream for efficient median calculation.
• Balance the heaps after each insertion to ensure their sizes differ by at most one.
• Calculate the median based on the root elements of the heaps once balanced.

Hints

• Keep the max heap storing the smaller half of numbers and the min heap storing the larger half.
• If the heaps have equal size, the median is the average of the two root elements; otherwise, it's the root of the heap with more elements.
• Push new numbers first into the max heap, then move the largest from max heap to min heap if needed to maintain order.

Starter code

#include <vector>
#include <queue>
using namespace std;

vector<double> getRunningMedians(const vector<int>& nums) {
    // Implement your function here
}

Expected output

[2, 1.5, 2, 2.5, 3]

Core concepts

heapspriority_queuevectormedian calculation

Challenge a Friend

Send this duel to someone else and see if they can solve it.