There is a problem called MKAverage:
This can be implemented in two ways:
- At add time, add an element to the Queue with the time complexity of O(1). At calculation time, sort m elements and return the average. This time complexity is O(mlogm).
- At add time, maintain sorted data structures. Add elements and delete elements at add time. This will have a time complexity of O(logm). At calculation time, return the average value of the already sorted data structure. This time complexity will be O(1).
This sorted data structure can vary based on the language you code. When using C language, a simple data structure can be BST. But to reduce time complexity, we can go for RBL trees or height-balanced BST.
In Java, there is TreeMap data structure and in C++ they called std::map, both are not completely the same, but they can be used for similar purposes.
In Python, there is a module called sortedcontainers, which has the functionality to maintain sorted dictionaries. This functionality can be used to solve this MKAverage problem.
As the problem says k smallest numbers, k largest numbers, and m number of members in the stream are to be considered. Accordingly, we can maintain a sorted dictionary for k smallest numbers, k largest numbers, and mid-sorted list.
When the element is added to the stream, perform add/delete operations on sorted lists based on the value of the element.
My solution for addElement functionality is:
add_to_sd and del_from_sd will have sorted list functionality:
