~/problems / Streams & durability / Serialization and durability

OA: Durable key-value store serialization

medium 4 levels ~80 min OpenAI

Level 1 Snapshot to a single blob

Build KVStore(fs), a string-to-string store that can be written to storage and read back by a brand-new instance.

The tests hand you a fake file system fs with two methods:

  • fs.save_blob(data: bytes) -> None replaces the stored blob.
  • fs.get_blob() -> bytes | None returns the last saved blob, or None if nothing has been saved yet.

Your class:

  • put(key, value) and get(key) work in memory; get returns None for a missing key.
  • shutdown() encodes the whole store into bytes and saves it.
  • restore() loads the blob and replaces the in-memory contents with it (an empty store if nothing was saved).

The catch: design the byte format yourself. Don't use json, pickle, marshal, shelve, repr/eval or similar. Keys and values can contain anything: :, ,, =, quotes, newlines, \x00, emoji, or text that looks like your own length markers. Picking a separator character and hoping it never appears in the data is the classic mistake.

The starter gives you helpers: serialize_int(n) turns an unsigned int into exactly 4 bytes, serialize_str(s) UTF-8-encodes a string, plus their deserialize_* inverses. Note that a string's byte length differs from its character length once it has non-ASCII characters.

kv = KVStore(fs)
kv.put("time:now", "a,b=c")
kv.put("multi\nline", "")
kv.shutdown()

again = KVStore(fs)
again.restore()
again.get("time:now")      # "a,b=c"
again.get("multi\nline")   # ""
again.get("nope")          # None

Loading must be linear in the blob size.

Show hint

Escaping is fiddly; instead, prefix every string with its length in bytes. When loading, walk the blob with a position index rather than repeatedly slicing off the part you've read.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Level 4 unlocks when level 3 passes.

Topic: Serialization and durability. Length-prefixed encodings, write-ahead logs, checkpoints and recovery.

0:00
Ctrl ' run · Ctrl ↵ submit
esc