Finding MK Average — Solution in Python, Java & C++
Finding MK Average solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Google.
Finding MK Average is a hard coding problem on heap, ordered set and queue, asked in Google interviews.
- Difficulty: Hard
- Topics: Heap, Ordered Set, Queue, Binary Indexed Tree
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Integers arrive in a stream. The MK average of the stream is computed from its last m elements:
- If fewer than
melements have arrived, the MK average is-1. - Otherwise take the last
melements, remove theksmallest and theklargest of them (as a multiset — equal values are separate elements). - The MK average is the average of the
m - 2kelements left, rounded down to an integer.
Write the class MKAverage:
MKAverage(int m, int k)starts an empty stream.void addElement(int num)appendsnumto the stream.int calculateMKAverage()returns the current MK average.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["MKAverage","addElement","addElement","addElement","addElement","calculateMKAverage","addElement","calculateMKAverage","addElement","calculateMKAverage","addElement","calculateMKAverage"]
[[5,1],[10],[20],[30],[40],[],[1],[],[100000],[],[2],[]]
Output: [null,null,null,null,null,-1,null,20,null,30,null,24]
Explanation: With 10, 20, 30, 40, 1 the window sorted is 1, 10, 20, 30, 40; dropping 1 and 40 leaves 10, 20, 30, average 20. After 100000 the window is 20, 30, 40, 1, 100000 and the middle three average 30. After 2 the middle is 2, 30, 40: 72 / 3 = 24.
Example 2
Input: ["MKAverage","addElement","addElement","calculateMKAverage","addElement","calculateMKAverage","addElement","calculateMKAverage","addElement","calculateMKAverage"]
[[3,1],[5],[5],[],[5],[],[6],[],[8],[]]
Output: [null,null,null,-1,null,5,null,5,null,6]
Explanation: Equal values are separate elements: from 5, 5, 5 one 5 is dropped at each end. The window 5, 6, 8 keeps only 6.
Constraints
3 <= m <= 10^51 <= k * 2 < m1 <= num <= 10^5At most 10^5 calls are made in total to addElement and calculateMKAverageThe sum of the window can exceed 2^31 - 1, so add it up in 64 bits; the average itself fits in 32 bits
Hints for Finding MK Average
Hint 1
Sorting the last
melements on every query is O(m log m) — too slow when bothmand the number of queries are 10^5.Hint 2
The middle sum is (sum of the
m - ksmallest) − (sum of theksmallest). So you need "sum of the c smallest elements of the window" quickly, while elements enter and leave.Hint 3
Values are at most 10^5: keep two Fenwick trees indexed by value — counts and sums — over the window (a queue tells you which element leaves). Walking down the count tree finds the value where the c-th smallest lies, and the sum tree gives everything below it. (Three ordered multisets — bottom k, middle, top k — also work.)
How to solve Finding MK Average
Keep the window in a queue and, over the value range 1..10^5, two Fenwick trees: how many window elements have each value, and their total. The sum of the c smallest elements is one top-down walk of the trees, and the MK average is the difference of two such sums divided by m - 2k.
Approach
addElement(num): pushnumto the queue and add (1, num) at positionnumin the count and sum trees. If the queue now holds more thanmelements, pop the oldest valuexand add (−1, −x) at positionx.smallest(c): walk the Fenwick tree from the highest power of two down, moving topos + stepwhenever the count stored there is< cremaining; collect the counts and sums passed. The walk ends atposwith fewer thancelements at values<= pos; the remaining ones all have valuepos + 1, so addremaining * (pos + 1).calculateMKAverage(): return-1while the queue holds fewer thanmelements; otherwise(smallest(m - k) - smallest(k)) / (m - 2k), rounded down.
Why it works
Sorted, the window's middle elements are positions k+1 … m-k, whose sum is the sum of the first m - k minus the sum of the first k. The Fenwick walk keeps the invariant that pos is the largest value with fewer than c elements at or below it, so the c-th smallest element has value exactly pos + 1 — counting the leftover copies at that value handles duplicates.
Complexity
- Time —
O(log V) per call, V = 10^5 - Space —
O(V + m)
Pitfalls
- The window sum reaches 10^10 — use 64-bit sums.
- Duplicates: the k smallest may cut through a run of equal values; take only part of that run (the
remaining * (pos + 1)term). - Only the last
melements count — evict the oldest one when the stream grows pastm.
Reference solution
Python
from collections import deque
class MKAverage:
SIZE = 1 << 17 # Fenwick trees over values 1..131072 (values are <= 10^5)
def __init__(self, m: int, k: int):
self.m, self.k = m, k
self.window = deque()
# Kept sparse (only positions an update touched): a fresh 131073-slot list
# per instance is most of the cost when many small streams are built.
self.cnt = {}
self.tot = {}
def _update(self, x, c):
i = x
cnt, tot = self.cnt, self.tot
while i <= self.SIZE:
cnt[i] = cnt.get(i, 0) + c
tot[i] = tot.get(i, 0) + c * x
i += i & -i
def _smallest(self, c): # sum of the c smallest values in the window
pos, acc, step = 0, 0, self.SIZE
cnt, tot = self.cnt, self.tot
while step:
nxt = pos + step
here = cnt.get(nxt, 0)
if nxt <= self.SIZE and here < c:
pos = nxt
c -= here
acc += tot.get(nxt, 0)
step >>= 1
return acc + c * (pos + 1) # the rest all equal pos + 1
def addElement(self, num: int) -> None:
self.window.append(num)
self._update(num, 1)
if len(self.window) > self.m:
self._update(self.window.popleft(), -1)
def calculateMKAverage(self) -> int:
if len(self.window) < self.m:
return -1
return (self._smallest(self.m - self.k) - self._smallest(self.k)) // (self.m - 2 * self.k)Java
class MKAverage {
private static final int SIZE = 1 << 17; // Fenwick trees over values 1..2^17
private final int m, k;
private final ArrayDeque<Integer> window = new ArrayDeque<>();
// Sparse (only positions an update touched): two 2^17-slot arrays per instance
// cost more than all the work when many small streams are built.
private final HashMap<Integer, long[]> tree = new HashMap<>(); // position -> {count, sum}
public MKAverage(int m, int k) {
this.m = m;
this.k = k;
}
private void update(int x, int c) {
for (int i = x; i <= SIZE; i += i & -i) {
long[] t = tree.computeIfAbsent(i, z -> new long[2]);
t[0] += c;
t[1] += (long) c * x;
}
}
private long smallest(int c) { // sum of the c smallest values in the window
int pos = 0;
long acc = 0;
for (int step = SIZE; step > 0; step >>= 1) {
int nxt = pos + step;
long[] t = tree.get(nxt);
long here = t == null ? 0 : t[0];
if (nxt <= SIZE && here < c) { pos = nxt; c -= here; acc += t == null ? 0 : t[1]; }
}
return acc + (long) c * (pos + 1); // the rest all equal pos + 1
}
public void addElement(int num) {
window.addLast(num);
update(num, 1);
if (window.size() > m) update(window.pollFirst(), -1);
}
public int calculateMKAverage() {
if (window.size() < m) return -1;
return (int) ((smallest(m - k) - smallest(k)) / (m - 2 * k));
}
}C++
class MKAverage {
static const int SIZE = 1 << 17; // Fenwick trees over values 1..2^17
int m, k;
deque<int> window;
// Sparse (only positions an update touched): two 2^17-slot arrays per instance
// cost more than all the work when many small streams are built.
unordered_map<int, long long> cnt, tot;
void update(int x, int c) {
for (int i = x; i <= SIZE; i += i & -i) { cnt[i] += c; tot[i] += (long long)c * x; }
}
long long smallest(int c) { // sum of the c smallest values in the window
int pos = 0;
long long acc = 0;
for (int step = SIZE; step > 0; step >>= 1) {
int nxt = pos + step;
auto it = cnt.find(nxt);
long long here = it == cnt.end() ? 0 : it->second;
if (nxt <= SIZE && here < c) { pos = nxt; c -= here; acc += tot[nxt]; }
}
return acc + (long long)c * (pos + 1); // the rest all equal pos + 1
}
public:
MKAverage(int m, int k) : m(m), k(k) {}
void addElement(int num) {
window.push_back(num);
update(num, 1);
if ((int)window.size() > m) { update(window.front(), -1); window.pop_front(); }
}
int calculateMKAverage() {
if ((int)window.size() < m) return -1;
return (int)((smallest(m - k) - smallest(k)) / (m - 2 * k));
}
};JavaScript
var MK_SIZE = 131072; // Fenwick trees over values 1..2^17 (values are <= 10^5)
var MKAverage = function(m, k) {
this.m = m;
this.k = k;
this.window = [];
this.head = 0;
this.cnt = new Int32Array(MK_SIZE + 1);
this.tot = new Float64Array(MK_SIZE + 1); // sums stay below 2^53, so doubles are exact
};
MKAverage.prototype.update = function(x, c) {
for (var i = x; i <= MK_SIZE; i += i & -i) { this.cnt[i] += c; this.tot[i] += c * x; }
};
MKAverage.prototype.smallest = function(c) { // sum of the c smallest values in the window
var pos = 0, acc = 0;
for (var step = MK_SIZE; step > 0; step >>= 1) {
var nxt = pos + step;
if (nxt <= MK_SIZE && this.cnt[nxt] < c) { pos = nxt; c -= this.cnt[nxt]; acc += this.tot[nxt]; }
}
return acc + c * (pos + 1); // the rest all equal pos + 1
};
MKAverage.prototype.addElement = function(num) {
this.window.push(num);
this.update(num, 1);
if (this.window.length - this.head > this.m) this.update(this.window[this.head++], -1);
};
MKAverage.prototype.calculateMKAverage = function() {
if (this.window.length - this.head < this.m) return -1;
return Math.floor((this.smallest(this.m - this.k) - this.smallest(this.k)) / (this.m - 2 * this.k));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 106 heap problems · the whole catalogue
Learn the technique: Heaps and Priority Queues · Queues and Deques