Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
The state store is a log of segments: each write appends a record, and a delete appends a tombstone. Compaction merges segments and keeps the newest record per key. The obvious optimisation is to drop the tombstones — they carry no data — and the last time somebody did that, every deleted key came back.
Write compact_segments(segments, retain_from_seq, full).
Function to write
compact_segments(segments: list[list[dict]], retain_from_seq: int, full: bool) -> dictA dict with the kept records ordered by key, and counts of the superseded records and dropped tombstones.
How to approach it
Group by key, take the highest sequence, then decide separately whether a tombstone may go.
Sample cases
+ 2 held back until you submit
three segments, partial compaction
A key updated three times, an old delete that can be dropped, and a recent one that cannot.
Input
Argument 1
[
[
{
'key': 'a',
'seq': 1,
'op': 'put',
'value': 'a1'
},
{
'key': 'b',
'seq': 2,
'op': 'put',
'value': 'b1'
},
{
'key': 'c',
'seq': 3,
'op': 'put',
'value': 'c1'
}
],
[
{
'key': 'a',
'seq': 4,
'op': 'put',
'value': 'a2'
},
{
'key': 'b',
'seq': 5,
'op': 'delete'
},
{
'key': 'd',
'seq': 6,
'op': 'put',
'value': 'd1'
}
],
[
{
'key': 'c',
'seq': 7,
'op': 'delete'
},
{
'key': 'a',
'seq': 8,
'op': 'put',
'value': 'a3'
}
]
]Argument 2
6Argument 3
FalseReturns
{
'records': [
{
'key': 'a',
'seq': 8,
'op': 'put',
'value': 'a3'
},
{
'key': 'c',
'seq': 7,
'op': 'delete',
'value': None
},
{
'key': 'd',
'seq': 6,
'op': 'put',
'value': 'd1'
}
],
'dropped': {
'superseded': 4,
'tombstones': 1
}
}compacting the whole table
With every segment present, no older data can resurrect, so every tombstone goes.
Input
Argument 1
[
[
{
'key': 'a',
'seq': 1,
'op': 'put',
'value': 'a1'
},
{
'key': 'b',
'seq': 2,
'op': 'put',
'value': 'b1'
},
{
'key': 'c',
'seq': 3,
'op': 'put',
'value': 'c1'
}
],
[
{
'key': 'a',
'seq': 4,
'op': 'put',
'value': 'a2'
},
{
'key': 'b',
'seq': 5,
'op': 'delete'
},
{
'key': 'd',
'seq': 6,
'op': 'put',
'value': 'd1'
}
],
[
{
'key': 'c',
'seq': 7,
'op': 'delete'
},
{
'key': 'a',
'seq': 8,
'op': 'put',
'value': 'a3'
}
]
]Argument 2
6Argument 3
TrueReturns
{
'records': [
{
'key': 'a',
'seq': 8,
'op': 'put',
'value': 'a3'
},
{
'key': 'd',
'seq': 6,
'op': 'put',
'value': 'd1'
}
],
'dropped': {
'superseded': 4,
'tombstones': 2
}
}nothing to compact
No segments produces no records and no drops rather than raising.
Input
Argument 1
[] (empty list)
Argument 2
0Argument 3
FalseReturns
{
'records': [],
'dropped': {
'superseded': 0,
'tombstones': 0
}
}Constraints
key, a seq and an op of put or delete. A record with no op is a put.seq wins for a key. The segment it came from is irrelevant — segments may be listed in any order.full is true — every segment of the store is in this compaction, so no older record survives anywhere to resurrect — or when its seq is below retain_from_seq, meaning every segment that could hold an older version has already been compacted past it.Worked example
Key a is written three times, at sequences 1, 4 and 8. Only a3 survives; the other two are superseded, which is the space compaction is meant to reclaim.
Key b is deleted at sequence 5, and key c at sequence 7. With retain_from_seq of 6, the delete of b is old enough that everything below it has already been compacted away — there is no b1 left anywhere to come back, so the tombstone can go. The delete of c cannot: a segment not part of this compaction still holds c1 at sequence 3, and dropping the tombstone would let a later read find it and conclude the key exists.
That is the whole difficulty. A tombstone is not data, it is evidence of absence, and it has to outlive every record it is suppressing. Dropping it early is invisible until a read happens to reach an old segment, which is why the resurrection bug is always found in production.
What this tests
Why deletes are so hard in a log-structured store: absence has to be represented positively, and the representation can only be discarded when you can prove nothing it contradicts survives. That proof is the full flag and the retention sequence, not an intuition about age.
compact_segments(segments: list[list[dict]], retain_from_seq: int, full: bool) -> dictSubmit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.