During a mathematics class, a teacher gives the students one integer at a time.

Design a classroom number tracker that stores each number and returns the median of all numbers given so far.

Median

To find the median, arrange the numbers from smallest to largest.

• If there is an odd number of values, the median is the middle value.
• If there is an even number of values, the median is the average of the two middle values.

Class

ClassroomNumberTracker()

Creates an empty number tracker.

Method Signatures

Add a Number

void addNumber(int value)

Parameters

• value: The next number given by the teacher.

Adds the given number to the tracker.

Get the Median

double getMedian()

Returns

The median of all numbers added so far.

Constraints

• -100,000 ≤ value ≤ 100,000
• At most 100,000 calls will be made to addNumber.
• getMedian is called only after at least one number has been added.
• Answers within 10-5 of the correct value are accepted.

Follow-Up Questions

1. How would you optimize the tracker if every number is between 0 and 100?
2. How would you optimize it if 99% of the numbers are between 0 and 100?

Examples

Example 1

ClassroomNumberTracker()

addNumber(value = 8)

addNumber(value = 14)

getMedian()

Returns 11.0.

The median is the average of 8 and 14, which is 11.0.

addNumber(value = 10)

getMedian()

Returns 10.0.

The ordered numbers are [8, 10, 14], so the middle value is 10.

Example 2

ClassroomNumberTracker()

addNumber(value = 5)

addNumber(value = 5)

addNumber(value = 20)

getMedian()

Returns 5.0.

The ordered numbers are [5, 5, 20], so the middle value is 5.