LSM Compaction Pick

Problem

Simulate leveled LSM-tree compaction cascades.

levels holds the number of files per level and capacities gives each level's maximum file count. Repeatedly compact the first level that exceeds its capacity by moving all of its files into the next level, until only the last level may remain over capacity.

Return [compaction_count, files_moved].

Hint

A compaction can push the next level over its own capacity, triggering a cascade.

Test cases

case 1

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

expected: [1,4]

case 2

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

expected: [0,0]

case 3

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

expected: [2,15]

case 4

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

expected: [0,0]

case 5

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

expected: [1,10]

Starter codePython

def lsm_compactions(levels, capacities):
    # Your code here
    pass

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