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.