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 Onsite 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 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.

Input: ('serialize', {'': '', 'a:b|c': 'x,y=z', 'k#1': 'v#2'})

Expected Output: '3#0#0#5#a:b|c5#x,y=z3#k#13#v#2'

Explanation: The keys are serialized in sorted order: '', 'a:b|c', 'k#1'. Each key and value is written as length + '#' + content.

Input: ('deserialize', '3#0#0#5#a:b|c5#x,y=z3#k#13#v#2')

Expected Output: {'': '', 'a:b|c': 'x,y=z', 'k#1': 'v#2'}

Explanation: Length prefixes allow correct parsing even though the strings contain punctuation and '#'.

Input: ('serialize', {'b': 'two words', 'a': '1', '': ' '})

Expected Output: '3#0#1# 1#a1#11#b9#two words'

Explanation: Sorted key order is '', 'a', 'b'. The single-space value is encoded as length 1, and 'two words' has length 9.

Input: ('deserialize', '3#0#1# 1#a1#11#b9#two words')

Expected Output: {'': ' ', 'a': '1', 'b': 'two words'}

Explanation: Empty keys, space-only values, and multi-word values are reconstructed exactly.

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.

Quick Overview

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.