# The Sum of Its Parts > Every assembly hides smaller ones. Count what it really takes to build. Canonical URL: Domain: Python · Difficulty: medium · Seniority: mid ## 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. ## 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** ```python 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 ``` > **Complexity** > > Time is O(n) where n is the number of nodes in the assembly: each node is visited exactly once and does O(1) work. Space is O(d) for the recursion stack, where d is the maximum depth, plus O(k) for the result dict over k distinct leaf names. Real assemblies are wide and shallow, so the stack stays tiny; the depth only matters if a design is pathologically nested, which is the cue to mention an explicit stack. > **Interviewers Watch For** > > Whether you carry state DOWN the recursion (the multiplier) rather than trying to combine results bubbling up, and whether you reach for `node.get('quantity', 1)` instead of assuming the key is always present. Strong candidates also state their leaf rule out loud: missing key, key present but empty list, both count as a leaf, which is exactly the `if not children` test. > **Common Pitfall** > > Summing quantities instead of multiplying them along the path. A rotor with quantity 4 holding a screw with quantity 6 means 24 screws, not 10. The other frequent miss is overwriting `counts[name] = qty` instead of adding to it, which silently drops every earlier occurrence of a part that appears in more than one branch. **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 - How would you rewrite this without recursion, in case an assembly is nested deep enough to hit Python's recursion limit? _(Tests whether the candidate can convert the recursion into an explicit stack of (node, multiplier) pairs while preserving the same multiply-and-accumulate logic.)_ - What if a component could appear as its own descendant, creating a cycle in the tree? _(Tests cycle awareness: a naive recursion would loop forever, so they need a visited set keyed by component identity and a decision about how to treat a self-referential design.)_ - How would you also return the depth at which each part first appears, alongside its total count? _(Tests extending the threaded state: pass depth down in parallel with the multiplier and record the minimum depth seen per name.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the-sum-of-its-parts) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.