Streaming Median of Trade Prices
Updated
Problem statement
A trading desk watches a live stream of trade prices. Prices arrive one at a time, and at any moment someone may ask for the median of every price seen so far.
You are given operations, a list of operations to apply in order to a stream that starts empty. Each operation is one of:
["add", p]: a new price arrives.pis a positive integer written as a decimal string, such as"101".["median"]: report the median of all prices added so far.
To find the median of k prices, sort them as numbers. If k is odd, the median is the middle price. If k is even, it is the average of the two middle prices, which can end in .5. Every price counts, including repeated ones.
Return an array with one value for each "median" operation, in the order the operations appear.
Function
streamingMedian(operations: String[][]) → double[]Examples
Example 1
operations = [["add","100"],["add","103"],["median"],["add","97"],["median"],["add","120"],["add","101"],["median"]]return = [101.5,100.0,101.0]- After 100 and 103 there are two prices, so the median is their average:
(100 + 103) / 2 = 101.5. - After 97 the sorted prices are
[97, 100, 103]; the middle one is100. - After 120 and 101 the sorted prices are
[97, 100, 101, 103, 120]; the middle one is101.
Example 2
operations = [["add","7"],["median"],["add","7"],["add","3"],["median"]]return = [7.0,7.0]- One price: the median is
7. - Repeated prices all count. The sorted prices are
[3, 7, 7], so the median is7.
Example 3
operations = [["add","9"],["add","10"],["add","200"],["median"]]return = [10.0]- Prices are compared as numbers, not as text. The sorted prices are
[9, 10, 200], so the median is10.
Constraints
2 <= operations.length <= 5000- Each
operations[i]is either["add", p]or["median"]. - Each price
pis an integer from1to10^9, written in decimal digits with no leading zeros. - Between
1and500of the operations are"median", and the first operation is an"add".
More Xantium Phone Screen questions
Similar questions at other companies
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Alert Engine with a Repeat IntervalChronosphere · PHONE SCREEN
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions
- Design a LeaderboardBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Find Median from Data StreamSusquehanna International Group (SIG) · PHONE SCREENSusquehanna International Group (SIG) interview questions
- Find Median from Data StreamAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Find Median from Data StreamXPeng Motors · PHONE SCREEN
- Median of a Number StreamAdobe · PHONE SCREENAdobe interview questions
- Top K Largest Values from a StreamThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
- Fixed-K Kth Largest StreamAmazon Web Services · ONSITE INTERVIEWAmazon Web Services interview questions