Optimize bread-factory pipeline for max profit
Company: Roblox
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You can assemble a production line by choosing modules of three types: Mixers, Ovens, Packers. Each module i has (type, build_cost_i, throughput_i units/hour). You have budget B and sale_price per loaf and variable_cost per loaf. Throughput of the line is limited by the bottleneck: floor(sum_throughput(Mixers), sum_throughput(Ovens), sum_throughput(Packers)). Choose a multiset of modules to maximize hourly profit = sale_price*throughput − variable_cost*throughput − sum(build_cost_i amortized/hour). Assume amortization_rate per hour is given to convert build_cost_i into cost/hour. Inputs: B up to 10^6, up to 2,000 modules. 1) Design an algorithm to select modules subject to total build_cost ≤ B that maximizes profit. 2) Provide time/space complexity and justify optimality or approximation guarantees. 3) Explain how you would extend the solution if each module also has a warmup_time that temporarily reduces its throughput for the first T minutes (hint: horizon-based planning or min-cut on a time-expanded network).
Overview: This question evaluates skills in combinatorial optimization, budgeted resource allocation, bottleneck throughput modeling, and algorithm design with cost amortization for maximizing profit under constraints.
Read the full Roblox Data Scientist interview experience this question came from
Community answers
Answer by KouJiaoDaHan
Module = Dict[str, int | str]
def _stage_min_cost_at_least(
modules: List[Tuple[int, int, int]]
) -> Tuple[List[int], List[int], List[List[Tuple[int, bool]]]]:
"""
modules: list of (original_index, build_cost, throughput)
Returns:
best_cost_at_least[t]: min cost to get throughput >= t
best_exact_sum[t]: exact throughput sum used for that min cost
parents: backtracking table for reconstructing chosen modules
"""
total_throughput = sum(throughput for , , throughput in modules)
inf = 10**18
dp = [inf] * (total_throughput + 1)
dp[0] = 0
parents: List[List[Tuple[int, bool]]] = []
for _, cost, throughput in modules:
new_dp = dp[:]
parent = [(s, False) for s in range(total_throughput + 1)]
for s in range(total_throughput - throughput + 1):
if dp[s] == inf:
continue
ns = s + throughput
candidate_cost = dp[s] + cost
if candidate_cost < new_dp[ns]:
new_dp[ns] = candidate_cost
parent[ns] = (s, True)
parents.append(parent)
dp = new_dp
best_cost_at_least = [inf] * (total_throughput + 2)
best_exact_sum = [-1] * (total_throughput + 2)
for need in range(total_throughput, -1, -1):
if dp[need] <= best_cost_at_least[need + 1]:
best_cost_at_least[need] = dp[need]
best_exact_sum[need] = need
else:
best_cost_at_least[need] = best_cost_at_least[need + 1]
best_exact_sum[need] = best_exact_sum[need + 1]
return best_cost_at_least, best_exact_sum, parents
def _reconstruct_stage(
modules: List[Tuple[int, int, int]],
parents: List[List[Tuple[int, bool]]],
exact_sum: int,
) -> List[int]:
selected = []
s =