Rolling CSAT Tracker
Problem statement
Maintain customer-satisfaction records in a rolling time window. Each recorded conversation has a globally unique string ID, an integer score from 1 through 5, and its original integer timestamp.
Process operations in order. The current clock starts at 0. A time-bearing operation advances it to its supplied timestamp; all supplied timestamps are nondecreasing. A record is active exactly when its original timestamp is at least currentTime - windowSize. The left boundary is included.
["RECORD", id, score, timestamp]: advance the clock, discard expired records, and insert this previously unused ID. Numeric cells are decimal strings.["AVERAGE", currentTime]: advance the clock, discard expired records, and append the active-score average as the exact reduced fractionnumerator/denominator. Include denominator1for an integer average. AppendEMPTYwhen no records are active.["UPDATE", id, newScore]: use the current clock to discard expired records, then replace the score only if this ID is active. Keep its original timestamp and order. An unknown or expired ID is ignored and never revived. This operation does not advance the clock or append a result.["PERCENTILE", p]: use the current clock to discard expired records and append the requested active-score percentile as a decimal score string, orEMPTYwhen the window is empty. This operation does not advance the clock.
For the percentile follow-up, use the nearest-rank convention: sort the m active scores in nondecreasing order and select the 1-based rank ceil(p * m / 100), with 1 <= p <= 100. This exercise uses an observed score even when the middle two values differ.
Return the results of all AVERAGE and PERCENTILE operations in encounter order.
Function
rollingCsat(operations: String[][], windowSize: int) → String[]Examples
Example 1
operations = [["RECORD","a","5","1"],["RECORD","b","3","3"],["AVERAGE","3"],["AVERAGE","6"]]windowSize = 5return = ["4/1","4/1"]At time six, timestamp one is exactly the inclusive left boundary and remains active. The earlier integer-window convention would incorrectly omit it.
Example 2
operations = [["AVERAGE","2"],["RECORD","a","4","2"],["AVERAGE","2"]]windowSize = 3return = ["EMPTY","4/1"]Equal timestamps are valid; an empty window differs from an average.
Example 3
operations = [["RECORD","a","1","0"],["RECORD","b","2","1"],["RECORD","c","5","2"],["AVERAGE","2"]]windowSize = 3return = ["8/3"]The exact average of all three scores is eight thirds.
Example 4
operations = [["RECORD","id with spaces","1","2"],["RECORD","other","5","2"],["UPDATE","id with spaces","5"],["AVERAGE","4"],["AVERAGE","5"],["UPDATE","id with spaces","1"],["AVERAGE","5"]]windowSize = 2return = ["5/1","EMPTY","EMPTY"]Updating at the current clock changes only the score. Both records remain active at time four, expire at time five, and cannot be revived.
Example 5
operations = [["RECORD","a","1","0"],["RECORD","b","4","1"],["RECORD","c","5","2"],["PERCENTILE","50"],["UPDATE","a","5"],["PERCENTILE","50"],["AVERAGE","3"],["PERCENTILE","100"]]windowSize = 2return = ["4","5","9/2","5"]At clock 2, active scores are [1,4,5], so rank 2 gives percentile 50 equal to 4. Updating a changes its score to 5 without moving timestamp 0, so the next median is 5. AVERAGE at clock 3 expires a and leaves scores [4,5], giving 9/2. The 100th percentile is 5.
Constraints
1 <= operations.length <= 200000.1 <= windowSize <= 10^9.- Each row is exactly one of the four operation forms in the statement; every numeric cell is a decimal integer string.
- Every recorded or updated score is from
1through5. Every supplied timestamp is from0through10^9, and all RECORD/AVERAGE timestamps are nondecreasing. - Every ID is a nonempty string of at most
100Unicode characters. Each RECORD uses an ID never used by another RECORD, even if the older record expired. - Percentile values satisfy
1 <= p <= 100. - At least one operation is AVERAGE or PERCENTILE.