How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Tesla.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Tesla during technical interviews.

Coordinate workers across two exclusive targets

Company: Tesla

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given two exclusive resources (targets) labeled **"A"** and **"B"**. You need to start **N = 10** parallel workers (e.g., processes or threads), each of which performs: 1. `setup()` (may take variable time) 2. `run(target)` where `target` must be either **"A"** or **"B"** The functions below must be treated as black boxes and **must not be modified**: ```python def setup(): # DO NOT TOUCH ... def run(target): # DO NOT TOUCH ... ``` ### Requirements - At any point in time, **no more than one** worker may be executing `run("A")`. - At any point in time, **no more than one** worker may be executing `run("B")`. - You should **maximize utilization** of both targets: if there are workers ready to call `run(...)`, and a target is free, some worker should run on that target (i.e., don’t unnecessarily serialize all work on a single target). - Your solution should be safe even if `run(target)` raises or the worker exits unexpectedly (i.e., resources must not be permanently lost). ### Task Implement the worker logic and any required shared synchronization so that starting 10 parallel copies of `main()` will satisfy the requirements. You may assume Python and typical concurrency primitives (e.g., locks, semaphores, queues), and you may structure the driver code that spawns the 10 workers.

Quick Answer: This question evaluates proficiency in concurrent programming and synchronization, focusing on safe resource coordination, mutual exclusion, utilization maximization, and fault-tolerant handling of worker failures.

In the original system-design interview question, each worker does `setup()` and then calls `run(target)` where `target` is either `"A"` or `"B"`. Only one worker may be running on `A` at a time, and only one worker may be running on `B` at a time. To make this judgeable as a coding problem, each worker `i` is modeled by two numbers: `setup_times[i]`, the time when that worker finishes setup and becomes ready, and `run_times[i]`, the amount of time it occupies whichever target it gets. Your task is to simulate a correct high-utilization scheduler. Scheduling rules: 1. A worker cannot start `run(...)` before its setup is finished. 2. Targets `A` and `B` are exclusive: each target can run at most one worker at a time. 3. If at least one worker is waiting and a target is free, a worker must start immediately at that time (do not leave a target idle unnecessarily). 4. Among waiting workers, always choose the worker with the earliest setup completion time; if tied, choose the smaller worker index. 5. If both targets are free at the same moment and workers are waiting, assign target `A` first, then target `B`. 6. If a worker becomes ready at exactly the same time a target becomes free, it may start immediately. Return the schedule as a list of tuples `(worker_index, target, start_time, end_time)` in the order workers start running. If two workers start at the same time, the tuple using target `A` must appear before the tuple using target `B`.

Constraints

0 <= n <= 100000
len(setup_times) == len(run_times) == n
0 <= setup_times[i] <= 10^9
1 <= run_times[i] <= 10^9

Examples

Input: ([], [])

Expected Output: []

Explanation: There are no workers, so the schedule is empty.

Input: ([0, 0, 1], [5, 2, 3])

Expected Output: [(0, 'A', 0, 5), (1, 'B', 0, 2), (2, 'B', 2, 5)]

Explanation: Workers 0 and 1 are both ready at time 0, so A gets worker 0 and B gets worker 1. Worker 2 becomes ready at time 1 and starts on B as soon as B frees at time 2.

Input: ([0, 3, 3], [3, 2, 1])

Expected Output: [(0, 'A', 0, 3), (1, 'A', 3, 5), (2, 'B', 3, 4)]

Explanation: Worker 0 starts on A at time 0. At time 3, workers 1 and 2 are ready and both targets are free, so A is assigned first to worker 1 and then B to worker 2.

Input: ([0, 1, 1, 1], [4, 3, 2, 1])

Expected Output: [(0, 'A', 0, 4), (1, 'B', 1, 4), (2, 'A', 4, 6), (3, 'B', 4, 5)]

Explanation: Worker 1 takes the idle B at time 1. Workers 2 and 3 wait until time 4, when both targets free at once; tied setup times are broken by index, so worker 2 is assigned before worker 3.

Input: ([0, 0, 2, 4], [4, 4, 3, 1])

Expected Output: [(0, 'A', 0, 4), (1, 'B', 0, 4), (2, 'A', 4, 7), (3, 'B', 4, 5)]

Explanation: Worker 2 has been waiting since time 2. At time 4, both targets free and worker 3 becomes ready; worker 2 is chosen first for A, then worker 3 gets B.

Input: ([5], [2])

Expected Output: [(0, 'A', 5, 7)]

Explanation: Both targets are idle until time 5. With one ready worker and both targets free, target A is assigned first.

Hints

Treat setup completions and target releases as time-ordered events. You do not need real threads for the judge version.
Use one structure for workers that are ready to run, and another structure to track when each busy target becomes free.

Quick Overview

This question evaluates proficiency in concurrent programming and synchronization, focusing on safe resource coordination, mutual exclusion, utilization maximization, and fault-tolerant handling of worker failures.