Find the First Bad Version in a Monotonic Release History
Company: Qualcomm
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find the First Bad Version in a Monotonic Release History
You are given a release history as a boolean array `bad`. Versions use zero-based indices. Once a bad version appears, every later version is also bad, so the array has the form `False, ..., False, True, ..., True`.
Return the index of the first bad version. Return `-1` if every version is good.
## Function Signature
```python
def first_bad_version(bad: list[bool]) -> int:
...
```
## Constraints
- `0 <= len(bad) <= 1_000_000`
- `bad` is monotonic: no `False` value appears after a `True` value.
- The implementation should remain efficient when the history is very large.
## Examples
```text
Input: bad = [False, False, True, True, True]
Output: 2
```
```text
Input: bad = [False, False]
Output: -1
```
```text
Input: bad = [True]
Output: 0
```
Quick Answer: Find the earliest bad entry in a monotonic release history, returning -1 when every version is good. This compact coding prompt tests boundary-safe binary search, empty and all-good inputs, first-element failures, loop invariants, and logarithmic performance on histories with up to a million versions.