Problem Statement

Shared context — identical in all four questions in this set. The scenario and artifacts below are exactly the same across all four questions; only the Question section changes. If you have already read them in another question, skip straight to Question . Numbers arrive one at a time in an endless stream. After each arrival you must be able to report the median of all numbers seen so far, quickly. You cannot store the data sorted and re-sort on every insert (too slow), and you cannot assume the values are bounded. Question A naive approach keeps a sorted array and inserts each new number into place, then reads the middle. What are the per-insert and per-median-query costs, and why is this too slow for a long stream? Provided Artifacts Stream of unbounded numbers, median required after each arrival. Hint: a max-heap (low half) and a min-heap (high half). Constraints No re-sorting the whole dataset per insert. Median of an even count = average of the two middle values. Keep the two heap