Window Sums by Tag
DatadogEasy
A monitoring service receives datapoints from customers. Each datapoint is a [timestamp, tag, value] triple, and points from different tags are interleaved in one stream.
Part 1: Sums per tag
Given a list of datapoints points, where each point is [timestamp, tag, value], and an integer k, return a dictionary mapping each tag to the sums of every run of k consecutive points of that tag.
points is ordered by increasing timestamp, and tags are interleaved. A window is k consecutive points of one tag in that tag's own timestamp order; points of other tags in between neither count toward a window nor break it.
Return one dictionary entry per tag that appears in points, with that tag's window sums ordered from the earliest window to the latest. A tag with fewer than k points maps to an empty list. With no points, return an empty dictionary.
- Example 1
- k
3- points
[[1,"tag",5],[2,"tag",4],[3,"tag",3],[4,"tag",2],[5,"tag",1]]- Output
{"tag":[12,9,6]}
Why: The windows cover values
[5, 4, 3],[4, 3, 2]and[3, 2, 1], which sum to 12, 9 and 6. - Example 2
- k
2- points
[[1,"cpu",10],[2,"mem",1],[3,"cpu",20],[4,"mem",2],[5,"cpu",30],[6,"mem",3],[7,"mem",4]]- Output
{"cpu":[30,50],"mem":[3,5,7]}
Why:
cpuhas values[10, 20, 30], giving windows 30 and 50.memhas[1, 2, 3, 4], giving 3, 5 and 7.
Constraints
0 <= len(points) <= 10^51 <= k <= 10^5points[i][0] < points[i + 1][0]for eachi(timestamps are distinct integers in increasing order)1 <= len(points[i][1])for eachi(tags are non-empty strings)-10^9 <= points[i][2] <= 10^9for eachi