Optimize bread-factory pipeline for max profit

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

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

Quick Answer: This question evaluates skills in combinatorial optimization, budgeted resource allocation, bottleneck throughput modeling, and algorithm design with cost amortization for maximizing profit under constraints.

|Home/Coding & Algorithms/Roblox
Roblox logo
Roblox
Oct 13, 2025, 9:49 PM
mediumData ScientistOnsiteCoding & Algorithms
8
0

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_pricethroughput − variable_costthroughput − 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).

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...