Count Completed Jobs in a Serial Multi-Worker Pipeline

Question

The question asks the candidate to design a solution that counts the number of completed jobs in a serial multi-worker pipeline.

Codemia · Accepted Answer

To count the completed jobs in a serial multi-worker pipeline, I would implement a solution that utilizes a shared counter to keep track of the number of jobs completed by each worker. Each worker would increment this counter upon finishing its job. I would ensure that access to the counter is thread-safe to prevent race conditions.

The algorithm can be implemented as follows:

1. Initialize a shared counter (e.g., `completed_jobs`) to zero.
2. For each worker, upon job completion, increment the counter.
3. Use a lock or atomic operations to ensure that increments to the counter are thread-safe.

Here is a simple Python code block to illustrate this:
```python
import threading

class JobCounter:
    def __init__(self):
        self.completed_jobs = 0
        self.lock = threading.Lock()

def job_completed(self):
        with self.lock:
            self.completed_jobs += 1

# Example usage
counter = JobCounter()
# Simulate job completion by multiple workers
```

The time complexity of this solution is O(n), where n is the number of jobs completed, as each completion requires a constant time operation to increment the counter. The space complexity is O(1), as we only maintain a single counter regardless of the number of jobs.

I would consider edge cases such as:
- No jobs being completed (the counter remains zero).
- Workers completing jobs at different rates, which should not affect the final count.
- Handling interruptions or failures in job processing, ensuring that the counter reflects only successfully completed jobs.

Using a lock for thread safety may introduce some overhead, which could lead to contention if many workers are trying to update the counter simultaneously. An alternative could be using atomic operations or a concurrent data structure, but this may complicate the implementation. It is essential to balance simplicity and performance based on the expected workload.

Count Completed Jobs in a Serial Multi-Worker Pipeline

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