Running Median Problem

Given a stream of integers, calculate and print the median after each new integer is added to the stream.

Output only the integer part of the median.

Example:

Input:

N = 5
Stream = [2, 3, 4, 1, 6]

Output:

2 2 3 2 3

Constraints:

0 ≤ N ≤ 10^5

1 ≤ ARR[i] ≤ 10^5

Time Limit: 1 sec

Question

Given a stream of integers, calculate and print the median after each new integer is added to the stream.

Output only the integer part of the median.

N = 5  
Stream = [2, 3, 4, 1, 6]

2 2 3 2 3

Accepted Answer

Calculate and print the median after each new integer is added to the stream.

Use two heaps - a max heap to store the smaller half of the numbers and a min heap to store the larger half.
Keep the sizes of the two heaps balanced or differ by at most 1 to get the median efficiently.
When a new integer is added, compare it with the current median and insert it into the appropriate heap.
If the sizes of the heaps differ by more than 1, rebalance them by moving an element from one heap to the other.
Calculate the median based on the sizes of the heaps and print the integer part of it.

Google Software Developer interview questions & answers