DGIM Bucket Count

Problem

Run the DGIM algorithm over a 0/1 stream and return the number of buckets in the summary of the last window bits.

Each 1-bit starts a size-1 bucket; whenever a size occurs three times, merge its two oldest buckets into one of double size, and drop buckets that end at or before t - window. Buckets are kept newest first, so the returned count is the summary size.

Hint

Three buckets of the same power of two always collapse into one bucket of the next size.

Test cases

case 1

in: [[1,0,1,1,0,1],6]

expected: 3

case 2

in: [[0,0,0],3]

expected: 0

case 3

in: [[1,1,1],10]

expected: 2

case 4

in: [[1,1,1,1,1,1,1,1],4]

expected: 3

case 5

in: [[1,0,1,0,1,1,0,1,1,1],5]

expected: 3

Starter codePython

def dgim_bucket_count(stream, window):
    # Your code here
    pass

5 test cases · run your code against them in the editor