I gave my 2nd Google interview today, below was the question asked -

It was a two part question.
Part 1 -
You are getting the readings of server latencies. You need to return the avg latency for the last K values.
For example -
Latencies - 10, 20, 30, 80, 30, 20, 80, 80
K = 5
O/P - 34 , 36, 48, 58
You can assume you start your output after once you have K values.

My solution -
This looked pretty simple, i told my approach with a deque sliding window. Keep adding at the back and remove from the front.
T(n) - O(n)
S(n) - O(k)

Interviewer was good with this approach and he did not ask me to code this and said we can just move to part 2. Here he modified the question in a twisted way, that took me 5 mins to understand, but it was basically -

You still have the same latencies coming in, but now you have window size of K and there is a value X. You need to ignore the top X values when calculating the avg.

For ex -
Latencies -60, 70, 30, 100, 30, 20, 40, 80
K = 5
X = 2
O/p - 36 [60+30+30+20+40], 38 [70+30+30+20+40]

So, your size now is K+X, and while getting the avg we need to ignore the top X values in that window and then return the avg.

This is where it got messed up. I thought using Heaps is the right approach, but how to remove the front of the sliding window was where i got stuck. I was thinking of how to do it, but then interviewer said that probably heap is not the right approach and you should look for some other data structure. I tried but i could not think of what else i can use and we were already 30 mins past. So he said just start with the brute force approach and then i talked about the BF approach which was having the some sliding window and sort it each time it slides and get the sum of top X and subtract it from the total sum of the window and return the result.

PS - I thought of using heap with deque, so using the deque i will remove element from the heap but interviewer said probably heap is not the right choice here what else can you think of and thus I thought maybe this will not give the best result.

After that i coded it up, i think the implementation was fine. The time was almost up, he gave me a change to think about more optimised solution but i could not think of it. And thats how it ended.
I think I am screwed. What will be the optimised answer here? I looked over in chatgpt, and it said the same solution as my BF approach and there was one more using the heap. Will I get a NH or LH?