Stream Median, Mean and Maximum
Updated
Problem statement
Maintain all integers inserted into a stream and answer median, arithmetic mean and maximum queries. Values never expire.
Every row in operations has two integers:
[0, value]: insert one occurrence ofvalue.[1, 0]: query the median.[2, 0]: query the mean.[3, 0]: query the maximum.
For an odd number of values, the median is the middle sorted value. For an even number, it is the average of the two middle sorted values. Keep duplicate occurrences.
Return one number per query in its original order as a double[]. Insertion produces no output. Every query follows at least one insertion; return an empty array when there are no queries.
Build the data structure without ready-made heap or ordered-collection methods. Ordinary arrays and array-backed lists are allowed; implement heap push and pop yourself if you use heaps. Aim for amortized O(log n) insertion and O(1) queries after n inserted values.
Function
streamMedianStats(operations: int[][]) → double[]Examples
Example 1
operations = [[0,1],[1,0],[0,4],[1,0],[0,2],[1,0],[2,0],[3,0]]return = [1,2.5,2,2.3333333333333335,4]The medians after inserting 1, then 4, then 2 are 1, 2.5 and 2. The final values sort as [1,2,4], with mean 7/3 and maximum 4.
Example 2
operations = [[0,-2],[0,8],[1,0],[2,0],[3,0]]return = [3,3,8]The two sorted values are [-2,8]. Their median and mean are both 3, and their maximum is 8.
Example 3
operations = []return = []There are no operations, so there are no query results.
Constraints
0 <= operations.length <= 100000- Every operation has exactly two integers.
-1000000000 <= operations[i][j] <= 1000000000- Operation codes are from 0 through 3. A query has second integer 0.
- Every query follows at least one insertion.
- Returned means are compared with the platform’s usual floating-point tolerance.
More Akuna Capital Phone Screen questions
- Match Orders by Price and Arrival TimeOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Biased Coin: Probability of Exactly h HeadsPHONE SCREEN · Seen Nov 2026
- Positive Nth Root with Gradient DescentPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Two SumOA · PHONE SCREEN · Seen Sep 2026
- Maximum Value in a Binary TreePHONE SCREEN · Seen Sep 2026
- Tiered Expiring Item StorePHONE SCREEN · Seen Aug 2026
- Statistics for the Latest K ValuesPHONE SCREEN · Seen Nov 2025
- Remove Duplicates While Preserving OrderPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2025
- Sliding Window MaximumPHONE SCREEN · Seen Oct 2025
- Evaluate a PolynomialPHONE SCREEN · Seen Oct 2025
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Minimize Total Weight After HalvingAmazon · ONSITE INTERVIEW
- Meeting Rooms IIeBay · PHONE SCREENeBay interview questions
- Top K Largest Values from a StreamThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
- Generate Complete Inputs for a Supplied ClassifierGeneral Motors · ONSITE INTERVIEW
- Minimum Meeting Rooms Without a Sweep LineGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Dominant Index with Strict Doubling GapsGoogle · ONSITE INTERVIEWGoogle interview questions
- Defer Expenses to Preserve BalanceDRW · PHONE SCREENDRW interview questions