FastPrep
Problem · Sliding Window

Sliding Window Average Excluding the Largest K Values

Learn this problem
● MediumGoogle logoGooglePHONE SCREEN
See Google hiring insights

Problem statement

Given an integer array values, an integer windowSize, and a non-negative integer k, compute one average for every contiguous window of length windowSize.

Within each window, ignore the k elements with the largest values, counting equal values as separate elements. Average the remaining windowSize - k elements, and return the averages in left-to-right window order.

The inputs are guaranteed to satisfy 0 <= k < windowSize <= values.length. When k = 0, ignore no elements and average the entire window.

Follow-up

How would the approach change if the input were very large or arrived as a stream?

Function

slidingWindowAverageExcludingLargestK(values: int[], windowSize: int, k: int) → double[]

Examples

Example 1

values = [1,3,2,6,4]windowSize = 3k = 1return = [1.5,2.5,3.0]

The windows are [1,3,2], [3,2,6], and [2,6,4]. Removing the largest value from each leaves [1,2], [3,2], and [2,4], whose averages are 1.5, 2.5, and 3.0.

Example 2

values = [2,-2,4]windowSize = 2k = 0return = [0.0,1.0]

Because k = 0, both values remain in each window. The averages of [2,-2] and [-2,4] are 0.0 and 1.0.

Example 3

values = [5,5,1,2]windowSize = 3k = 2return = [1.0,1.0]

In [5,5,1], both occurrences of 5 are ignored. In [5,1,2], 5 and 2 are ignored. The only retained value is 1 in both windows.

More Google problems

drafts saved locally
public double[] slidingWindowAverageExcludingLargestK(int[] values, int windowSize, int k) {
    // write your code here
}
values[1,3,2,6,4]
windowSize3
k1
expected[1.5,2.5,3.0]
checking account