📘

Find Median from Data Stream

Design a data structure that supports adding integers and finding the median efficiently.

Input: operations as add,num or find_median separated by semicolons. Output median results with 1 decimal place.

Input:

add,1;add,2;find_median;add,3;find_median

Output:

1.5
2.0

Reasoning:

Initially, two numbers are added to the data structure: 1 and 2.
When find_median is called, the median of the current data stream [1, 2] is calculated as the average of the two middle numbers, which is $\frac{1+2}{2} = 1.5$ .
Then, the number 3 is added to the data stream, making it [1, 2, 3].
When find_median is called again, the median of the current data stream [1, 2, 3] is the middle number, which is $2.0$ .

Editor

Python 3.13.1

0/0

Run code to see test results.