Solution: Find Median from a Data Stream
Let's solve the Find Median from a Data Stream problem using the Two Heaps pattern.
Statement
Create a data structure that can store a list of integers that can change in size over time and find the median from this dynamically growing list in constant time,
Implement a class, MedianOfStream, which should support the following operations:
Constructor(): This initializes the object of this class, which in turn creates the max and the min heap.
Insert Num(num): This adds an integer,
num
, to the data structure.Find Median(): This finds the median of all elements seen so far. If there are an even number of elements, return the average of the two middle values.
Constraints:
num
, where num
is an integer received from the data stream.There will be at least one element in the data structure before the median is computed.
At most,
calls will be made to the function that calculates the median.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.