Rocket Component Cost
Learn this problem
SpaceXINTERNONSITE INTERVIEWProblem statement
Rocket Component Cost
Write code to calculate the total cost of building a rocket. You are provided a map from each part to its cost and another map from each part to the required subparts and their quantities.
The reported dependency representation has the form {part: [[required_part_1, amount_1], [required_part_2, amount_2], ...]}. The source notes that a solution can cache computed costs while traversing component dependencies with DFS or BFS.
Practice Contract
For this exercise, assume parts[i] has direct unit cost directCosts[i]. The aligned rows requiredParts[i] and requiredAmounts[i] list the immediate subparts needed to build one unit of parts[i].
The total cost of one part is its direct cost plus, for every required subpart, the required quantity multiplied by that subpart's total cost. Return the total cost of one targetPart.
Part names are unique, every referenced subpart exists, and the dependency graph is acyclic. Shared subassemblies may be required from multiple places, so avoid recomputing their total costs.
Function
calculateRocketCost(parts: String[], directCosts: long[], requiredParts: String[][], requiredAmounts: int[][], targetPart: String) → longExamples
Example 1
parts = ["rocket","engine","tank","metal"]directCosts = [100,20,1000,5]requiredParts = [["engine","tank"],["metal"],[],[]]requiredAmounts = [[2,1],[100],[],[]]targetPart = "rocket"return = 2140One engine costs 20 + 100 × 5 = 520. The rocket costs 100 + 2 × 520 + 1 × 1000 = 2140.
Example 2
parts = ["rocket"]directCosts = [42]requiredParts = [[]]requiredAmounts = [[]]targetPart = "rocket"return = 42The target has no required subparts, so its total cost is its direct cost.
Example 3
parts = ["rocket","stage","engine","bolt"]directCosts = [0,0,0,2]requiredParts = [["stage","engine"],["engine","bolt"],["bolt"],[]]requiredAmounts = [[2,1],[1,10],[50],[]]targetPart = "rocket"return = 340An engine costs 100, a stage costs 100 + 20 = 120, and the rocket costs 2 × 120 + 100 = 340. Memoization computes the shared engine assembly once.
Constraints
1 ≤ parts.length ≤ 10,000parts.length == directCosts.length == requiredParts.length == requiredAmounts.length- Part names are unique, non-empty, and every required-part name appears in
parts. - For every
i,requiredParts[i].length == requiredAmounts[i].length. 0 ≤ directCosts[i] ≤ 10^9and1 ≤ requiredAmounts[i][j] ≤ 10^6.- The dependency graph is acyclic.
- The answer fits in a signed 64-bit integer.