Flatten / Unflatten Nested Python Structure

Two paired sub-problems on nested Python containers. Part 1: walk an arbitrarily nested mix of `list / dict / tuple` whose leaves are `int` and emit a flat `list[int]` in encounter order. Part 2: given the original (or a template-shaped) structure plus a flat list of new integers, rebuild the same structure with leaves replaced in order. Requirements Part 1 — flatten Input: arbitrarily nested mix of list, dict, tuple. All leaves are int. Output: list[int] in traversal order. Input: {'a': [1, 2, 3], 'b': {'c': [{'d': 4}], 'e': 5}} Output: [1, 2, 3, 4, 5] Part 2 — unflatten Input: flat_list: list[int] and a structure (template) of the same nested shape with placeholder integers at the leaves. Output: a new structure with the same shape and types, but with leaf integers consumed in order from flat_list. flat_list = [6, 7, 8, 9, 0] structure = {'a': [_, _, _], 'b': {'c': [{'d': _}], 'e': _}} result = {'a': [6, 7, 8], 'b': {'c': [{'d': 9}], 'e': 0}} Canonical OA signatures (length mismatch is an error, not silent truncation): from typing import Any def flatten(structure: Any) -> list[int]: ... # int leaves only; list / tuple / dict internal nodes def unflatten(flat_list: list[int], structure: Any) -> Any: ... # Rebuild structure's shape, consuming flat_list in traversal order, preserving container types. # Raise ValueError if flat_list has too few OR too many values; raise TypeError on unsupported node types. Notes Dict iteration order is insertion order in modern Python; your traversal must match between flatten and unflatten or the values will land in the wrong slots. Tuples must be reconstructed as tuples, lists as lists, dicts as dicts — preserving container types is part of the grading. Use a single iterator/cursor over flat_list during unflatten (it = iter(flat_list); next(it)) so recursion does not need to thread an index parameter. Validate length exactly: a StopIteration raised mid-build means flat_list was too short; after rebuilding, one more successful next(it) means it was too long. Convert both into a ValueError. Empty containers (empty list / dict / tuple) should round-trip as themselves; make sure your recursion does not collapse them. The round runs in ~30 minutes inside a longer screen — keep both functions tight. Preparation Write flatten(x) and unflatten(flat, structure) from scratch in under 15 minutes. Practice the iterator-as-cursor pattern for unflatten — it is the cleanest implementation and the one interviewers seem to expect. Be ready to extend to additional leaf types (floats, strings) and to handle structure / data length mismatches. Strong follow-ups to have ready: extract a single shared traversal helper so flatten and unflatten provably walk nodes in the same order; hide "is this a leaf" behind an is_leaf(node) predicate so leaves can be arbitrary types, not just int; and for pathological depth, swap recursion for an explicit stack to dodge Python's frame limit. This is the natural superset of the classic "flatten nested list iterator" problem: where the textbook version restricts inputs to list[NestedInteger] and asks for an __init__ / hasNext / next iterator, the xAI version generalizes to mixed list / dict / tuple containers and adds the inverse unflatten direction. The iterator-cursor pattern (it = iter(flat_list)) is exactly the trick that makes the canonical lazy next() implementation clean — same idea, used for the write side instead of the read side. Canonical complexity: flatten and unflatten both O(n) over the total leaf count; recursion depth bounded by nesting depth (watch Python's default 1000-frame limit on pathological inputs).