Set That Picks in Turn
Implement a class RotatingSet, a set of integers whose pick method takes turns through the members in increasing order. Write these methods:
RotatingSet()starts empty, with nothing picked yet.insert(x)addsxto the set and returnstrue, or returnsfalseifxis already in the set.remove(x)removesxfrom the set and returnstrue, or returnsfalseifxis not in the set.pick()returns the smallest member that is greater than the value returned by the last successfulpick. If no member is greater, or if nothing has been picked yet, it returns the smallest member. If the set is empty it returns-1, and that does not change which value was picked last.count_members()returns how many values are in the set.
The last pick is remembered as a value, so it still counts after that value has been removed from the set. The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.
Example 1
RotatingSet()
insert(5) returns true
insert(2) returns true
insert(9) returns true
insert(5) returns false
pick() returns 2
pick() returns 5
pick() returns 9
pick() returns 2
remove(5) returns true
pick() returns 9
remove(9) returns true
pick() returns 2
count_members() returns 1
The picks go 2, 5, 9 and wrap back to 2. After 5 is removed the next member above 2 is 9. After 9 is removed nothing is above 9, so the pick wraps to 2.
Constraints
0 <= x <= 30- 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.