Please use Laptop/Desktop or any other large screen for the Mock Interview Session.
You need to be Logged In to Start the Interview
Median Finder from Number Stream
The median is the middle element in a sorted list of integers. If the list contains an even number of elements, the median is the average of the two middle elements.
For instance,
[4, 5, 6] has median 5
[7, 8] has median (7 + 8) / 2 = 7.5
Create a data structure that supports the following operations:
insertNumber(int val)- Add an integer value from the input stream.getMedian()- Retrieve the median of all numbers added so far.
Examples
insertNumber(5)
insertNumber(10)
getMedian() // Returns 7.5
insertNumber(3)
getMedian() // Returns 5
Constraints
- Each input number will be between -10,000 and 10,000 inclusive.
- There will be at most 50,000 calls to
insertNumberandgetMediancombined.