Checkpoint and WAL Replay

medium · log replay

Given snapshot (string-to-integer dictionary), checkpoint (nonnegative sequence number), and wal records, recover state. Each record is [sequence, operation, key, value], with sequence >= 1 and operation 'set' or 'delete' (value ignored for delete). Process records in ascending sequence order and keep the FIRST record in input order if a sequence repeats. Ignore sequences <= checkpoint. A delete of a missing key is a no-op. Return {'state': recovered dictionary, 'last_sequence': greatest applied sequence or checkpoint if none}. Gaps are allowed and are not errors; do not mutate the snapshot. Examples (JSON; null means Python None): Input: {"snapshot": {"a": 1}, "checkpoint": 2, "wal": [[4, "set", "a", 3], [3, "set", "b", 2]]} Output: {"state": {"a": 3, "b": 2}, "last_sequence": 4} Input: {"snapshot": {"a": 7}, "checkpoint": 3, "wal": [[2, "set", "a", 0], [4, "delete", "a", null], [4, "set", "a", 9]]} Output: {"state": {}, "last_sequence": 4}

Starter code

def replay_checkpoint(snapshot: dict[str, int], checkpoint: int, wal: list[list]) -> dict:
    """Recover a snapshot by replaying later unique log records."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.

  2. The GraderCharacter joke · No posting date

    Your solution is correct. Your variable names are a crime scene.

  3. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.