KV Store - Serialize and Deserialize

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

The most-reported OpenAI coding problem. You need a key-value store that can checkpoint its full state to a single string and restore from it. The catch: both keys and values are arbitrary strings - newlines, delimiters, null bytes, unicode, anything - so the serialization format must survive adversarial content without escaping.

Level 1 - put / get / erase

put: store key->value (overwrite if it already exists)
get: return value or None if missing
erase: remove key. Return True if it existed, False otherwise

Example:

store = KVStore()
store.put("name", "alice")
store.get("name")        # "alice"
store.erase("name")      # True
store.get("name")        # None
store.erase("ghost")     # False

Level 2 - serialize / deserialize with simple keys

Round-trip the store's state through a single string. Assume keys and values are simple ASCII without delimiters for this phase. The format is up to you; the natural answer is the same length-prefix framing the next phase requires.

Example:

store.put("host", "localhost")
store.put("port", "8080")
blob = store.serialize()
restored = KVStore.deserialize(blob)
restored.get("host")     # "localhost"
restored.get("port")     # "8080"

Level 3 - arbitrary characters in keys and values

Now keys and values can contain anything: :, ,, \n, \0, multi-byte unicode, even the empty string. Serialization must still round-trip.

Example:

store.put(":key:", ":value:")
store.put("line\nkey", "tab\tv")
store.put("", "")
blob = store.serialize()
restored = KVStore.deserialize(blob)
restored.get(":key:")     # ":value:"
restored.get("line\nkey") # "tab\tv"
restored.get("")          # ""

Level 4 - corruption resilience

On deserialize, if the blob is truncated or malformed, raise ValueError with a message that identifies the location. Don't silently return a partial store.

Example:

KVStore.deserialize("5:hello")
# ValueError: Malformed blob: missing ':' after position 7
# (key read ok, but value length prefix is absent)
 
KVStore.deserialize("5:hello3:ab")
# ValueError: field at position 7 claims 3 chars but only 2 remain

Level 5 - Binary protocol

Replace the ASCII length-prefix with a fixed 4-byte big-endian header per field. Format: [4 bytes: field_len][field bytes] for each key, then each value, per pair. Add two new methods:

def serialize_binary(self) -> bytes: ...
 
@classmethod
def deserialize_binary(cls, blob: bytes) -> "KVStore": ...

Same round-trip invariant and edge cases as Levels 2-4: empty key, empty value, multi-byte unicode, empty store, and corrupted input raises ValueError.

Example:

store.put("emoji", "中文")
blob = store.serialize_binary()
# 4-byte header encodes byte length: "中文".encode() is 6 bytes, not 2 chars
 
restored = KVStore.deserialize_binary(blob)
restored.get("emoji")   # "中文"

Mastery checklist

Check	Why it matters
Length-prefix framing, not delimiter scheme	Any delimiter can appear inside the data; escape rules add bugs without benefit
Empty key, empty value, empty store all round-trip	Three different zero-length cases that often break
Multi-byte unicode round-trips automatically with `str`	`len(s)` is character-based for `str`; only switch to `bytes` if asked
Corrupted input raises `ValueError` with location	Don't silently truncate - the caller needs to know
`erase` returns `True`/`False`, not the removed value	Mirrors `dict.pop` semantics; tests check the boolean
4-byte big-endian header: fixed-width read, no colon scan	Parsing is O(1) per field; the ASCII variant must scan forward to find `:`

Patterns used

Foundations primers this challenge draws on.

Hash Maps

Loading editor…

Premium content

The live editor for this challenge unlocks with Premium.

0/0 passed