The Sum of Its Parts

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
mid
Asked in
Autodesk

Problem

A 3D modeling tool stores each design as an assembly tree: every component carries a name, a quantity (how many of it appear inside its parent, defaulting to 1 when absent), and a children list of sub-components nested arbitrarily deep. Roll the tree up into the total count of each leaf part (a component with no children, including one whose children list is empty), where a part's count is the product of the quantities along the path from the root down to it, added up across every place that part appears.

Every assembly hides smaller ones. Count what it really takes to build.

Example 1

Input:

assembly = {"name":"Drone","children":[{"name":"Rotor","children":[{"name":"Blade","quantity":2},{"name":"Screw","quantity":6}],"quantity":4},{"name":"Screw","quantity":8}],"quantity":1}

Output:

{"Blade":8,"Screw":32}

Example 2

Input:

assembly = {"name":"Bracket","children":[{"name":"Bolt","quantity":3},{"name":"Washer"}]}

Output:

{"Bolt":3,"Washer":1}

Worked solution and explanation

Why this problem exists in real interviews

This is a recursive rollup over an unbounded-depth tree wearing a bill-of-materials costume. The skill being probed: can you walk an assembly whose depth you do not know in advance, carry a running multiplier from the root down to each leaf, and fold equal part names into one total? Anyone can loop over assembly['children']. The trick is that a part's true count is the PRODUCT of quantities along its whole path, and the same name shows up in different branches. Loop only the top level and you miss every nested part; forget to multiply the multiplier down and a screw that lives inside a rotor appearing four times gets counted once instead of times four.

Break down the requirements

Step 1: Recurse, because depth is unknown

You cannot write a fixed number of nested loops: an assembly can be a single bolt or ten levels of subassemblies. A recursive helper (or an explicit stack) is the only thing that reaches every leaf regardless of depth. The base case is a node with no children, or whose children is missing or empty.

Step 2: Thread the multiplier down each path

Pass a running multiplier into the recursion. At each node, multiply it by node.get('quantity', 1) so the value reaching a leaf already encodes how many of that part the whole chain demands. The .get default of 1 handles components that omit quantity.

Step 3: Aggregate leaves by name, not by occurrence

The same leaf name can appear in several branches, so accumulate into a single dict keyed by name rather than returning a list of occurrences. counts.get(name, 0) + qty folds each occurrence into the running total.

The solution

Recursive rollup with a threaded multiplier
def count_parts(assembly):
    counts = {}

    def walk(node, multiplier):
        qty = multiplier * node.get('quantity', 1)
        children = node.get('children')
        if not children:
            name = node['name']
            counts[name] = counts.get(name, 0) + qty
            return
        for child in children:
            walk(child, qty)

    walk(assembly, 1)
    return counts
Flat loop (wrong)
Iterate only assembly['children'] and add each child's quantity. Deeper subassemblies are never opened, so nested parts vanish and nothing is multiplied through. The Drone example returns the rotor and a screw count of 8, missing the 24 screws and 8 blades hidden one level down.
Recursive rollup (right)
Recurse into every child, multiplying the path quantity as you descend and accumulating leaves by name. The Drone example correctly yields 8 blades and 32 screws because the rotor's count of 4 propagates into its children before they are tallied.

Common follow-up questions