Coding questions · Cognitiv

Maintain a Streaming Median

This question evaluates understanding of streaming algorithms and dynamic data structures for maintaining order statistics, along with analysis of time complexity and memory trade-offs.

You are designing a component that receives integers one at a time and must return the current median after each update.

Example:

After processing [2, 3, 1], the median is 2.
After processing one more value to form [2, 3, 1, 4], the median is (2 + 3) / 2 = 2.5.

Implement a data structure with two operations:

add(x): insert an integer
getMedian(): return the median of all inserted values so far

Discuss the time complexity of your approach.

Follow-up: if the full input array is available up front and you want to avoid extra auxiliary space, how would you compute the median while minimizing additional memory usage?

Streaming Median

Process add and median operations using two heaps, returning medians for median queries.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.