Finding MK Average

Hard
2096.

Finding MK Average

HardQueueHeap (Priority Queue)Ordered SetBinary Indexed TreeDesignGoogle

Finding MK Average is a hard coding problem on heap, ordered set and queue, asked in Google interviews.

Integers arrive in a stream. The MK average of the stream is computed from its last m elements:

  1. If fewer than m elements have arrived, the MK average is -1.
  2. Otherwise take the last m elements, remove the k smallest and the k largest of them (as a multiset — equal values are separate elements).
  3. The MK average is the average of the m - 2k elements left, rounded down to an integer.

Write the class MKAverage:

  • MKAverage(int m, int k) starts an empty stream.
  • void addElement(int num) appends num to 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^5
  • 1 <= k * 2 < m
  • 1 <= num <= 10^5
  • At most 10^5 calls are made in total to addElement and calculateMKAverage
  • The sum of the window can exceed 2^31 - 1, so add it up in 64 bits; the average itself fits in 32 bits
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} k
 */
var MKAverage = function(m, k) {
    
};

/**
 * @param {number} num
 * @return {void}
 */
MKAverage.prototype.addElement = function(num) {
    
};

/**
 * @return {number}
 */
MKAverage.prototype.calculateMKAverage = function() {
    
};

Sign in to run your own test cases

Sign in

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.

Problem statement

Integers arrive in a stream. The MK average of the stream is computed from its last m elements:

  1. If fewer than m elements have arrived, the MK average is -1.
  2. Otherwise take the last m elements, remove the k smallest and the k largest of them (as a multiset — equal values are separate elements).
  3. The MK average is the average of the m - 2k elements left, rounded down to an integer.

Write the class MKAverage:

  • MKAverage(int m, int k) starts an empty stream.
  • void addElement(int num) appends num to 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^5
  • 1 <= k * 2 < m
  • 1 <= num <= 10^5
  • At most 10^5 calls are made in total to addElement and calculateMKAverage
  • The 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

  1. Hint 1

    Sorting the last m elements on every query is O(m log m) — too slow when both m and the number of queries are 10^5.

  2. Hint 2

    The middle sum is (sum of the m - k smallest) − (sum of the k smallest). So you need "sum of the c smallest elements of the window" quickly, while elements enter and leave.

  3. 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

  1. addElement(num): push num to the queue and add (1, num) at position num in the count and sum trees. If the queue now holds more than m elements, pop the oldest value x and add (−1, −x) at position x.
  2. smallest(c): walk the Fenwick tree from the highest power of two down, moving to pos + step whenever the count stored there is < c remaining; collect the counts and sums passed. The walk ends at pos with fewer than c elements at values <= pos; the remaining ones all have value pos + 1, so add remaining * (pos + 1).
  3. calculateMKAverage(): return -1 while the queue holds fewer than m elements; 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 m elements count — evict the oldest one when the stream grows past m.

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