Quick Overview

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.

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.

Overview: 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

  1. Simulate an event-driven pipeline with three single-server stations and two finite buffers.
  2. Start stations in downstream-to-upstream order (S3, then S2, then S1) at each event to relieve backpressure.
  3. Use blocking-before-service: require downstream capacity before starting, and track reserved output slots so completions never block.

Loading coding console...

Show the approach

Approach

Use an event-driven simulation of a three-stage pipeline with finite intermediate buffers under blocking-before-service. Maintain two counts per buffer: items currently available for the downstream station and reserved output slots for in-flight jobs upstream. At any time, repeatedly start stations in downstream-to-upstream order (S3, then S2, then S1) while their preconditions hold: S3 consumes an available item from buffer23; S2 consumes one item from buffer12 and reserves a slot in buffer23; S1 reserves a slot in buffer12. Track the next completion time for each station and advance the simulation clock to the earliest completion, processing all completions at that time. Count S3 completions whose finish time is at most T. This ordering relieves backpressure and ensures maximal utilization without violating buffer capacities.

Time complexity:
O(E), where E is the number of station completions up to time T (at most about 3 * T / min(ti))
Space complexity:
O(1)