Optimize Station Sequence for Maximum Car Output in Simulation
Company: TikTok
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
The Car-Building mini-game lets you sequence chassis, engine, and paint stations with limited buffers.
##### Question
Describe a strategy to maximize completed cars within a fixed 5-minute simulation window.
##### Hints
Consider critical-path scheduling, queue length, and backpressure control.
Quick Answer: This question evaluates a candidate's skills in scheduling and throughput optimization, including queue management and simulation-based performance analysis within constrained buffering and station sequencing.
You run a three-stage pipeline of stations: S1 (chassis), S2 (engine), S3 (paint). Processing times are t1, t2, t3 time units per item. Between S1 and S2 is buffer12 with capacity b12; between S2 and S3 is buffer23 with capacity b23. Initially, all stations are idle and both buffers are empty. There is unlimited raw input for S1. Each station can process only one item at a time. Transfers are instantaneous and the following blocking-before-service rules apply: (1) S1 may start only if buffer12 has a free slot; starting reserves one slot in buffer12; when S1 finishes, it releases the reservation and adds one item to buffer12. (2) S2 may start only if buffer12 has at least one item and buffer23 has a free slot; starting removes one item from buffer12 and reserves one slot in buffer23; when S2 finishes, it releases the reservation and adds one item to buffer23. (3) S3 may start only if buffer23 has at least one item; starting removes one item from buffer23; when S3 finishes, one completed car is produced. Given times = [t1, t2, t3], buffers = [b12, b23], and a simulation window T, return the maximum number of cars whose S3 completion time is less than or equal to T. Implement max_cars(times, buffers, T).
Constraints
- times has length 3 and buffers has length 2
- 1 <= times[i] <= 10^5
- 1 <= buffers[j] <= 10^5
- 0 <= T <= 10^6
- All values are integers
Hints
- Simulate an event-driven pipeline with three single-server stations and two finite buffers.
- Start stations in downstream-to-upstream order (S3, then S2, then S1) at each event to relieve backpressure.
- Use blocking-before-service: require downstream capacity before starting, and track reserved output slots so completions never block.