Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Finding MK Average

Explore how to implement a custom data structure that maintains a sliding window of the last m elements from a stream and computes the MK Average by excluding the smallest and largest k elements. Understand how to keep three balanced sorted lists, efficiently update them on element addition and removal, and calculate the average in constant time. This lesson deepens your skills in managing complex data structures for scalable, performant solutions.

We'll cover the following...

Statement

You are given two integers, m and k, and a stream of integers. Your task is to design and implement a data structure that efficiently calculates the MK Average for the stream.

To compute the MK Average, follow these steps:

  1. Stream length check: If the stream contains fewer than m elements, return -1 as the MK Average.

  2. Window selection: Otherwise, copy the last m elements of the stream to a separate container and remove the smallest k elements and the largest k elements from the container.

  3. Average calculation: Calculate the average of the remaining elements (rounded down to the nearest integer).

Implement the MKAverage class

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

  • void addElement(int num): Adds the integer num to the stream.

  • int calculateMKAverage() ...