Simulate Modulo-Assigned Document Indexers with Wrap-Around and Rank the Busiest
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Documents are indexed through a processing queue served by `m` indexers, numbered `0` to `m - 1`. Document `i` (0-based) arrives at time `queue_time[i]` and needs `processing_time[i]` time units. It goes to indexer `i mod m` if that indexer is not busy. Otherwise it goes to the next indexer that is not busy, trying `i mod m + 1`, `i mod m + 2`, and so on, wrapping around from `m - 1` to `0`. If every indexer is busy, the document is dropped.
- Step 1: report the total number of documents processed successfully, and the indexer that processed the most documents.
- Step 2: report the top `k` indexers and the share of the processed documents that they handled.
### Function Signature
```python
def index_documents(m: int, queue_time: list[int], processing_time: list[int], k: int) -> tuple[int, int, list[int], int]:
```
Return the tuple `(processed, busiest, top_k, top_k_count)`.
### Rules
- Documents are handled in index order, and `queue_time` is non-decreasing.
- An indexer that starts a document at time `s` with processing time `p` is busy during `[s, s + p)` and free again from time `s + p` onward. A document that arrives exactly at `s + p` can be assigned to it. The original problem does not settle this boundary; this version fixes it.
- A document arriving at time `t` tries indexers in the order `i mod m`, `(i mod m) + 1`, ..., wrapping to `0` after `m - 1`, and is assigned to the first one that is free at time `t`. If all `m` indexers are busy, the document is dropped and counts for no one.
- `processed` is the number of documents that were assigned.
- Rank the indexers by the number of documents they processed, most first, and break ties by the smaller indexer id. Indexers that processed nothing still take part in the ranking. `busiest` is the first indexer in this ranking, and `top_k` lists the first `k`, in ranking order.
- `top_k_count` is the total number of documents processed by the indexers in `top_k`. The share asked for in Step 2 is `top_k_count / processed`. It is returned as a count so that the answer is exact.
### Constraints
- `1 <= m <= 10^5`
- `1 <= n <= 10^5`, where `n = len(queue_time) == len(processing_time)`
- `0 <= queue_time[i] <= 10^9`, and `queue_time` is non-decreasing
- `1 <= processing_time[i] <= 10^9`, so every finish time is at most `2 * 10^9` and fits in a 32-bit signed integer
- `1 <= k <= m`
### Examples
**Example 1**
```text
Input: m = 3, queue_time = [1, 2, 3, 7], processing_time = [5, 4, 3, 2], k = 2
Output: (4, 0, [0, 1], 3)
```
Documents 0, 1 and 2 go to indexers 0, 1 and 2, which are all busy until time 6. Document 3 arrives at time 7. `3 mod 3 = 0`, and indexer 0 is free again, so it takes the document. The counts are `[2, 1, 1]`: all 4 documents are processed and indexer 0 is the busiest. Indexers 1 and 2 tie, so the smaller id goes into the top 2. The top 2 handled 3 of the 4 documents, a 75% share.
**Example 2**
```text
Input: m = 3, queue_time = [0, 0, 0, 1, 2, 5], processing_time = [1, 9, 9, 4, 3, 2], k = 2
Output: (5, 0, [0, 1], 4)
```
- Documents 0, 1 and 2 go to indexers 0, 1 and 2. Indexer 0 is busy until time 1, and indexers 1 and 2 until time 9.
- Document 3 arrives at time 1. Indexer 0 is free from time 1, so it takes the document and is busy until 5.
- Document 4 arrives at time 2. Indexers 1, 2 and 0 are all busy, so the document is dropped.
- Document 5 arrives at time 5. Indexer 2 is busy, so it wraps around to indexer 0, which is free from time 5.
The counts are `[3, 1, 1]`, and 5 documents are processed. The top 2 handled 4 of them, an 80% share.
**Example 3**
```text
Input: m = 1, queue_time = [0, 1], processing_time = [2, 1], k = 1
Output: (1, 0, [0], 1)
```
The single indexer is still busy when document 1 arrives, so document 1 is dropped.
Overview: Simulate documents assigned to indexers by index modulo m, falling through to the next free indexer with wrap-around and dropping documents when all are busy, then report processed totals, the busiest indexer and the top-k share. Tests event simulation, finding the next free slot efficiently and precise tie rules.
Documents are indexed through a processing queue served by `m` indexers, numbered `0` to `m - 1`. Document `i` (0-based) arrives at time `queue_time[i]` and needs `processing_time[i]` time units. It goes to indexer `i mod m` if that indexer is not busy. Otherwise it goes to the next indexer that is not busy, trying `i mod m + 1`, `i mod m + 2`, and so on, wrapping around from `m - 1` to `0`. If every indexer is busy, the document is dropped.
Answer two questions about the run:
- **Step 1:** the total number of documents processed successfully, and the indexer that processed the most documents.
- **Step 2:** the top `k` indexers and the share of the processed documents that they handled.
Implement `index_documents(m, queue_time, processing_time, k)` and return `(processed, busiest, top_k, top_k_count)`.
### Rules
- Documents are handled in index order (`0, 1, 2, ...`), and `queue_time` is non-decreasing, so several documents can share an arrival time.
- An indexer that starts a document at time `s` with processing time `p` is busy during `[s, s + p)` and free again from time `s + p` onward. A document that arrives exactly at `s + p` can be assigned to it.
- A document arriving at time `t` tries indexers in the order `i mod m`, `(i mod m) + 1`, ..., wrapping to `0` after `m - 1`, and is assigned to the first one that is free at time `t`, starting there at time `t`. If all `m` indexers are busy, the document is dropped and counts for no one.
- `processed` is the number of documents that were assigned.
- Rank all `m` indexers by the number of documents they processed, most first, and break ties by the smaller indexer id. Indexers that processed nothing still take part in the ranking. `busiest` is the first indexer in this ranking, and `top_k` lists the first `k` indexers, in ranking order.
- `top_k_count` is the total number of documents processed by the indexers in `top_k`. The share asked for in Step 2 is `top_k_count / processed`; it is returned as a count so that the answer is exact.
### Return value per language
- Python: the tuple `(processed, busiest, top_k, top_k_count)`, with `top_k` a list.
- JavaScript: the array `[processed, busiest, top_k, top_k_count]`.
- Java: a `java.util.List<Object>` holding `processed`, `busiest`, `top_k` (a `java.util.List<Integer>`) and `top_k_count`, in that order.
- C++: a `std::tuple<int, int, std::vector<int>, int>`.
### Constraints
- `1 <= m <= 10^5`
- `1 <= n <= 10^5`, where `n = len(queue_time) == len(processing_time)`
- `0 <= queue_time[i] <= 10^9`, and `queue_time` is non-decreasing
- `1 <= processing_time[i] <= 10^9`, so every finish time is at most `2 * 10^9` and fits in a 32-bit signed integer
- `1 <= k <= m`
No input value, finish time or returned count exceeds `2^31 - 1`, so 32-bit `int` suffices in Java and C++.
### Example 1
```text
Input: m = 3, queue_time = [1, 2, 3, 7], processing_time = [5, 4, 3, 2], k = 2
Output: (4, 0, [0, 1], 3)
```
Documents 0, 1 and 2 go to indexers 0, 1 and 2, which are all busy until time 6. Document 3 arrives at time 7. `3 mod 3 = 0`, and indexer 0 is free again, so it takes the document. The counts are `[2, 1, 1]`: all 4 documents are processed and indexer 0 is the busiest. Indexers 1 and 2 tie, so the smaller id goes into the top 2. The top 2 handled 3 of the 4 documents, a 75% share.
### Example 2
```text
Input: m = 3, queue_time = [0, 0, 0, 1, 2, 5], processing_time = [1, 9, 9, 4, 3, 2], k = 2
Output: (5, 0, [0, 1], 4)
```
- Documents 0, 1 and 2 go to indexers 0, 1 and 2. Indexer 0 is busy until time 1, and indexers 1 and 2 until time 9.
- Document 3 arrives at time 1. Indexer 0 is free from time 1, so it takes the document and is busy until 5.
- Document 4 arrives at time 2. Indexers 1, 2 and 0 are all busy, so the document is dropped.
- Document 5 arrives at time 5. Indexer 2 is busy, so it wraps around to indexer 0, which is free from time 5.
The counts are `[3, 1, 1]`, and 5 documents are processed. The top 2 handled 4 of them, an 80% share.
Constraints
- 1 <= m <= 10^5
- 1 <= n <= 10^5, where n = len(queue_time) == len(processing_time)
- 0 <= queue_time[i] <= 10^9, and queue_time is non-decreasing
- 1 <= processing_time[i] <= 10^9, so every finish time is at most 2 * 10^9 and fits in a 32-bit signed integer
- 1 <= k <= m
Examples
Input: (3, [1, 2, 3, 7], [5, 4, 3, 2], 2)
Expected Output: (4, 0, [0, 1], 3)
Explanation: Source Example 1: indexer 0 is free again at time 7; tied indexers 1 and 2 resolve to the smaller id.
Input: (3, [0, 0, 0, 1, 2, 5], [1, 9, 9, 4, 3, 2], 2)
Expected Output: (5, 0, [0, 1], 4)
Explanation: Source Example 2: release exactly at s + p, one all-busy drop, and a wrap from indexer 2 to indexer 0.
Hints
- The first indexer tried by document i is always i mod m, however many earlier documents were dropped.
- An indexer whose document finishes at s + p can take a document arriving at exactly s + p, but not one arriving at s + p - 1.
- Every indexer, including one that processed nothing, is part of the ranking, and equal counts are ordered by the smaller id.