Compute sliding-window average excluding top k
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an integer array `nums`, a window size `windowSize = w`, and an integer `k`.
For every contiguous subarray (window) of length `w` as the window slides from left to right by 1, compute the **average of the elements after removing the largest `k` elements in that window**.
More precisely, for each window `nums[i .. i+w-1]`:
1. Identify the `k` largest values in the window (if there are ties, removing any `k` elements among the maximum values is fine).
2. Remove those `k` elements.
3. Compute the arithmetic mean of the remaining `w - k` elements.
Return the list of averages in order, one per window.
## Input
- `nums`: array of integers
- `w`: window size (`1 <= w <= len(nums)`)
- `k`: number of largest elements to exclude (`0 <= k < w`)
## Output
- An array `ans` of length `len(nums) - w + 1`, where `ans[i]` is the average for window starting at index `i`.
## Notes / Clarifications
- Use floating-point averages (do not floor/round unless specified).
- Constraints are not provided; propose an algorithm more efficient than recomputing from scratch for each window.
## Example
If `w = 3`, `k = 1`, and `nums = [1, 3, 2, 6, 4]`:
- Window `[1,3,2]` remove max `3` → average of `[1,2]` = `1.5`
- Window `[3,2,6]` remove max `6` → average of `[3,2]` = `2.5`
- Window `[2,6,4]` remove max `6` → average of `[2,4]` = `3.0`
Return `[1.5, 2.5, 3.0]`.
Quick Answer: This question evaluates a candidate's understanding of sliding-window algorithms, order-statistics maintenance, and data-structure techniques for incremental aggregation when excluding the largest k elements from each window.
You are given an integer array nums, a window size w, and an integer k. For every contiguous subarray of length w, remove the largest k elements from that window and compute the arithmetic mean of the remaining w - k elements. Return the averages for all windows as the window slides from left to right by one position. If there are ties among the largest values, removing any k of them is acceptable because the resulting remaining-sum is unchanged.
Constraints
- 1 <= len(nums) <= 200000
- 1 <= w <= len(nums)
- 0 <= k < w
- -10^9 <= nums[i] <= 10^9
- Answers are evaluated with a small floating-point tolerance
Examples
Input: ([1, 3, 2, 6, 4], 3, 1)
Expected Output: [1.5, 2.5, 3.0]
Explanation: The windows are [1,3,2], [3,2,6], and [2,6,4]. Removing the largest element gives remaining averages 1.5, 2.5, and 3.0.
Input: ([5, -1, 3], 2, 0)
Expected Output: [2.0, 1.0]
Explanation: Since k = 0, no elements are removed. The averages are (5 + -1) / 2 = 2.0 and (-1 + 3) / 2 = 1.0.
Input: ([4, 4, 4, 1, 1], 3, 2)
Expected Output: [4.0, 1.0, 1.0]
Explanation: For each window, keep only the smallest 1 element. The kept values are 4, 1, and 1.
Input: ([-5, -2, -3], 3, 2)
Expected Output: [-5.0]
Explanation: There is only one window. Removing the two largest values, -2 and -3, leaves -5.
Input: ([7], 1, 0)
Expected Output: [7.0]
Explanation: This is the smallest valid input: one window of size 1 with no removals.
Hints
- Removing the largest k elements is equivalent to keeping the smallest w - k elements. Can you maintain their sum efficiently?
- Consider coordinate compression plus Fenwick trees for counts and sums so you can query the sum of the smallest t elements in O(log n).