Running Stream Medians
Updated
Problem statement
Read the integers in values from left to right. After inserting each value into the stream, report the median of all values read so far.
For an odd number of values, the median is the middle value in sorted order. For an even number, it is the arithmetic mean of the two middle values. Duplicate values count separately. Return one median for each input value, in order. An empty stream returns an empty array.
Maintain the stream incrementally rather than sorting every prefix again.
Function
runningMedians(values: int[]) → double[]Examples
Example 1
values = [1,2,3]return = [1,1.5,2]The sorted prefixes are [1], [1,2], and [1,2,3]. Their medians are 1, (1 + 2) / 2 = 1.5, and 2.
Example 2
values = [5,2,10,0]return = [5,3.5,5,3.5]The two-value prefix has median (2 + 5) / 2 = 3.5. After inserting 10, the middle value is 5. After inserting 0, the sorted values are [0,2,5,10], whose median is again 3.5.
Constraints
0 <= values.length <= 100000.-10^9 <= values[i] <= 10^9.
More Citadel Onsite Interview questions
- Maximize Workday EarningsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Changes for Palindromic BlocksOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Removal PoolONSITE INTERVIEW · Seen Sep 2026
- Centered K-by-K Submatrix SumsONSITE INTERVIEW · Seen Aug 2026
- Search Suggestions with a Prefix TreeONSITE INTERVIEW · Seen Aug 2026
- Traverse Interior Matrix Cells in Row-Major OrderONSITE INTERVIEW · Seen Aug 2026
- Time-Based Key-Value StorePHONE SCREEN · ONSITE INTERVIEW · Seen Feb 2026
- 2048 Simulation and Board CodecONSITE INTERVIEW · Seen Jan 2026
- Cancellable Priority Task QueueONSITE INTERVIEW · Seen Jan 2026
- Dynamic Weighted SamplingONSITE INTERVIEW · Seen Jan 2026
Similar questions at other companies
- Top K With a Deterministically Noisy Comparator (MLE)Mercor · ONSITE INTERVIEWMercor interview questions
- Find Median from Data StreamAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Find Median from Data StreamBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP 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
- Fixed-K Kth Largest StreamGoogle · ONSITE INTERVIEWGoogle interview questions
- Find Median from Data StreamSusquehanna International Group (SIG) · PHONE SCREENSusquehanna International Group (SIG) interview questions
- Progressive Banking SystemAirbnb · OAAirbnb interview questions
- Find Median from Data StreamIntuit · OAIntuit interview questions
- Cloud Compute Credits SystemCoinbase · OACoinbase interview questions