Round 1
Questions: 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.
Part 2:
You still have the same latencies coming in, but now you have a window size of K and there is a value X. You need to ignore the top X values when calculating the avg.
For example -
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.
Candidate's Approach
For Part 1, the candidate proposed using a deque sliding window to keep adding values at the back and removing from the front. The time complexity is O(n) and space complexity is O(k).
For Part 2, the candidate initially thought of using heaps but struggled with how to remove the front of the sliding window. After discussing the challenges, the candidate suggested a brute force approach that involves maintaining a sliding window, sorting it each time it slides, and then calculating the sum of the top X values to subtract from the total sum of the window.
Interviewer's Feedback
The interviewer was supportive of the candidate's approach for Part 1 and did not require coding for that part. However, for Part 2, the interviewer indicated that heaps might not be the best choice and encouraged the candidate to think of alternative data structures.