Detect timed-out RPC calls from paired start and end log records
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A service writes a log record when a remote procedure call (RPC) starts and another when it ends. Given the log, in time order, and a timeout, report every call that ran for longer than the timeout. A call that has started but has no end record is still running when the log ends, and it counts as timed out if it has already been running for longer than the timeout at that point.
### Function Signature
```python
def timed_out_calls(logs: list[tuple[int, int, str]], timeout: int) -> list[int]:
```
Each record is `(call_id, timestamp, kind)`, where `kind` is `"start"` or `"end"`.
### Rules
- Records are listed in non-decreasing order of `timestamp`.
- Each `call_id` has exactly one `"start"` record and at most one `"end"` record. If a call has an end record, it appears later in the list than that call's start record.
- Let `now` be the timestamp of the last record in the list. A call's running time is `end_timestamp - start_timestamp` if it has an end record, and `now - start_timestamp` otherwise.
- A call is timed out when its running time is strictly greater than `timeout`. A running time exactly equal to `timeout` is not a timeout.
- Return the `call_id` of every timed-out call, sorted by start timestamp in ascending order, with ties broken by `call_id` in ascending order. Because every call has the same timeout, this is also the order in which their deadlines expire. Return an empty list if no call timed out.
### Constraints
- `1 <= len(logs) <= 200000`
- `0 <= call_id <= 10^9`
- `0 <= timestamp <= 10^9`
- `0 <= timeout <= 10^9`
- Every sum `start_timestamp + timeout` is at most `2 * 10^9`, which fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: logs = [(1, 0, "start"), (2, 1, "start"), (1, 3, "end"), (3, 4, "start"), (2, 9, "end"), (3, 10, "end")], timeout = 5
Output: [2, 3]
```
Call 1 ran 3 - 0 = 3 units. Call 2 ran 9 - 1 = 8 units and call 3 ran 10 - 4 = 6 units, both more than 5. Call 2 started at time 1 and call 3 at time 4, which gives the order.
**Example 2**
```text
Input: logs = [(7, 2, "start"), (8, 2, "start"), (8, 6, "end"), (9, 7, "start")], timeout = 4
Output: [7]
```
The log ends at time 7. Call 7 has no end record and has been running for 7 - 2 = 5 units, which is more than 4. Call 8 ran exactly 6 - 2 = 4 units, which is not more than the timeout. Call 9 has no end record and has been running for 7 - 7 = 0 units.
**Example 3**
```text
Input: logs = [(5, 0, "start"), (4, 0, "start"), (5, 10, "end"), (4, 10, "end")], timeout = 3
Output: [4, 5]
```
Both calls ran 10 units and both started at time 0, so the tie is broken by `call_id`.
Overview: Given RPC log records that mark when each call starts and ends, in time order, plus a timeout, return every call that ran longer than the timeout, including calls still open when the log ends. Tests per-call bookkeeping over an ordered log, strict boundary rules and a deterministic output order.
A service writes a log record when a remote procedure call (RPC) starts and another when it ends. Given the log, in time order, and a timeout, report every call that ran for longer than the timeout. A call that has started but has no end record is still running when the log ends, and it counts as timed out if it has already been running for longer than the timeout at that point.
Each record is `(call_id, timestamp, kind)`, where `kind` is `"start"` or `"end"`.
### Rules
- Records are listed in non-decreasing order of `timestamp`.
- Each `call_id` has exactly one `"start"` record and at most one `"end"` record. If a call has an end record, it appears later in the list than that call's start record.
- Let `now` be the timestamp of the last record in the list (that record may be a start or an end record). A call's running time is `end_timestamp - start_timestamp` if it has an end record, and `now - start_timestamp` otherwise.
- A call is timed out when its running time is strictly greater than `timeout`. A running time exactly equal to `timeout` is not a timeout.
- Return the `call_id` of every timed-out call, sorted by start timestamp in ascending order, with ties broken by `call_id` in ascending order. Because every call has the same timeout, this is also the order in which their deadlines expire. Return an empty list if no call timed out.
### Record format by language
- Python: `logs` is a list of `(call_id, timestamp, kind)` tuples.
- JavaScript: each record is an array `[call_id, timestamp, kind]`.
- Java: each record is a `java.util.List<Object>` whose elements 0 and 1 are integers (read them through `Number`) and whose element 2 is a `String`.
- C++: each record is a `std::tuple<int, int, std::string>`.
### Constraints
- `1 <= len(logs) <= 200000`
- `0 <= call_id <= 10^9`
- `0 <= timestamp <= 10^9`
- `0 <= timeout <= 10^9`
- Every sum `start_timestamp + timeout` is at most `2 * 10^9`, which fits in a 32-bit signed integer. No input value, running time or returned `call_id` exceeds `2^31 - 1`, so a 32-bit `int` is enough in Java and C++.
### Example 1
```text
Input: logs = [(1, 0, "start"), (2, 1, "start"), (1, 3, "end"), (3, 4, "start"), (2, 9, "end"), (3, 10, "end")], timeout = 5
Output: [2, 3]
```
Call 1 ran 3 - 0 = 3 units. Call 2 ran 9 - 1 = 8 units and call 3 ran 10 - 4 = 6 units, both more than 5. Call 2 started at time 1 and call 3 at time 4, which gives the order.
### Example 2
```text
Input: logs = [(7, 2, "start"), (8, 2, "start"), (8, 6, "end"), (9, 7, "start")], timeout = 4
Output: [7]
```
The log ends at time 7. Call 7 has no end record and has been running for 7 - 2 = 5 units, which is more than 4. Call 8 ran exactly 6 - 2 = 4 units, which is not more than the timeout. Call 9 has no end record and has been running for 7 - 7 = 0 units.
Constraints
- 1 <= len(logs) <= 200000
- 0 <= call_id <= 10^9
- 0 <= timestamp <= 10^9
- 0 <= timeout <= 10^9
- Every sum start_timestamp + timeout is at most 2 * 10^9, which fits in a 32-bit signed integer; no value exceeds 2^31 - 1.
- kind is exactly "start" or "end".
- Records are listed in non-decreasing order of timestamp.
- Each call_id has exactly one "start" record and at most one "end" record, and an end record appears later in the list than that call's start record.
Examples
Input: ([(42, 100, 'start')], 0)
Expected Output: []
Explanation: Single start record: now is 100, so the call has run 0 units, which is not more than timeout 0.
Input: ([(1, 0, 'start'), (2, 1, 'start'), (1, 3, 'end'), (3, 4, 'start'), (2, 9, 'end'), (3, 10, 'end')], 5)
Expected Output: [2, 3]
Explanation: Source example 1: call 1 ran 3, call 2 ran 8, call 3 ran 6; calls 2 and 3 exceed 5 and are ordered by start time 1 then 4.
Hints
- now comes only from the last record in the list, whatever kind of record it is; it is not necessarily the last end time.
- For each call you need its start timestamp and, if it has one, its end timestamp; a call without an end record is measured up to now.
- Order the answer by start timestamp first and by call_id only when start timestamps are equal, and remember that a running time exactly equal to timeout does not count.