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 nan difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at xAI.

What role is this question designed for?

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

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.

Examples

Input: [1, (2, 3), {'a': 4, 'b': [5]}]

Expected Output: [1, 2, 3, 4, 5]

Explanation: Visit the list left to right: 1, then tuple (2, 3), then dict values 4 and [5].

Input: {'x': [1, 2], 'y': {'z': 3}, 'w': (4, 5)}

Expected Output: [1, 2, 3, 4, 5]

Explanation: Dict values are visited in insertion order: [1, 2], then {'z': 3}, then (4, 5).

Input: 7

Expected Output: [7]

Explanation: If the input is already an integer leaf, return it as a one-element list.

Input: {'a': [], 'b': (), 'c': {'d': []}}

Expected Output: []

Explanation: All containers are empty, so there are no integer leaves.

Input: [-1, {'a': (-2, [-3, {'b': -1}])}, 0]

Expected Output: [-1, -2, -3, -1, 0]

Explanation: Traverse through nested list, dict, tuple, and list while preserving order.

Input: {'first': [1, {'second': (2, {'third': 3})}], 'last': 4}

Expected Output: [1, 2, 3, 4]

Explanation: Nested containers are flattened in traversal order, ending with the dict value 4.

Hints

A depth-first traversal naturally matches the required output order.
When you reach a dict, iterate through its keys exactly as the dict provides them, and recurse on each value.

Part 2: Unflatten into a Nested Python Structure

You are given a flat list of integers and a template nested structure. A container in the template can be a list, tuple, or dict, and every leaf in the template is an int. Build and return a new object with the exact same shape and container types as the template, but replace each integer leaf with values from `flat_list` in traversal order. Traverse lists and tuples from left to right, and dicts in their existing iteration order. Do not mutate the template. If `flat_list` has too few or too many values for the template, raise `ValueError`.

Constraints

Supported container types in the template are `list`, `tuple`, and `dict`.
Every non-container leaf in the template is an `int`.
The template root may itself be an `int`.
For dicts, use the dictionary's existing iteration order; do not sort keys.
If the number of integers in `flat_list` does not exactly match the number of integer leaves in `template`, the function should raise `ValueError`.
The total number of nodes in the template is at most 10^5.

Examples

Input: ([6, 7, 8, 9, 0], {'a': [0, 0, 0], 'b': {'c': [{'d': 0}], 'e': 0}})

Expected Output: {'a': [6, 7, 8], 'b': {'c': [{'d': 9}], 'e': 0}}

Explanation: Fill the three leaves in 'a' first, then continue into 'b'. Inside 'b', the value under 'c' is visited before 'e', so 9 goes to 'd' and 0 goes to 'e'.

Input: ([1, 2, 3, 4], ([0, (0, 0)], {'x': 0}))

Expected Output: ([1, (2, 3)], {'x': 4})

Explanation: Traverse the outer tuple left to right. The list part consumes 1, 2, 3, and then the dict value 'x' receives 4.

Input: ([], {'left': [], 'right': (), 'meta': {}})

Expected Output: {'left': [], 'right': (), 'meta': {}}

Explanation: There are no integer leaves anywhere in the template, so the flat list must be empty and the shape is reproduced unchanged.

Input: ([-5], 0)

Expected Output: -5

Explanation: The template itself is a single integer leaf, so it is replaced by the only value in flat_list.

Input: ([2, 2, -1, 2], {'k': (0, [0, 0]), 'z': 0})

Expected Output: {'k': (2, [2, -1]), 'z': 2}

Explanation: Dict iteration visits 'k' before 'z'. Inside 'k', the tuple is traversed left to right, so the values are assigned as 2, 2, -1, then finally 2 for 'z'.

Hints

Keep a moving index, or use an iterator over `flat_list`, so each integer leaf consumes the next value exactly once.
Recurse on the template and rebuild each container type instead of modifying the template in place.

Quick Overview

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.