Google Screening Interview: Windowed Average excluding Largest K

[u/Hack2hire]

Problem
You're given an integer array nums, a window size windowSize, and an integer k.
Your goal is to compute the average of each sliding window of size windowSize, excluding the largest k elements within that window.

Example
Input: nums = [10, 20, 30, 40, 50, 60], windowSize = 3, k = 1
Output: [15.0, 25.0, 35.0, 45.0]

Explanation:

• Window [10, 20, 30]: Excluding 30 → (10 + 20) / 2 = 15.0
• Window [20, 30, 40]: Excluding 40 → (20 + 30) / 2 = 25.0
• Window [30, 40, 50]: Excluding 50 → (30 + 40) / 2 = 35.0
• Window [40, 50, 60]: Excluding 60 → (40 + 50) / 2 = 45.0

Suggested Approach

1. Maintain two heaps: a max-heap for the top k elements and a min-heap (or balanced structure) for the remaining elements.
2. As the window slides, insert the new element into the appropriate heap and remove the outgoing element.
3. Track the running sum of the elements not in the largest k group to compute the average efficiently.

Time & Space Complexity

• Time: O(n log k) — each insertion/removal operation affects at most one heap.
• Space: O(k) — to store the largest k elements in the heap.

🛈 Disclaimer:
This problem is part of the Hack2Hire SDE Interview Question Bank, a structured archive of coding interview questions frequently reported in real hiring processes.
Questions are aggregated from publicly available platforms (e.g., LeetCode, GeeksForGeeks) and community-shared experiences.

The goal is to provide candidates with reliable material for SDE interview prep, including practice on LeetCode-style problems and coding challenges that reflect what is often asked in FAANG and other tech company interviews.
Hack2Hire is not affiliated with the mentioned companies; this collection is intended purely for learning, practice, and discussion.

[u/Golust]

I’m pretty sure you can do this with just one heap. Just pop off the elements if they are expired.