Optimize bread-factory pipeline for max profit

Q: Optimize bread-factory pipeline for max profit

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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Optimize bread-factory pipeline for max profit

Overview

Comments (0)