HyperLogLog Bucket Update

Problem

Update the registers of a HyperLogLog sketch and return the bucket list.

num_buckets registers each store the maximum rank observed. For each item, hash with djb2; the low bits choose the bucket (hash mod num_buckets) and the rank is the position of the leftmost 1-bit of the remaining value, capped at 32.

Return the register values.

Hint

A register only ever grows: keep the maximum rank seen for each bucket.

Test cases

case 1

in: [4,["a","b","c"]]

expected: [17,0,17,17]

case 2

in: [8,[]]

expected: [0,0,0,0,0,0,0,0]

case 3

in: [1,["x"]]

expected: [15]

case 4

in: [4,["a","a","b"]]

expected: [0,0,17,17]

Starter codePython

def hll_buckets(num_buckets, items):
    # Your code here
    pass

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