Implement BFS serializer and deserializer

Q: Implement BFS serializer and deserializer

This is a Coding & Algorithms interview question from Airtable for Software Engineer roles. View the full question and solution on PracHub.

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

Implement two functions, serialize(obj) -> representation and deserialize(representation) -> obj, for a Python object graph containing str, int, and dict, including possible circular references. Use a BFS traversal to produce a structure of the form: { 'root_id': <id_str>, 'value_map': { <id_str>: <value_or_mapping>, ... } }, where each visited object gets a unique string identifier (e.g., str(id(obj))). For dictionaries, store a mapping of field names to child identifiers; for primitives (str, int), store the raw value under their identifiers. Ensure shared subobjects reuse the same identifier and that cycles are preserved without duplication. Deserialization should reconstruct the original graph from value_map by allocating nodes, wiring references by identifiers, and returning the object at root_id. Discuss correctness, determinism of traversal/ID assignment, and the time/space complexity.

Implement BFS serializer and deserializer

Comments (0)