Middle Tracker
Implement a class MiddleTracker that holds a changing collection of numbers and can always say which one is in the middle. The same number may be held several times. Write these methods:
MiddleTracker()starts with no numbers.add(x)adds the numberx.remove(x)takes out one copy ofxand returnsTrue, or returnsFalseifxis not held.count_below(x)returns how many held numbers are strictly smaller thanx.get_middle()returns the middle number: with the held numbers lined up in order, the one in the middle position. With an even count there are two middle positions, and the smaller of the two numbers is returned. With no numbers it returns-1.
The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.
Example 1
MiddleTracker()
add(5)
add(1)
add(9)
get_middle() returns 5
add(7)
get_middle() returns 5
remove(5) returns true
get_middle() returns 7
count_below(8) returns 2
The numbers 5, 1, 9 have 5 in the middle. Adding 7 gives 1, 5, 7, 9 with the middle pair 5 and 7, so the answer is 5. After removing 5 the line is 1, 7, 9 and the middle is 7. Two of those are below 8.
Constraints
1 <= x <= 1000- Each test makes
1to40method calls after the constructor.
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.