FastPrepRunning Stream Medians
Problems/Running Stream Medians

Running Stream Medians

Citadel logoCitadel● HardINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Citadel intern onsite interview, in a later superday round. The report names a well-known problem and says the solutions used min and max heaps. This version reports the median after each insertion. We added the batch interface, the limits, what happens when empty, and the examples. Our version is about 95% the same as the reported question.

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

Interview reports that mention this question

  • Citadel SWE Intern Later Rounds and Superday: 13 Experiences

Citadel interview experiences

  • Citadel Securities Quant Researcher Intern Loop: 1 Experience
  • Citadel Securities Research Engineer Interview: 1 Experience
  • Citadel Securities SWE Intern First Round: 2 Experiences
  • Citadel Securities Experienced SWE Interviews: 1 Experience
  • Citadel SWE Intern First-Round Questions: 20 Experiences
All Citadel interview questionsSee Citadel hiring insights
Saved
class Solution {
    public double[] runningMedians(int[] values) {
        // Write your code here.
    }
}
Checking account…