Implement a serializable key-value store
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement in C++ an in-memory key-value store with:
- put(key: string, value: string), get(key) -> optional<string>, erase(key).
- serialize() -> vector<uint8_t> that encodes the entire store state.
- deserialize(const vector<uint8_t>&) to restore an identical store state.
Constraints:
- Use only the provided helper byte I/O functions; do not use external libraries for serialization.
- Choose a robust binary format (versioned, length-prefixed) that supports arbitrary bytes in keys/values and Unicode.
- Ensure correctness for empty store, very large keys/values, duplicate overwrites, and deletions.
- Validate input and handle malformed or truncated streams gracefully with clear error signaling.
- Time/space complexity should be O(n) in the total serialized data size; support streaming-friendly encoding.
- Provide unit tests and explain complexity, trade-offs (e.g., delimiter-escaped text vs. length-prefixed binary), and failure recovery.
Quick Answer: This question evaluates competency in implementing robust serialization and in-memory data structures, covering binary format design, handling arbitrary bytes and Unicode, correctness across edge cases (empty state, large keys/values, overwrites, deletions), input validation and failure recovery, complexity analysis, and unit testing.
Implement an **in-memory key–value store** with a custom **binary serialization format**, driven by a list of operations.
Because the judge calls a single function rather than a class, you are given a **list of operations** to apply, in order, to one store. Each operation is a sequence (tuple/list) whose first element is the operation name and whose remaining elements are its arguments:
```python
def solution(operations):
...
```
## Operations
Apply each operation to a single store, in the given order:
- **`('put', key, value)`** — Insert or update `key` with `value`. If `key` already exists, overwrite its value **in place** (do **not** create a duplicate entry, and keep the key's original position in insertion order). Produces no output.
- **`('get', key)`** — Append the stored value for `key` to the result, or `None` if the key is absent.
- **`('erase', key)`** — Remove `key` from the store. Erasing a missing key does nothing. Produces no output.
- **`('serialize',)`** — Append the `bytes` encoding of the entire current store to the result (see format below).
- **`('deserialize', blob)`** — Attempt to parse `blob`. Append `True` if the blob is fully valid (and replace the store with the parsed contents), or `False` if it is malformed (and leave the store **unchanged**).
**Return** a list containing the outputs of every `get`, `serialize`, and `deserialize` operation, in the order they occurred. `put` and `erase` contribute nothing to the result.
## Key / value handling
- Keys and values are `bytes` objects.
- If a test passes a Python `str`, treat it as **UTF-8** and convert it to `bytes` before storing, comparing, or encoding.
## Binary serialization format
`serialize` must produce, and `deserialize` must accept, **exactly** this length-prefixed binary layout:
1. **4-byte magic header:** the ASCII bytes `KVS1`.
2. **4-byte unsigned big-endian** entry count.
3. For each key–value pair, **in current insertion order**:
- 4-byte unsigned big-endian **key length**
- the raw **key bytes**
- 4-byte unsigned big-endian **value length**
- the raw **value bytes**
Length prefixes (rather than delimiters) keep the format robust for keys/values that may contain **arbitrary bytes**, including zero bytes and non-ASCII Unicode data.
## Deserialization rules (all-or-nothing)
`deserialize` replaces the store **only if** `blob` is completely valid. On **any** failure, leave the store unchanged and append `False`. A blob is **malformed** if any of the following hold:
- The magic header is not `KVS1`.
- The blob is **truncated** — any declared length runs past the end of the data, or there are too few bytes to read a required field.
- It contains **duplicate keys**.
- There are **extra trailing bytes** after the declared number of entries have been read.
## Constraints
- `1 <= len(operations) <= 200000`
- The total number of bytes across all keys, values, and serialized blobs is at most `10^6`.
- Each key and value length is between `0` and `2^32 - 1` bytes.
- Average-case `O(1)` map operations are acceptable; each `serialize` / `deserialize` must run in time linear in the blob size.
Constraints
- 1 <= len(operations) <= 200000
- The total number of bytes appearing in all keys, values, and serialized blobs is at most 10^6
- Each key and value length is between 0 and 2^32 - 1 bytes
- Average-case O(1) map operations are acceptable; each serialize/deserialize must be linear in the blob size
Examples
Input: [('put', b'name', b'alice'), ('put', b'lang', b'py'), ('get', b'name'), ('serialize',), ('erase', b'name'), ('get', b'name'), ('deserialize', b'KVS1\x00\x00\x00\x02\x00\x00\x00\x04name\x00\x00\x00\x05alice\x00\x00\x00\x04lang\x00\x00\x00\x02py'), ('get', b'name'), ('get', b'lang')]
Expected Output: [b'alice', b'KVS1\x00\x00\x00\x02\x00\x00\x00\x04name\x00\x00\x00\x05alice\x00\x00\x00\x04lang\x00\x00\x00\x02py', None, True, b'alice', b'py']
Explanation: The store is serialized with two entries, then one key is deleted. Deserializing the earlier blob restores both pairs.
Input: [('serialize',), ('deserialize', b'KVS1\x00\x00\x00\x00'), ('get', b'missing')]
Expected Output: [b'KVS1\x00\x00\x00\x00', True, None]
Explanation: An empty store serializes to just the header and a zero entry count. Deserializing it succeeds and the store remains empty.
Hints
- A delimiter like ':' is unsafe because keys and values may contain arbitrary bytes. Store a fixed-size length before each raw byte sequence.
- For failure recovery, do not modify the live store while parsing a blob. Decode into a temporary dictionary first, then replace the store only if parsing finishes exactly at the end.