Log Compaction

A compacted log keeps only the latest record per key. Older records for the same key are dropped. Tombstones are treated like normal records: if a tombstone is the latest record for a key, it should be kept.

Given an ordered log of records, return the compacted log in original order.

Types

type Record struct {
    Key       string
    Value     string
    Tombstone bool
}

Function signature

func CompactLog(records []Record) []Record

Example

records = [
  {Key:"a", Value:"1"},
  {Key:"b", Value:"x"},
  {Key:"a", Value:"2"},
  {Key:"b", Tombstone:true},
]

compacted = [
  {Key:"a", Value:"2"},
  {Key:"b", Tombstone:true},
]

Constraints

• 0 <= len(records) <= 200000

Notes

• The compacted log must preserve the relative order of retained records.