WAL Replay

A write-ahead log (WAL) stores updates in order. To recover a key-value store after a crash, replay the log from the beginning.

Each log entry either sets a key or deletes it. Return the final key-value state sorted by key.

Types

type LogEntry struct {
    Key     string
    Value   string
    Deleted bool
}

type KV struct {
    Key   string
    Value string
}

Function signature

func ReplayWAL(entries []LogEntry) []KV

Example

entries = [
  {Key:"a", Value:"1"},
  {Key:"b", Value:"2"},
  {Key:"a", Deleted:true}
]
output = [{Key:"b", Value:"2"}]

Notes

• If a key is deleted, it should not appear in the output.
• Output must be sorted by key ascending.