Hi everyone,\n\nI recently had a screening round with Google on 29th July 2024. The question was:-\n\n# ***QUESTION :-***\n\nGiven an big stream of numbers, you have to return the mean of the last K elements in the stream. For example:-\nfor ```arr = [50, 60, 70, 50, 100, 120, 80, 140]```(arr represents the order in which elements came in the stream) and ```K = 5```,\n\nFirstly 50 comes into the stream, mean = 50\nThen, 60 comes into the stream, mean = 55\nThen, 70 comes into the stream, mean = 60\nThen, 50 comes into the stream, mean = 57.5\nThen, 100 comes into the stream, mean = 66\nThen, 120 comes into the stream, mean = 80 (because 1st 50 is no longer in the last K elements)\nThen, 80 comes into the stream, mean = 84 (because 60 is no longer in the last K elements)\n\n**Answer:** First, I suggested a queue-based approach where, as we enqueue the most recent element, we keep track of the queue size and, if it exceeds K, we dequeue the last element and calculate the mean by iterating through the queue to find the sum and dividing it by the length of the queue, resulting in O(K) TC per enqueue. Interviewer asked to optimize it. I suggested an approach where I keep track of the current sum in ```curSum``` where, whenever an element is enqueued, I add it to ```curSum``` and whenever an element is dequeued, I subtract it from ```curSum``` and the average is simply ```curSum / len(queue)``` resulting in O(1) TC per enqueue and O(K) SC overall. Interviewer was satisfied and asked me to code it up, which I did.\n\n\n\n# ***FOLLOW UP:-***\n\nThe follow up was basically the same problem statement as above but whenever I calculate the mean of the last K elements, I had to exclude the largest X elements. For simplicity, the interviewer asked me to assume that the queue always contains K elements\n\n**Answer:** Initially, I suggested an approach where I maintain a ```sortedcontainers.SortedList``` (non-Python users might know it as an AVL Tree) alongside the queue where, whenever an element is enqueued, it is added to the ```SortedList``` and dequeued elements are removed from the same. I initially suggested to loop from the end of the ```sortedList``` and subtract the largest X elements from the ```curSum``` which I was maintaining for the current window. The mean would be ```(curSum - sum of largest x) / (k - x)``` which would result in O(X + log(K)) TC per enqueue and O(K) SC overall. The interviewer asked me to optimize. I suggested maintaining a variable ```sumLargestX``` to store the current sum. Whenever any value is enqueued, I binary search the position ```pos``` where the value is going to be in the ```sortedList``` using ```sortedList.bisect_left()``` (C++ and Java users might have to implement this). If the value is in top X, I add it to ```sumLargestX```. Now, I check if the value which is to be dequeued is in the top X or not. If it is, I subtract that value from ```sumLargestX```. Else, I subtract ```sortedList[k - x - 1]``` from ```sumLargestX```. Now, the mean is simply ```(curSum - sumLargestX) / (k - x)``` which results on O(log(K)) TC per enqueue and O(K) SC overall. Interviewer was satisfied and asked me to code it up, which I did.\n\nEDIT: Found a similar problem to the follow up: https://leetcode.com/problems/finding-mk-average/description/\n\n***Feedback:*** The interviewer was satisfied with the method and the code for both the initial question and the follow up. Recruiter reached out to me later in the day and told me the feedback was positive(clarified later to be a "Hire") and they are going to be scheduling the on-sites in mid to late August\n\n**UPDATE**: On-site interviews have been scheduled on 27th, 28th, 29th and 30th August

Hi everyone,\n\nI recently had a screening round with Google on 29th July 2024. The question was:-\n\n# QUESTION :-\n\nGiven an big stream of numbers, you have 