Find when failures started in log stream
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an array of log entries sorted by timestamp ascending. Each log entry contains:
- `timestamp` (monotonic increasing)
- `status` ∈ {`OK`, `FAIL`}
Assume the system behaves as follows:
- At some time `T` (possibly never), a failure begins.
- **Once a failure begins, every log at time ≥ T has status `FAIL`** (i.e., the statuses are a prefix of `OK`s followed by a suffix of `FAIL`s).
### Task
Return the **earliest timestamp (or index)** at which failure started (the first `FAIL` in the array). If there is no failure, return a sentinel value (e.g., `null` / `-1`).
### Edge cases to consider
- Empty log array
- All logs are `OK`
- All logs are `FAIL`
### Complexity goal
Better than linear time if possible.
Quick Answer: This question evaluates understanding of monotonic sequences and search algorithms (such as binary search), along with algorithmic reasoning about correctness and time-complexity.
Given monotonic OK...FAIL logs, return the first FAIL timestamp or -1 if no failure exists.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([(1,'OK'), (2,'OK'), (3,'FAIL'), (4,'FAIL')],)
Expected Output: 3
Explanation: Failure begins at timestamp 3.
Input: ([(1,'OK'), (2,'OK')],)
Expected Output: -1
Explanation: No failure.
Input: ([(5,'FAIL')],)
Expected Output: 5
Explanation: All fail.
Input: ([],)
Expected Output: -1
Explanation: Empty logs.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.