Implement map serialization and deserialization

Q: Implement map serialization and deserialization

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

The concrete string format you choose.
How serialize produces that format for a given map.
How deserialize parses that format back into the original map and handles edge cases (e.g., empty map, empty keys/values, special characters).
The time and space complexity of both functions.

Implement map serialization and deserialization

Overview

Comments (0)