Apple: Leaf Parts Needed for Each Mac Build Order
Before a production run, Mac operations planners turn each build order into a parts list for the suppliers.
- Difficulty: Hard
- Topics: Subqueries, Joins, Aggregation
- Dialect: MySQL
- Problem: #616
Problem statement
Before a production run, Mac operations planners turn each build order into a parts list for the suppliers. A product is assembled from parts listed in a bill of materials, and a part can itself be an assembly with lines of its own, nested to any depth. A leaf part is one with no lines of its own in BomLine — it is bought, not built.
For every build order, return order_id, part_name and total_qty: how many of each leaf part the order needs, multiplying the quantities along every path from the ordered part down to the leaf (units × each qty_per on the way) and adding up a leaf reached by several paths. An order for a part that is itself a leaf needs just that part, units times. Order the rows by order_id, then part_name.
A practice scenario set at Apple: the tables and data are invented, and this is not a question from, or endorsed by, Apple.
Tables
Table: Part
| Column | Type |
|---|---|
| part_id | varchar |
| part_name | varchar |
Primary key: part_id.
Every product, sub-assembly and component; names are unique.
Table: BomLine
| Column | Type |
|---|---|
| parent_id | varchar |
| child_id | varchar |
| qty_per | int |
Primary key: parent_id, child_id.
One unit of parent_id needs qty_per units of child_id. The structure never loops back on itself.
Table: BuildOrder
| Column | Type |
|---|---|
| order_id | int |
| part_id | varchar |
| units | int |
Primary key: order_id.
A request to build units of a part — usually a finished product.
Examples
Example 1
Part
| part_id | part_name |
|---|---|
| MBA13 | MacBook Air 13 |
| LOGIC | Logic board |
| TOPC | Top case |
| M4 | M4 chip |
| SCRW | Pentalobe screw |
| KEYB | Keyboard |
| CELL | Battery cell |
BomLine
| parent_id | child_id | qty_per |
|---|---|---|
| MBA13 | LOGIC | 1 |
| MBA13 | TOPC | 1 |
| MBA13 | SCRW | 10 |
| LOGIC | M4 | 1 |
| LOGIC | SCRW | 4 |
| TOPC | KEYB | 1 |
| TOPC | CELL | 3 |
| TOPC | SCRW | 6 |
BuildOrder
| order_id | part_id | units |
|---|---|---|
| 1 | MBA13 | 2 |
| 2 | TOPC | 5 |
| 3 | CELL | 40 |
Output
| order_id | part_name | total_qty |
|---|---|---|
| 1 | Battery cell | 6 |
| 1 | Keyboard | 2 |
| 1 | M4 chip | 2 |
| 1 | Pentalobe screw | 40 |
| 2 | Battery cell | 15 |
| 2 | Keyboard | 5 |
| 2 | Pentalobe screw | 30 |
| 3 | Battery cell | 40 |
How to solve Apple: Leaf Parts Needed for Each Mac Build Order
A bill of materials is a tree (strictly, a graph without cycles) of unknown depth, so the natural tool is a recursive CTE. The anchor is one row per build order: the ordered part with quantity units. The recursive step takes every row produced so far, joins the BOM lines whose parent is that part, and emits each child with quantity qty × qty_per. The recursion stops by itself at parts that have no lines, and it cannot run forever because the structure has no cycles.
The explosion holds every level — products, sub-assemblies and leaves — so keep only the leaf rows: parts with no BOM line of their own (NOT EXISTS). A shared component such as the screw in the example arrives along several paths (directly from the laptop, through the logic board and through the top case), each with its own multiplied quantity, and the final SUM per order and part adds them: 2 × 10 + 2 × 4 + 2 × 6 = 40 screws for order 1. An order for a leaf itself never recurses and keeps its own row.
The alternative explodes each ordered part once, per single unit (1 at the root), sums the per-unit leaf needs, and only then multiplies by each order's units — handy when many orders share a product. Both walk each BOM path once per root.
Reference solution (MySQL)
WITH RECURSIVE explode AS (
SELECT order_id, part_id, units AS qty
FROM BuildOrder
UNION ALL
SELECT e.order_id, l.child_id, e.qty * l.qty_per
FROM explode e
JOIN BomLine l ON l.parent_id = e.part_id
)
SELECT e.order_id, p.part_name, SUM(e.qty) AS total_qty
FROM explode e
JOIN Part p ON p.part_id = e.part_id
WHERE NOT EXISTS (SELECT 1 FROM BomLine l WHERE l.parent_id = e.part_id)
GROUP BY e.order_id, e.part_id, p.part_name
ORDER BY e.order_id, p.part_nameAnother way
WITH RECURSIVE tree AS (
SELECT part_id AS root_id, part_id, 1 AS per_unit
FROM (SELECT DISTINCT part_id FROM BuildOrder) r
UNION ALL
SELECT t.root_id, l.child_id, t.per_unit * l.qty_per
FROM tree t JOIN BomLine l ON l.parent_id = t.part_id
), leaf_per_unit AS (
SELECT root_id, part_id, SUM(per_unit) AS per_unit
FROM tree
WHERE part_id NOT IN (SELECT parent_id FROM BomLine)
GROUP BY root_id, part_id
)
SELECT b.order_id, p.part_name, b.units * u.per_unit AS total_qty
FROM BuildOrder b
JOIN leaf_per_unit u ON u.root_id = b.part_id
JOIN Part p ON p.part_id = u.part_id
ORDER BY b.order_id, p.part_name← Apple: New and Cumulative Unique Apple Arcade Players by Day · Apple: Subscription Billing Lapses Recovered in the Grace Period →