Count Servers With At Least k Consecutive Failed Health Checks
Company: Akuna Capital
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A fleet of servers reports health checks into one shared log. Given the log in chronological order and a threshold `k`, count how many servers failed at least `k` of their own checks in a row.
The candidate's report says only that the task counts servers with consecutive failures; this version fixes the exact rule, including the threshold `k`, in Rules below.
### Function Signature
```python
def count_servers_with_failure_streak(logs: list[list[str]], k: int) -> int:
```
### Rules
- Each entry of `logs` is `[server_id, status]`, where `status` is either `"pass"` or `"fail"`. Entries are listed in chronological order.
- A server's checks are the entries with its `server_id`, in log order. Entries for other servers that fall between them neither break nor extend its run.
- A failure run is a maximal sequence of consecutive `"fail"` checks of one server; a `"pass"` check of that same server ends the run.
- A server is counted when at least one of its failure runs has length `k` or more. Each server is counted at most once.
- Return the number of counted servers as a single integer.
### Constraints
- `1 <= len(logs) <= 10^5`
- `1 <= k <= 10^5`
- `server_id` has 1 to 20 characters, each a lowercase English letter or a digit.
- `status` is exactly `"pass"` or `"fail"`.
### Examples
**Example 1**
```text
Input: logs = [["a", "fail"], ["b", "fail"], ["a", "fail"], ["b", "pass"], ["a", "fail"], ["b", "fail"]], k = 3
Output: 1
```
Server `a` has the checks fail, fail, fail: one run of length 3, so it is counted. Server `b` has fail, pass, fail, so its longest run is 1.
**Example 2**
```text
Input: logs = [["x", "fail"], ["x", "pass"], ["x", "fail"], ["y", "pass"], ["x", "fail"]], k = 2
Output: 1
```
Server `x` has the checks fail, pass, fail, fail; its last two checks form a run of length 2. The `"pass"` between them belongs to `y`, so it does not break `x`'s run. Server `y` never fails.
**Example 3**
```text
Input: logs = [["s1", "pass"], ["s2", "fail"], ["s1", "fail"]], k = 2
Output: 0
```
Each server's longest failure run has length 1.
Overview: Given a chronological log of server health checks and a threshold k, count how many servers failed at least k of their own checks in a row. Tests per-server tracking over an interleaved event stream and careful handling of where each failure run starts and ends.
A fleet of servers reports health checks into one shared log. You are given the log `logs` in chronological order and an integer threshold `k`. Count how many servers failed at least `k` of their own checks in a row.
Implement `count_servers_with_failure_streak(logs, k)`, which returns an integer.
### Rules
- Each entry of `logs` is `[server_id, status]`, where `status` is either `"pass"` or `"fail"`. Entries are listed in chronological order.
- A server's checks are the entries with its `server_id`, in log order. Entries for other servers that fall between them neither break nor extend its run.
- A failure run is a maximal sequence of consecutive `"fail"` checks of one server; a `"pass"` check of that same server ends the run.
- A server is counted when at least one of its failure runs has length `k` or more. Each server is counted at most once.
- Return the number of counted servers as a single integer.
### Constraints
- `1 <= len(logs) <= 10^5`
- `1 <= k <= 10^5`
- `server_id` has 1 to 20 characters, each a lowercase English letter or a digit.
- `status` is exactly `"pass"` or `"fail"`.
The answer is at most the number of distinct servers (at most 10^5), so no value here exceeds 2^31 - 1 and a 32-bit `int` suffices in every language.
### Example 1
```text
Input: logs = [["a", "fail"], ["b", "fail"], ["a", "fail"], ["b", "pass"], ["a", "fail"], ["b", "fail"]], k = 3
Output: 1
```
Server `a` has the checks fail, fail, fail: one run of length 3, so it is counted. Server `b` has fail, pass, fail, so its longest run is 1.
### Example 2
```text
Input: logs = [["x", "fail"], ["x", "pass"], ["x", "fail"], ["y", "pass"], ["x", "fail"]], k = 2
Output: 1
```
Server `x` has the checks fail, pass, fail, fail; its last two checks form a run of length 2. The `"pass"` between them belongs to `y`, so it does not break `x`'s run. Server `y` never fails.
Constraints
- 1 <= len(logs) <= 10^5
- 1 <= k <= 10^5
- server_id has 1 to 20 characters, each a lowercase English letter or a digit.
- status is exactly "pass" or "fail".
Examples
Input: ([['a', 'fail'], ['b', 'fail'], ['a', 'fail'], ['b', 'pass'], ['a', 'fail'], ['b', 'fail']], 3)
Expected Output: 1
Explanation: Source Example 1: a has fail, fail, fail (a run of exactly k = 3, counted); b has fail, pass, fail (longest run 1).
Input: ([['x', 'fail'], ['x', 'pass'], ['x', 'fail'], ['y', 'pass'], ['x', 'fail']], 2)
Expected Output: 1
Explanation: Source Example 2, interleaving regression: y's pass between x's last two fails does not break x's run of 2; y never fails.
Hints
- Look only at each server's own checks, in log order; an entry for a different server does not affect that server's run.
- A "pass" from the same server ends its current run, and the threshold k applies to the length of a single run, not to the server's total number of failures.
- A server can reach the threshold more than once, or in a run that is still open when the log ends; it still counts exactly once.