Latency Bucket Counter
Learn this problem
DatadogFULLTIMEOAProblem statement
You are given an array latencies of positive integers sorted in ascending order, an integer numOfBuckets, and an integer bucketWidth. Each latency is measured in milliseconds.
Return an array of numOfBuckets counts. For every bucket index i from 0 through numOfBuckets - 2, bucket i covers the inclusive range [i * bucketWidth, (i + 1) * bucketWidth - 1]. The last bucket is an overflow bucket: it contains every latency greater than or equal to (numOfBuckets - 1) * bucketWidth.
The returned value at index i must equal the number of latencies assigned to bucket i.
Function
countLatenciesInBuckets(latencies: int[], numOfBuckets: int, bucketWidth: int) → int[]Examples
Example 1
latencies = [6,7,50,100,110]numOfBuckets = 11bucketWidth = 10return = [2,0,0,0,0,1,0,0,0,0,2]Latencies 6 and 7 fall in bucket 0, latency 50 falls in bucket 5, and latencies 100 and 110 fall in the last overflow bucket.
Example 2
latencies = [12,22,38,41,120,131,250]numOfBuckets = 6bucketWidth = 40return = [3,1,0,2,0,1]The first bucket covers 0 through 39, so it contains 12, 22, and 38. Values 120 and 131 share bucket 3, while 250 goes to the overflow bucket.
Example 3
latencies = [1,2,3,4,5]numOfBuckets = 5bucketWidth = 10return = [5,0,0,0,0]Every latency is between 0 and 9, so all five values fall in bucket 0.
Constraints
1 <= latencies.length <= 10^51 <= latencies[i] <= 10^9latenciesis sorted in ascending order.1 <= numOfBuckets <= 10^41 <= bucketWidth <= 10^6