Implement map serialization and deserialization
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an in-memory map (dictionary) from strings to strings.
Implement two functions:
- `string serialize(map<string, string> m)`
- `map<string, string> deserialize(string data)`
Requirements:
- The serialization format must be **invertible**: deserializing the result of `serialize(m)` must always reconstruct the original map exactly.
- Keys and values are arbitrary strings and may contain spaces, punctuation, and characters that you might otherwise want to use as delimiters (e.g., `:`, `,`, `;`, `|`, `=`). You may assume they do not contain the null character `"\0"`.
- You **may not** use built-in serialization formats or libraries (e.g., no JSON, protobuf, or similar). You must design the encoding yourself.
- Aim for an efficient solution in both time and space for maps with up to, say, tens of thousands of key–value pairs.
Specify and implement:
1. The concrete string format you choose.
2. How `serialize` produces that format for a given map.
3. How `deserialize` parses that format back into the original map and handles edge cases (e.g., empty map, empty keys/values, special characters).
4. The time and space complexity of both functions.
Quick Answer: This question evaluates understanding of serialization, string encoding and parsing, data structure invariants (invertibility), and efficiency when representing maps with arbitrary string keys and values.
Design a custom, invertible encoding for a map from strings to strings. Because keys and values may contain any punctuation characters (including characters you might normally use as delimiters), a delimiter-only format is not safe. For this problem, use a length-prefixed format and implement both operations through one judge function: solution(operation, data). If operation == 'serialize', data is a dictionary {string: string} and you must return its serialized string. If operation == 'deserialize', data is a serialized string and you must return the original dictionary. Use this concrete format: <pair_count>#<key_length>#<key><value_length>#<value>... for every key-value pair, with pairs written in lexicographically sorted key order so the serialization is deterministic. Example: {'a': 'hi', 'b': ''} becomes '2#1#a2#hi1#b0#'. Empty maps, empty keys, empty values, spaces, and characters like ':', ',', ';', '|', '=', and '#' must all work correctly.
Constraints
- 0 <= number of key-value pairs <= 50000
- The total number of characters across all keys and values is at most 10^6
- Keys and values are arbitrary strings and may contain delimiter-like characters, including '#'
- Keys and values do not contain the null character '\0'
- For deserialize, the input string is expected to follow the specified format; malformed input may raise ValueError
Examples
Input: ('serialize', {})
Expected Output: '0#'
Explanation: An empty map has 0 pairs, so the entire encoding is just the pair count followed by '#'.
Input: ('deserialize', '0#')
Expected Output: {}
Explanation: The pair count is 0, so the reconstructed dictionary is empty.
Hints
- If keys and values can contain any delimiter character, splitting on a separator is not enough.
- Prefix each key and value with its length so the parser always knows exactly how many characters to read next.