Finding MK Average

Finding MK Average is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Two Heaps for Median Finding subpattern.

Problem statement

You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:

- If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.

- Remove the smallest k elements and the largest k elements from the container.

- Calculate the average value for the rest of the elements rounded down to the nearest integer.

Implement the MKAverage class:

- MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.

- void addElement(int num) Inserts a new element num into the stream.

- int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.

Example 1:

Input ["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"] [[3, 1], [3], [1], [], [10], [], [5], [5], [5], []] Output [null, null, null, -1, null, 3, null, null, null, 5]

Explanation MKAverage obj = new MKAverage(3, 1); obj.addElement(3); // current elements are [3] obj.addElement(1); // current elements are [3,1] obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist. obj.addElement(10); // current elements are [3,1,10] obj.calculateMKAverage(); // The last 3 elements are [3,1,10]. // After removing smallest and largest 1 element the container will be [3]. // The average of [3] equals 3/1 = 3, return 3 obj.addElement(5); // current elements are [3,1,10,5] obj.addElement(5); // current elements are [3,1,10,5,5] obj.addElement(5); // current elements are [3,1,10,5,5,5] obj.calculateMKAverage(); // The last 3 elements are [5,5,5]. // After removing smallest and largest 1 element the container will be [5]. // The average of [5] equals 5/1 = 5, return 5

Constraints:

- 3 <= m <= 105

- 1 < k2 < m

- 1 <= num <= 105

- At most 105 calls will be made to addElement and calculateMKAverage.

Topics and companies

Topics: Design, Queue, Heap (Priority Queue), Data Stream, Ordered Set.

Reported in interviews at Google.

How to practise Finding MK Average on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log m) per addElement and calculateMKAverage. Each insertion/removal in multiset is O(log m), and balancing the sets after each operation is O(log m) amortized. The initial build when the first m elements are added is O(m log m), but this happens only once. time and O(m) for storing the last m elements in the deque and the three multisets (left, mid, right), each holding at most m elements in total. space.

Open Finding MK Average in the code editor, or read the Finding MK Average editorial for a worked solution with its approach and complexity analysis.

Where Finding MK Average sits in the DSA pattern sheet

Problems related to Finding MK Average

Other problems that use the same Two Heaps for Median Finding and Heap (Priority Queue) Patterns techniques:

Preparing this workspace.