~/problems / Stateful stores / In-memory database

Per-field undo in a record store

easy ~15 min

A greenhouse keeps notes on each plant bed in a record store: a record per bed ("bed3"), fields like "crop" or "watered". Staff keep mistyping things, so every field gets its own undo button.

Build UndoStore with:

  • set(key, field, value) -> None: write the field (creating the record if needed). Every call counts as a change, even if the value is the same as before.
  • get(key, field) -> str | None: the current value, or None if the record or field is missing.
  • delete(key, field) -> bool: remove the field and return True, or return False if it wasn't there. A delete that returns False is not a change.
  • undo(key, field) -> bool: revert the most recent change to that one field that hasn't been undone yet, and return True. The field goes back to the value it had just before that change, or disappears if it didn't exist then. Return False (changing nothing) if there is nothing left to undo for that field. Undo can be repeated all the way back to the field's very first change. Undo only affects the named field.
  • fields(key) -> list[str]: the record's current field names, sorted; [] for a missing record.
  • count() -> int: how many records have at least one field right now.

There is no redo: an undone change is gone for good.

s = UndoStore()
s.set("bed3", "crop", "kale")
s.set("bed3", "crop", "chard")
s.set("bed3", "watered", "mon")
s.delete("bed3", "crop")      # True
s.get("bed3", "crop")         # None
s.undo("bed3", "crop")        # True   (the delete is undone)
s.get("bed3", "crop")         # "chard"
s.undo("bed3", "crop")        # True
s.get("bed3", "crop")         # "kale"
s.undo("bed3", "crop")        # True   (the very first set is undone)
s.get("bed3", "crop")         # None
s.undo("bed3", "crop")        # False  (nothing left)
s.fields("bed3")              # ["watered"]
s.undo("bed3", "watered")     # True
s.count()                     # 0

count() is called a lot, so keep it O(1): don't scan all records.

Show hint

next to the key -> {field: value} dict from Basics, keep a dict (key, field) -> list of previous values. Before each change push the old value (None if the field was missing); undo pops it and writes it back, or deletes the field when it's None. Remove a record from the outer dict when its last field goes, and count() is len(...).

Topic: In-memory database. CRUD with fields, range scans, TTL expiry, time-travel reads.

0:00
Ctrl ' run · Ctrl ↵ submit
esc