Flatten and unflatten nested Python structures
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: nan
Interview Round: Technical Screen
You are given nested Python data structures used to represent hierarchical data.
## Supported node types
- Parent/container nodes can be:
- `list`
- `tuple`
- `dict`
- Leaf nodes are **always integers** (`int`).
For deterministic behavior, traverse containers in this order:
- `list` / `tuple`: left-to-right
- `dict`: iterate keys in the dictionary’s iteration order (assume it is deterministic for the input)
---
## Part A — Flatten
**Task:** Write a function `flatten(structure) -> list[int]` that extracts all integer leaves in traversal order into a single flat list.
**Example**
Input:
```python
{'a': [1, 2, 3], 'b': {'c': [{'d': 4}], 'e': 5}}
```
Output:
```python
[1, 2, 3, 4, 5]
```
---
## Part B — Unflatten
This is the inverse operation.
**Inputs:**
- `flat_list`: a list of integers (new values)
- `template`: a nested structure (same allowed types as above) whose **shape** should be reproduced
**Task:** Write a function `unflatten(flat_list, template)` that returns a **new** object with the exact same nested shape and container types as `template`, but with each integer leaf replaced by values from `flat_list` in traversal order.
**Assumptions / constraints:**
- `flat_list` contains exactly the number of integers required by `template` (or define and implement behavior if it has too few/too many).
**Example (conceptual)**
Given:
- `flat_list = [6, 7, 8, 9, 0]`
- `template` is a nested dict/list/tuple structure with 5 integer leaves (e.g., corresponding to leaves at keys/positions `a, b, c, d, e` in traversal order)
Output:
- a new structure with the same shape as `template`, whose leaf values become `6, 7, 8, 9, 0` in that order.
Quick Answer: This question evaluates proficiency in manipulating nested data structures, deterministic traversal and mapping between hierarchical shapes and flat integer sequences while preserving container types and iteration order.
Part 1: Flatten a Nested Python Structure
You are given a nested Python structure used to represent hierarchical data. A container can be a list, tuple, or dict, and every leaf value is an int. Traverse lists and tuples from left to right, and traverse dicts in their existing iteration order. Return a flat list containing all integer leaves in traversal order. The input itself may also be a single integer.
Constraints
- Supported container types are `list`, `tuple`, and `dict`.
- Every non-container leaf is an `int`.
- The root may itself be an `int`.
- For dicts, use the dictionary's existing iteration order; do not sort keys.
- The total number of nodes in the structure is at most 10^5.