Find Median from Data Stream

Explore how to design a data structure in Go that stores integers from a dynamic data stream and finds the median in constant time. Learn to implement insert and median retrieval methods using heap data structures to handle continuous input efficiently.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

Design a data structure that stores a dynamically changing list of integers and can find the median in constant time, $O(1)$ , as the list grows. To do that, implement a class named MedianOfStream with the following functionality:

Constructor(): Initializes an instance of the class.
insertNum(int num): Adds a new integer num to the data structure.
findMedian(): Returns the median of all integers added so far.

Note: The median is the middle value in a sorted list of integers.
For an odd-sized list (e.g., $[4, 5, 6]$ ), the median is the middle element: $5$ .
For an even-sized list (e.g., $[2, 4, 6, 8]$ ), the median is the average of the two middle elements: $(4 + 6) / 2 = 5$ .

Constraints:

$-10^5 \leq$ num $\leq 10^5$ , 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, $500$ calls will be made to the function that calculates the median.

usercode > main.go

package main

// Tip: You may use some of the code templates provided
// in the support files

type MedianOfStream struct {
    // Write your code here
}

func (this* MedianOfStream) Init() {
    // Write your code here
}

// insertNum() should take a number and store it
func (this* MedianOfStream) InsertNum(num int) float64 {
    // Replace this placeholder return statement with your code
	return -99.99
}

// findMedian() should return the median of the stored numbers
func (this* MedianOfStream) FindMedian() float64 {
    // Replace this placeholder return statement with your code
    return -99.99
}

Find Median from Data Stream

Find Median from Data Stream

Statement

Examples

Understand the problem

Figure it out!

Try it yourself