Running Median of a Stream
Updated
Problem statement
Integers arrive in the order given by stream. After each insertion, return the median of all values received 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.
For this exercise, assume the result is an array of medians in arrival order. An empty stream returns an empty array. Duplicate and negative values are allowed.
Function
runningMedians(stream: int[]) → double[]Examples
Example 1
stream = [5,15,1,3]return = [5.0,10.0,5.0,4.0]The sorted prefixes have middle values 5, then 5 and 15, then 5, then 3 and 5.
Example 2
stream = [-1,-2,-3]return = [-1.0,-1.5,-2.0]Use an arithmetic mean for the even-length prefix; do not truncate -1.5.
Constraints
- For this exercise, assume
0 <= stream.length <= 10000. -10^9 <= stream[i] <= 10^9.- Each median is an integer or a half-integer and is represented as a double.
More PeopleStrong Phone Screen questions
- Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
- Level of the Minimum-Sum SubtreePHONE SCREEN · Seen Jan 2026
- Ceiling Value in a Sorted ArrayPHONE SCREEN · Seen Sep 2025
- Maximum Employee Salary for a CompanyPHONE SCREEN · Seen Sep 2025
- Valid ParenthesesPHONE SCREEN · Seen Sep 2025
- Number of ProvincesPHONE SCREEN · Seen May 2025
- Shortest Subarray with an Exact Target SumPHONE SCREEN · Seen May 2025
- Add Forward Linked-List Numbers Using RecursionPHONE SCREEN · Seen Oct 2021
- Build an Expression Tree from PostfixPHONE SCREEN · Seen Oct 2021
- Maximum Score from Deleting Neighboring ValuesPHONE SCREEN · Seen Oct 2021
Similar questions at other companies
- Meeting Rooms III: Most Booked RoomGoogle · ONSITE INTERVIEWGoogle interview questions
- Top K With a Deterministically Noisy Comparator (MLE)Mercor · ONSITE INTERVIEWMercor interview questions
- IPOTekion · PHONE SCREENTekion interview questions
- Smallest Range Covering Elements from K ListsSnap Inc. · PHONE SCREENSnap Inc. interview questions
- Employee Free TimeIDFC Bank · ONSITE INTERVIEWIDFC Bank interview questions
- Minimum Refueling StopsUber · ONSITE INTERVIEWUber interview questions
- IPOInMobi · PHONE SCREENInMobi interview questions
- Meeting Rooms IIIBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions