Katkat
Back

Flatten and unflatten nested Python structures

xAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests recursion, type introspection, and data structure manipulation by requiring the implementation of flattening and reconstruction logic for arbitrarily nested lists and dictionaries.

Flatten and Unflatten Nested Structures

You are tasked with creating two functions: flatten and unflatten.

Part 1: Flatten

Write a function flatten(data) that takes a nested structure (containing lists, dictionaries, integers, and strings) and returns a flat list of values while preserving the original structure's order. To reconstruct the structure later, flatten must also return a 'schema' object that captures the hierarchy.

Part 2: Unflatten

Write a function unflatten(flat_list, schema) that uses the provided schema to restore the values into their original nested containers.

Constraints

  • data can contain nested list or dict objects.
  • Dictionaries will have keys that are strings.
  • Assume flat_list matches the sequence length required by the schema.

Example

# Input
data = {'a': [1, 2], 'b': {'c': 3}}

# flatten(data) might return:
values = [1, 2, 3]
schema = {'a': ['L', 'L'], 'b': {'c': 'I'}}

# unflatten(values, schema) returns:
{'a': [1, 2], 'b': {'c': 3}}

Edge Cases

  • Empty lists [] or empty dictionaries {}.
  • Deeply nested structures (e.g., lists inside lists inside dicts).
  • Data types other than nested containers (e.g., None, floats).

Hints

Hint 1

Use recursion to traverse the data structure: when you encounter a container, drill down; when you encounter a leaf node, append the value to your result list.

Hint 2

For the schema, consider using a recursive representation where 'L' stands for a list index, 'D' for a dictionary key, and 'I' for a primitive/leaf value.

Hint 3

To unflatten, treat the schema as a blueprint: iterate through the schema recursively, consuming elements from an iterator created from the flat list to ensure O(n) performance.

Follow-up questions

  • How would you modify your solution to handle circular references in the nested structure?
  • What changes are required if you need to flatten the structure into a single dictionary using dot notation (e.g., 'a.0', 'b.c') instead of a separate schema object?
  • How would you optimize the memory footprint if the input structure contains millions of elements?