Median and Percentile in a Data Stream Hard · Topics · Company Tags · Hints
Design a data structure that continuously receives integers and can report the median of all numbers that have been added so far, on demand.
For an odd number of collected values, the median is the middle element when sorted. For an even count, the median is the arithmetic mean of the two middle elements (i.e., their sum divided by two).
The structure must expose two methods:
addNum(x): records the integer x.findMedian(): returns the current median. The return value should be treated as a floating‑point number, but when the result is an exact integer you may print it without a fractional part (see output format).Follow‑up: Modify the design so that it can also answer arbitrary percentile queries: findPercentile(p) with p an integer between 0 and 100 inclusive. Use the nearest‑rank rule: for n sorted elements, the p‑th percentile is the element at index ceil(p / 100 * n) - 1 (using 0‑based indexing). When p = 0, return the smallest value. Discuss how to keep operations efficient while supporting these additional queries.
The first line of input contains a single integer q, representing the number of operations to process.
Each subsequent line is an operation – either:
add x (insert integer x), ormedian (output the median of all inserted numbers so far).There will always be at least one add before any median command.
For every median query, print the result on its own line. If the value is a whole number, print it as an integer; otherwise print it with exactly one digit after the decimal point (e.g., 5.5).
Example 1:
Input:
6
add 3
add 8
median
add 10
median
median
Output:
5.5
8
8
Explanation: After the first two insertions, the sorted list is [3, 8]; median = (3 + 8) / 2 = 5.5. Adding 10 yields a sorted order of [3, 8, 10]; the middle element is 8. The second and third median queries both return 8.
Constraints:
1 ≤ q (number of operations) ≤ 200,000-1,000,000,000 ≤ x ≤ 1,000,000,000addNum and findMedian as fast as possible (ideally O(log n) for insertion and O(1) for median retrieval, where n is the current number of elements).