Median of Every Fixed-Length Sliding Window in an Integer Array
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `nums` and a window length `k`, slide a window of exactly `k` consecutive elements across the array from left to right, one position at a time. For every window position, report the median of the `k` numbers currently inside the window.
The median of a window is its middle value after sorting the window in non-decreasing order. When `k` is odd it is the single middle element; when `k` is even it is the arithmetic mean of the two middle elements.
### Function Signature
```python
def window_medians(nums: list[int], k: int) -> list[float]:
```
### Rules
- The first window covers `nums[0..k-1]`, the second covers `nums[1..k]`, and so on, so there are exactly `len(nums) - k + 1` windows.
- Return the medians in window order: the median of the window that starts at index `i` is element `i` of the result.
- Return every median as a float, including whole numbers (for example `5.0`). Every median is exactly an integer or an integer plus one half, so no rounding is involved.
- Duplicate values count separately: the window `[2, 2, 9]` has median `2.0`.
### Constraints
- `1 <= k <= len(nums) <= 10^5`
- `-2^31 <= nums[i] <= 2^31 - 1`
- Values span the full signed 32-bit range, so the sum of the two middle elements of an even-sized window can fall outside the 32-bit range (its magnitude can reach about `2^32`). Compute the mean without 32-bit overflow. All values and sums stay well within `±2^53`.
### Examples
**Example 1**
- Input: `nums = [4, 1, 7, 3, 8, 2]`, `k = 2`
- Output: `[2.5, 4.0, 5.0, 5.5, 5.0]`
- Explanation: the windows are `[4, 1]`, `[1, 7]`, `[7, 3]`, `[3, 8]` and `[8, 2]`, and each median is the mean of its two values.
**Example 2**
- Input: `nums = [5, 2, 9, 2, 6]`, `k = 3`
- Output: `[5.0, 2.0, 6.0]`
- Explanation: the sorted windows are `[2, 5, 9]`, `[2, 2, 9]` and `[2, 6, 9]`.
**Example 3**
- Input: `nums = [3, -1, 4, 10]`, `k = 4`
- Output: `[3.5]`
- Explanation: the only window sorts to `[-1, 3, 4, 10]`, and the mean of `3` and `4` is `3.5`.
Overview: A coding problem that slides a window of fixed length k across an integer array and asks for the median of every window position, returned as floats in window order. It tests keeping the middle of a changing collection available as elements enter and leave, exact handling of even-sized windows, and overflow-safe averaging.
Read the full Microsoft Software Engineer interview experience this question came from