WAL Replay

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

Each log entry either:

• sets a key to a value, or
• deletes a key.

Return the final visible key-value state sorted by key ascending.

This problem is intentionally direct: if you follow the replay rules exactly, the implementation is short.

Types

type LogEntry struct {
    Key     string
    Value   string
    Deleted bool
}

type KV struct {
    Key   string
    Value string
}

Function signature

func ReplayWAL(entries []LogEntry) []KV

Exact semantics

• Replay entries in input order, left to right.
• For a set entry (Deleted=false), write state[Key] = Value.
• For a delete entry (Deleted=true), remove Key from state.
• Deleting a missing key is allowed and is a no-op.
• A key may be deleted and later re-created by a newer set.
• Final output must contain only existing keys, sorted by key.

Implementation recipe (almost the full answer)

1. Create state := map[string]string{}.
2. Loop over entries in order.
3. If entry.Deleted, call delete(state, entry.Key).
4. Else assign state[entry.Key] = entry.Value.
5. Collect keys from map into a slice.
6. Sort keys ascending.
7. Build result []KV in sorted-key order.

Examples

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

entries = [
  {Key:"x", Deleted:true},
  {Key:"x", Value:"9"}
]
output = [{Key:"x", Value:"9"}]

entries = [
  {Key:"k", Value:"1"},
  {Key:"k", Value:"2"},
  {Key:"k", Value:"3"}
]
output = [{Key:"k", Value:"3"}]

Complexity target

• Replay pass: O(n)
• Sorting output keys: O(m log m), where m is number of remaining keys
• Extra space: O(m)

Notes

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