How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Implement a serializable key-value store

Quick Overview

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.

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.

Input: [('put', b'a', b'1'), ('put', b'a', b'2'), ('serialize',), ('erase', b'a'), ('get', b'a'), ('deserialize', b'KVS1\x00\x00\x00\x01\x00\x00\x00\x01a\x00\x00\x00\x012'), ('get', b'a')]

Expected Output: [b'KVS1\x00\x00\x00\x01\x00\x00\x00\x01a\x00\x00\x00\x012', None, True, b'2']

Explanation: Overwriting the same key updates the value instead of creating a second copy. The serialized blob contains only one entry for key b'a'.

Input: [('put', b'\xcf\x80', b'\x00\xffA'), ('get', b'\xcf\x80'), ('serialize',)]

Expected Output: [b'\x00\xffA', b'KVS1\x00\x00\x00\x01\x00\x00\x00\x02\xcf\x80\x00\x00\x00\x03\x00\xffA']

Explanation: The format supports arbitrary bytes in both keys and values, including non-ASCII bytes and embedded zero bytes.

Input: [('put', b'x', b'1'), ('deserialize', b'KVS1\x00\x00\x00\x01\x00\x00\x00\x01x'), ('get', b'x')]

Expected Output: [False, b'1']

Explanation: The blob is truncated after the key, so deserialization fails. The original store must remain unchanged.

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.

Quick Overview