Track the Running Twice-Median of a Live Price Feed
Implement runningTwiceMedian
A trading desk receives a live feed of prices. You are given a log of events: record adds a price to the feed, and query asks for the median of every price recorded so far. Report each median doubled (for an odd count that is twice the middle price; for an even count it is the sum of the two middle prices) so the answers are always integers, and return them in order.
Re-sorting the entire history on every query gets slower as the feed grows. Keeping the smaller half of the prices in a max-heap and the larger half in a min-heap puts the median right at the two roots, so a query is instant and each new price only costs a heap insertion.
Example 1:
Input: ops = ["record","record","query","record","query","record","query"], values = [8,2,0,6,0,10,0]
Output: [10,12,14]
Example 2:
Input: ops = ["record","query"], values = [7,0]
Output: [14]
Example 3:
Input: ops = ["record","record","query"], values = [-5,5,0]
Output: [0]
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ ops.length ≤ 100, and values.length equals ops.length - ●
Each op is "record" (add values[i] to the feed) or "query" (report the current median, doubled) - ●
-1000 ≤ values[i] ≤ 1000 for every "record"; the values entry of a "query" is ignored - ●
At least one "record" appears before every "query" - ●
The median of an even number of prices is the average of the two middle prices; report it doubled so the answer is always an integer
ops =
values =