Class Tracker With Nearest5

Khan Academy may need to inspect the five learning-event values closest to a target while new values continue arriving. Implement the behavior of a Tracker that supports efficient insertion and nearest-value queries.

For this coding exercise, expose the behavior through one function, tracker_operations(operations), which internally maintains the tracker. Each operation is an object with op, either add or nearest5, and an integer value.

Requirements

1. add(value) inserts one occurrence of value; duplicate values must be preserved.
2. nearest5(value) returns up to five stored numbers ordered by increasing absolute distance from value.
3. If two numbers have the same distance, return the smaller number first.
4. Return one result list for every nearest5 operation, in query order.
5. Use a data structure that keeps insertion and query performance logarithmic in the number of stored values. An AVL tree or another balanced ordered structure with subtree sizes is appropriate.

Formal Specification

Input: operations, a list of operation objects with string field op and integer field value.

Output: A list of integer lists. Each inner list contains at most five stored values for one nearest5 operation.