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

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airtable during technical interviews.

Implement BFS serializer and deserializer

Company: Airtable

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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.

Quick Answer: 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.

Implement a serializer and deserializer for a Python object graph whose nodes are integers, strings, and dictionaries with string keys. The graph may contain shared dictionaries and circular references. A serialized graph has the form {'root_id': <id_str>, 'value_map': {<id_str>: <value_or_mapping>, ...}}. For a primitive int or str node, store the raw primitive value in value_map. For a dictionary node, store a dictionary mapping each field name to the identifier of that field's child node. To make the result deterministic and testable, assign identifiers as strings '0', '1', '2', ... in BFS first-discovery order, with the root assigned '0'. When visiting a dictionary, process its keys in lexicographic order. The judge calls solution(mode, data). For mode == 'serialize', return the serialized representation of data. For mode == 'deserialize', data is a serialized representation; reconstruct the object graph, then return its canonical serialized form by serializing the reconstructed root. This re-serialization lets the judge compare cyclic graphs safely.

Constraints

The graph contains only int, str, and dict objects; dictionary keys are strings.
The graph may contain cycles and shared dictionary subobjects.
The number of reachable nodes is at most 10000.
The total number of dictionary fields is at most 50000.
For deterministic output, assign IDs '0', '1', ... by BFS first discovery and visit dictionary keys in lexicographic order.
Every child identifier in an input representation exists in value_map.

Examples

Input: ('serialize', 42)

Expected Output: {'root_id': '0', 'value_map': {'0': 42}}

Explanation: A primitive root receives ID '0' and is stored directly as its raw value.

Input: ('serialize', {})

Expected Output: {'root_id': '0', 'value_map': {'0': {}}}

Explanation: An empty dictionary has no child fields, so its stored mapping is empty.

Input: ('serialize', {'b': 'hi', 'a': {'x': 1}})

Expected Output: {'root_id': '0', 'value_map': {'0': {'a': '1', 'b': '2'}, '1': {'x': '3'}, '2': 'hi', '3': 1}}

Explanation: The root is ID '0'. Keys are visited as 'a', then 'b', so the nested dictionary is ID '1' and 'hi' is ID '2'. The nested value 1 is then discovered as ID '3'.

Input: ('deserialize', {'root_id': 'r', 'value_map': {'r': {'right': 'child', 'left': 'child'}, 'child': {'value': 'v'}, 'v': 7}})

Expected Output: {'root_id': '0', 'value_map': {'0': {'left': '1', 'right': '1'}, '1': {'value': '2'}, '2': 7}}

Explanation: Both 'left' and 'right' point to the same reconstructed dictionary, so canonical serialization reuses child ID '1' for both fields.

Input: ('deserialize', {'root_id': 'root', 'value_map': {'root': {'self': 'root', 'n': 'one'}, 'one': 1}})

Expected Output: {'root_id': '0', 'value_map': {'0': {'n': '1', 'self': '0'}, '1': 1}}

Explanation: The 'self' field points back to the root dictionary, so it is serialized as ID '0' rather than duplicating the node.

Input: ('deserialize', {'root_id': 'A', 'value_map': {'A': {'next': 'B', 'name': 'N1'}, 'B': {'next': 'A', 'name': 'N2'}, 'N1': 'a', 'N2': 'b'}})

Expected Output: {'root_id': '0', 'value_map': {'0': {'name': '1', 'next': '2'}, '1': 'a', '2': {'name': '3', 'next': '0'}, '3': 'b'}}

Explanation: This representation encodes a two-node cycle. The canonical BFS serialization preserves B's back-reference to A as 'next': '0'.

Hints

Use a queue for BFS and a map from object identity to assigned string ID. Enqueue an object only when it is first discovered.
For deserialization, allocate all dictionary nodes first, then fill their fields in a second pass so cycles and back-references can be wired correctly.

Quick Overview

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.