Implement BFS serializer and deserializer

Q: Implement BFS serializer and deserializer

This question evaluates the skill of serializing and deserializing Python object graphs using BFS, including handling primitives, dictionaries, shared subobjects, and circular references while preserving object identity.

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

Overview

Comments (0)