Apple: Leaf Parts Needed for Each Mac Build Order

Hard
616.

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. 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

ColumnType
part_idvarchar
part_namevarchar

Primary key: part_id.

Every product, sub-assembly and component; names are unique.

Table: BomLine

ColumnType
parent_idvarchar
child_idvarchar
qty_perint

Primary key (together): 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

ColumnType
order_idint
part_idvarchar
unitsint

Primary key: order_id.

A request to build units of a part — usually a finished product.

Example

The rows must come back in the order shown.

Part

part_idpart_name
MBA13MacBook Air 13
LOGICLogic board
TOPCTop case
M4M4 chip
SCRWPentalobe screw
KEYBKeyboard
CELLBattery cell

BomLine

parent_idchild_idqty_per
MBA13LOGIC1
MBA13TOPC1
MBA13SCRW10
LOGICM41
LOGICSCRW4
TOPCKEYB1
TOPCCELL3
TOPCSCRW6

BuildOrder

order_idpart_idunits
1MBA132
2TOPC5
3CELL40

Output

order_idpart_nametotal_qty
1Battery cell6
1Keyboard2
1M4 chip2
1Pentalobe screw40
2Battery cell15
2Keyboard5
2Pentalobe screw30
3Battery cell40
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
part_idvarchar
part_namevarchar

Primary key: part_id.

Every product, sub-assembly and component; names are unique.

Table: BomLine

ColumnType
parent_idvarchar
child_idvarchar
qty_perint

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

ColumnType
order_idint
part_idvarchar
unitsint

Primary key: order_id.

A request to build units of a part — usually a finished product.

Examples

Example 1

Part

part_idpart_name
MBA13MacBook Air 13
LOGICLogic board
TOPCTop case
M4M4 chip
SCRWPentalobe screw
KEYBKeyboard
CELLBattery cell

BomLine

parent_idchild_idqty_per
MBA13LOGIC1
MBA13TOPC1
MBA13SCRW10
LOGICM41
LOGICSCRW4
TOPCKEYB1
TOPCCELL3
TOPCSCRW6

BuildOrder

order_idpart_idunits
1MBA132
2TOPC5
3CELL40

Output

order_idpart_nametotal_qty
1Battery cell6
1Keyboard2
1M4 chip2
1Pentalobe screw40
2Battery cell15
2Keyboard5
2Pentalobe screw30
3Battery cell40

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_name

Another 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 →