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.
