Quantile Sketch Rank Error

Problem

Return the maximum relative rank error of a quantile sketch given its bands.

Each band is [value, rank_min, rank_max] and contributes error (rank_max - rank_min) / 2. Divide the largest such error by the stream length n and return it, or 0.0 when n is non-positive or there are no bands.

Hint

Each band's uncertainty is half its rank interval, normalized by the stream length.

Test cases

case 1

in: [[[5,10,20]],100]

expected: 0.05

case 2

in: [[[1,0,4],[9,10,16]],100]

expected: 0.03

case 3

in: [[],50]

expected: 0

case 4

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

expected: 0

case 5

in: [[[1,0,200],[2,50,100]],100]

expected: 1

Starter codePython

def max_quantile_rank_error(bands, n):
    # Your code here
    pass

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