## Prompt Design and implement serialization for an in-memory key-value store whose keys and values are arbitrary UTF-8 strings. The interviewer provides helpers that encode a nonnegative integer as exactly four bytes and decode those four bytes back to an integer; you do not need to implement bit manipulation. Define a deterministic binary format, then write pseudocode for `serialize(store)` and `deserialize(bytes)`. The decoder must reject malformed or truncated input instead of returning partial state. ### Constraints & Assumptions - Keys are unique strings and values are strings; either may be empty. - UTF-8 byte length, not character count, is stored. - No key or value exceeds the unsigned 32-bit length limit. - The byte stream may contain any byte value, so delimiter-only formats are unsafe without escaping. - Serialization of logically equal stores must produce identical bytes; choose and state a deterministic key order. - The decoder has a configurable maximum entry count and total decoded bytes to prevent resource exhaustion. ### Clarifying Questions to Ask - Must the format support future schema versions? - Are keys and values text, raw bytes, or typed values? - Is deterministic output required for hashing or tests? - How should duplicate keys, trailing bytes, invalid UTF-8, and oversized lengths be handled? - Is backward compatibility required after the format changes? ```hint Length-prefix every variable field Encode an entry count, then for each sorted key encode key length, key bytes, value length, and value bytes. ``` ### What a Strong Answer Covers - A byte-level format with magic or version information, entry count, and length-prefixed fields. - Deterministic key ordering and a clear UTF-8 encoding rule. - Bounds checks before every read and before allocating based on an untrusted length. - Rejection of duplicate keys, invalid UTF-8, overflow, trailing garbage, and incomplete records. - Linear-time encoding and decoding without repeatedly copying the entire buffer. - Trade-offs among simplicity, forward compatibility, checksums, and streaming. ### Follow-up Questions 1. Why is joining fields with a delimiter insufficient for arbitrary strings? 2. How would a checksum distinguish corruption from a parse error? 3. How would you decode from a stream without loading the complete payload? 4. How would optional typed values be added without breaking old decoders?