Rolling Metrics
Akuna Capital● MediumINTERNOAProblem statement
A telemetry component receives integer readings, each with a timestamp measured in microseconds since the Unix epoch. For a fixed window length windowSize, answer queries about the number, minimum value, and maximum value of readings inside a time window ending at a requested timestamp.
Operations
Implement rollingMetrics(windowSize, operations). Process operations in the supplied order. Each row is one of the following:
["add", timestamp, value]adds one reading. The timestamp and value are base-10 integer strings.["query", T]asks for the statistics of previously added readings whose timestamps lie in the closed interval[T - windowSize, T]. The query timestamp is a base-10 integer string.
For each query, append one row [count, minimum, maximum] to the result. Add operations produce no result row. Return the query rows in operation order; if there are no queries, return an empty array.
Practice rules
Use these fixed decisions for this exercise:
- Both window endpoints are included. A reading later than
Tis excluded even if it was added before the query. - An empty window returns
[0, 0, 0]. For a nonempty window, the minimum and maximum come from its actual readings, including negative values. - Every add creates a separate reading. Equal timestamps and identical timestamp-value pairs are counted separately.
- Only add operations appearing before the query are visible to it. Reading timestamps and query timestamps may arrive in any order.
- Queries do not delete data. A later operation may ask about an earlier time, so previously added readings remain available.
- When
windowSize = 0, only readings whose timestamp equalsTqualify.
Document your assumptions
Put a comment block at the top of your solution summarizing the rules you rely on, including window boundaries, empty results, duplicate readings, and operation ordering. Be prepared to explain the time and space costs and how your choice suits many inserts with few queries, or frequent queries.
The complete operation batch is available as input, but this does not change visibility: future add operations must never contribute to an earlier query.
Function
rollingMetrics(windowSize: long, operations: String[][]) → long[][]Examples
Example 1
windowSize = 5operations = [["add","5","8"],["add","10","-2"],["add","10","4"],["add","11","100"],["query","10"],["query","15"]]return = [[3,-2,8],[3,-2,100]]For T = 10, the window [5, 10] contains values 8, -2, and 4. The reading at timestamp 11 is excluded, giving [3, -2, 8].
For T = 15, the window [10, 15] contains values -2, 4, and 100, giving [3, -2, 100]. Both readings at timestamp 10 count separately.
Example 2
windowSize = 2operations = [["query","6"],["add","10","-4"],["add","4","7"],["query","6"],["query","12"],["add","6","1"],["query","6"]]return = [[0,0,0],[1,7,7],[1,-4,-4],[2,1,7]]The first query sees no readings. After the next two adds, querying T = 6 includes only the reading (4, 7); the previously added reading at timestamp 10 lies in the future of that window.
The query at T = 12 includes only (10, -4). Adding (6, 1) and querying T = 6 again includes both (4, 7) and (6, 1). The later-time query did not erase earlier data, and the first query did not see future add operations.
Constraints
0 <= windowSize <= 10^15, measured in microseconds.1 <= operations.length <= 500.- Every reading timestamp and query timestamp satisfies
0 <= timestamp <= 9 * 10^15. - Every reading value satisfies
-10^9 <= value <= 10^9. - Every operation has exactly the specified form and contains valid base-10 integer strings. Timestamps may repeat and need not be sorted.
- The operation list may contain no adds or no queries.
- All timestamp arithmetic and returned statistics fit in signed 64-bit integers. A window's lower endpoint may be negative.
Source note: Original task screenshot. The class interface and complete test definitions are outside the photographed area.