Finding MK Average

Finding MK Average

1. What is this problem about?

The Finding MK Average interview question is a high-level design task for a data stream. You need to implement a structure that stores the last $M$ numbers. When a query is made, you must:

1. Remove the $k$ smallest and $k$ largest elements from the last $M$ elements.
2. Calculate the average of the remaining $M - 2k$ elements. The challenge is to perform these updates and queries efficiently as new data arrives continuously.

2. Why is this asked in interviews?

Google and Amazon ask the Finding MK Average coding problem to test a candidate's ability to maintain a Sorted Sliding Window. It requires balancing three different sorted sets (Smallest, Middle, Largest) while handling deletions of elements that are no longer in the last $M$ positions. It evaluations your mastery of Ordered Set interview patterns.

3. Algorithmic pattern used

This problem is solved using Three Sorted Sets (or balanced BSTs) and a Queue.

1. Storage: Use a queue to track the order of the last $M$ elements.
2. Sets: Maintain three sorted sets: low (size $k$), mid (size $M-2k$), and high (size $k$).
3. Running Sum: Keep a variable sumMid to track the sum of elements in the mid set for $O(1)$ average calculation.
4. Balance: When a new element arrives or an old one expires, move elements between the sets to maintain their fixed sizes and ensure all elements in low < mid < high.

4. Example explanation

$M=6, K=1$. Stream: [10, 20, 30, 40, 50, 60]

• low: {10}, mid: {20, 30, 40, 50}, high: {60}.
• sumMid = 140. Average = $140 / 4 = 35$.
• Add 5: Queue pops 10. 5 is new.
• New state: low: {5}, mid: {20, 30, 40, 50}, high: {60}.
• Average remains 35.

5. Common mistakes candidates make

• Full Sorting: Sorting the last $M$ elements for every query ($O(M \log M)$), which is too slow for a high-frequency data stream.
• Incomplete Deletion: Failing to find and remove the specific instance of a number that just fell out of the sliding window.
• Balance Errors: Forgetting to update the sumMid when an element moves between sets during rebalancing.

6. Interview preparation tip

Master the use of MultiSets (C++) or multiple TreeMaps (Java). They are essential for sliding window problems where you need to track ranked statistics like the median or MK-average in $O(\log M)$ time.