KLL Sketch Compaction

Problem

Compact a KLL-style quantile sketch summary.

values are inserted as [value, weight] pairs with weight 1 and kept sorted. While the summary is longer than capacity, adjacent pairs are merged with weight doubled and the value replaced by the larger of the two; a trailing odd item is kept unchanged.

Return the compacted [value, weight] pairs.

Hint

Each compaction pass halves the summary length while doubling the weights it carries.

Test cases

case 1

in: [[1,2,3,4,5,6],3]

expected: [[2,2],[4,2],[6,2]]

case 2

in: [[1],3]

expected: [[1,1]]

case 3

in: [[],2]

expected: []

case 4

in: [[5,4,3,2],1]

expected: [[5,4]]

case 5

in: [[3,1,2],2]

expected: [[2,2],[3,1]]

Starter codePython

def kll_compaction(values, capacity):
    # Your code here
    pass

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