Real-Time Temperature Window Statistics
Google● MediumFULLTIMEONSITE INTERVIEWProblem statement
Process a finite sequence of operations for a real-time temperature stream with a fixed positive windowSize. Each operation is one of:
ADD <temperature>: append one integer reading.AVERAGE: report the exact average of the latestwindowSizereadings, or all readings so far when fewer exist.MAX: report the maximum over that same current window.
If a query occurs before any reading has been added, return "null". Otherwise, return an average as a reduced numerator/denominator string with a positive denominator, and return a maximum as its decimal integer string. Normalize a zero average to 0/1.
Return one string per AVERAGE or MAX operation, in query order. ADD operations produce no output.
Function
temperatureWindowStatistics(operations: String[], windowSize: int) → String[]Examples
Example 1
operations = ["AVERAGE","MAX","ADD 5","AVERAGE","MAX","ADD 1","ADD 9","AVERAGE","MAX","ADD 3","AVERAGE","MAX"]windowSize = 3return = ["null","null","5/1","5","5/1","9","13/3","9"]The first two queries have no readings. After adding 5, both statistics use [5]. After 5, 1, 9, the average is 5/1 and the maximum is 9. Adding 3 evicts 5, leaving [1,9,3].
Example 2
operations = ["ADD -4","ADD 2","AVERAGE","MAX","ADD -2","AVERAGE","MAX"]windowSize = 2return = ["-1/1","2","0/1","2"]The first window [-4,2] has average -1/1 and maximum 2. After adding -2, the active window is [2,-2], whose average is 0/1.
Constraints
1 <= operations.length <= 100000.1 <= windowSize <= 100000.- Every operation is exactly
ADD <temperature>,AVERAGE, orMAX. -1000000000 <= temperature <= 1000000000.- Use signed 64-bit arithmetic for the rolling sum.