Calculate Ordered Job Makespan Across Parallel Workers

Question

The question asks the candidate to calculate the makespan of ordered jobs processed across multiple parallel workers.

Codemia · Accepted Answer

To calculate the makespan for ordered jobs across parallel workers, we need to distribute jobs to workers in a way that minimizes the total time taken to complete all jobs. The makespan is defined as the time at which the last job is completed. We can achieve this by simulating the job assignment to workers while keeping track of their current workload.

1. Initialize an array to keep track of the finish time for each worker.
2. Iterate through each job in the ordered list:
   - Assign the job to the worker with the least finish time.
   - Update that worker's finish time by adding the job's duration.
3. The makespan will be the maximum value in the finish time array after all jobs have been assigned.

The time complexity of this algorithm is O(n * m), where n is the number of jobs and m is the number of workers. This is because for each job, we may need to check all workers to find the one with the minimum finish time. The space complexity is O(m) for storing the finish times of the workers.

```python
def calculate_makespan(jobs, num_workers):
    finish_times = [0] * num_workers
    for job in jobs:
        # Find the worker with the minimum finish time
        min_worker = finish_times.index(min(finish_times))
        # Assign the job to this worker
        finish_times[min_worker] += job
    return max(finish_times)

# Example usage
jobs = [2, 4, 6, 8]
num_workers = 2
makespan = calculate_makespan(jobs, num_workers)
print(makespan)  # Output should be 10
```

Consider edge cases such as:
- No jobs (should return 0).
- More workers than jobs (the makespan will be the duration of the longest job).
- Jobs with varying durations and how they affect worker assignment.

Calculate Ordered Job Makespan Across Parallel Workers

Plaid

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Plaid Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string