Katkat
Back

Compute sliding-window average excluding top k

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to maintain order statistics in a sliding window using balanced data structures or heaps to perform efficient removals and updates while excluding the top k elements.

Sliding Window Trimmed Average

You are given an array of integers nums, a window size w, and an integer k. You need to calculate the average of the elements in each sliding window of size w, excluding the k largest elements within that window. Assume w > k.

Implement the following function: def sliding_window_trimmed_average(nums: List[int], w: int, k: int) -> List[float]:

Input/Output

  • nums: List[int] (1 <= len(nums) <= 10^5, 0 <= nums[i] <= 10^6)
  • w: int (1 <= w <= len(nums))
  • k: int (0 <= k < w)
  • Return: A list of floats representing the trimmed average for each window.

Example 1

Input: nums = [10, 20, 30, 40, 50], w = 3, k = 1

  • Window 1 [10, 20, 30]: Top 1 is 30. Sum of remaining: 10+20=30. Avg = 15.0
  • Window 2 [20, 30, 40]: Top 1 is 40. Sum of remaining: 20+30=50. Avg = 25.0
  • Window 3 [30, 40, 50]: Top 1 is 50. Sum of remaining: 30+40=70. Avg = 35.0 Output: [15.0, 25.0, 25.0, 35.0] (Correction: [15.0, 25.0, 35.0])

Constraints & Edge Cases

  • Consider k=0 (standard sliding average).
  • Consider cases where window elements are duplicates.
  • Performance: Aim for better than O(w * n). A solution with O(n log w) is preferred.

Implementation Note

You may use two balanced BSTs (or multisets) to store elements currently in the window, split between the "k largest" elements and the "w-k" remaining elements, to keep track of the running sum dynamically.

Hints

Hint 1

Maintaining two multisets or heaps can help separate the k largest elements from the others as the window slides.

Hint 2

When moving the window, you need a way to efficiently remove the element that is sliding out, which suggests using a data structure that supports logarithmic removal.

Hint 3

Track two running sums: one for the 'k largest' set and one for the 'others' set to compute the average in O(1) after each update.

Follow-up questions

  • How would you modify your solution if the window size w could also change dynamically?
  • What are the trade-offs of using two heaps with lazy removal versus using a balanced BST (like a Treap or AVL tree)?
  • If the constraints on n were significantly smaller (e.g., n=1000), would a simpler brute-force approach be acceptable?