Streaming Median for Live Events

In a Meta live monitoring pipeline, event counts arrive one integer at a time. Implement a data structure that supports inserting a new integer from the stream and returning the median of all values seen so far at any moment.

Formal Specification

Implement a function that processes a list of operations and returns the result for each median query.

• Input:
  • operations: a list of operations
  • Each operation is either:
    • {"op": "add", "value": x} where x is an integer
    • {"op": "median"}
• Output:
  • Return a list where each median query contributes the current median.
  • If the number of elements seen so far is odd, the median is the middle value.
  • If it is even, the median is the average of the two middle values.