Tombstone Purge Trigger

Problem

Decide which tombstones can be purged.

entries is a list of [key, value, timestamp] and oldest_snapshot is the oldest live snapshot timestamp. Tombstone entries (value None) with a timestamp at or before oldest_snapshot can be purged; later tombstones must stay.

Return [remaining_tombstones, purged_tombstones].

Hint

Purging is only safe once no live snapshot can still see the deleted value.

Test cases

case 1

in: [[[1,null,5],[2,"a",7],[3,null,10]],5]

expected: [1,1]

case 2

in: [[[1,null,3]],5]

expected: [0,1]

case 3

in: [[[1,"a",1]],5]

expected: [0,0]

case 4

in: [[],5]

expected: [0,0]

Starter codePython

def purge_tombstones(entries, oldest_snapshot):
    # Your code here
    pass

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