Find the maximum average of any contiguous subarray of size k.

How to think about it

What the interviewer is really listening for is whether you spot that consecutive windows overlap. The phrase “best window of fixed size k” is the tell: k never changes, so two neighbouring windows of size k share k-1 elements. Recomputing each sum from scratch throws that overlap away — and throwing it away is the O(n·k) brute force they want you to move past.

So you do the arithmetic once and then maintain it. Sum the first k elements to seed the window. After that, each step is two operations: add the element entering on the right, subtract the element leaving on the left. The sum is now correct for the new window without touching the k-1 elements in the middle. Track the largest sum you have seen, and divide by k only at the very end — the maximum average lives at the same window as the maximum sum, since k is constant.

A worked example

def find_max_average(nums, k):
    # build the first window
    window_sum = sum(nums[:k])
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]   # +incoming, -outgoing
        best = max(best, window_sum)
    return best / k

print(find_max_average([1, 12, -5, -6, 50, 3], 4))   # window [12,-5,-6,50] wins
print(find_max_average([5, 5, 5, 5, 5], 2))           # every window ties
print(find_max_average([-1, -2, -3], 2))              # all-negative input
print(find_max_average([3, 1, 4, 1, 5, 9], 1))        # k=1 -> the max element

12.75
5.0
-1.5
9.0

Trace the first call. The seed window [1, 12, -5, -6] sums to 2. Sliding once adds 50 and drops 1, giving 51; sliding again adds 3 and drops 12, giving 42. The best sum is 51, so the answer is 51 / 4 = 12.75 — exactly the window [12, -5, -6, 50]. The last call with k=1 confirms the edge: a window of one element makes the maximum average just the maximum value, 9.0.