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
```
Overview: 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.
A deployment system keeps a log of every release it has ever shipped, ordered oldest first and indexed from zero. Each entry records whether that release was broken.
Once a release breaks, every release after it inherits the same defect, so the log is **monotonic**: no working release ever appears after a broken one. The log therefore always has the shape `False, False, ..., True, True, ..., True` -- a (possibly empty) block of working releases followed by a (possibly empty) block of broken ones.
You are given the log as a list of booleans `bad`, where `bad[i]` is `True` exactly when release `i` is broken. Return the zero-based index of the **earliest broken release**. If no release in the log is broken, return `-1`.
The log can be very large, so a solution that inspects only a small number of entries is preferred over one that reads every entry.
## Output semantics
The answer is a single integer and is always unique. Monotonicity guarantees there is at most one index that is broken and whose predecessor (if any) works, so no tie-breaking rule is needed.
Return `-1`, and only `-1`, when the log contains no broken release. An empty log contains no broken release and therefore also returns `-1`.
## Examples
**Example 1**
```text
Input: bad = [False, False, True, True, True]
Output: 2
```
Releases 0 and 1 work. Release 2 is the first broken one, and releases 3 and 4 inherit the same defect.
**Example 2**
```text
Input: bad = [False, False]
Output: -1
```
Every release in the log works, so there is no earliest broken release and the sentinel `-1` is returned.
**Example 3**
```text
Input: bad = [True]
Output: 0
```
The very first release is already broken.
Constraints
- 0 <= len(bad) <= 1_000_000
- Every element of bad is a boolean: True or False.
- bad is monotonic: no False appears at any index after a True, so bad always has the form False*, True*.
- The empty log is permitted by the lower bound 0 <= len(bad); it contains no broken release and returns -1.
- The return value is either the sentinel -1 or an index in [0, len(bad) - 1], so it always lies in [-1, 999_999]. Every value and every intermediate index therefore fits comfortably in a 32-bit signed integer -- int is sufficient in Java and C++ -- and nothing comes anywhere near 2^53.
Examples
Input: ([],)
Expected Output: -1
Input: ([False],)
Expected Output: -1
Hints
- Monotonicity means the log is already sorted: every False sits before every True. That is exactly the precondition a search that halves its range needs.
- Instead of asking "which entry is broken?", ask "is the earliest broken release at or before index i?". That predicate is False on a prefix of the log and True on the rest, so you can decide which half to discard from a single lookup.
- Carry the best (smallest) broken index you have seen so far. Landing on a broken release means you can record it and keep searching strictly to its left; landing on a working one means everything to the left works too. If you finish without ever recording an index, the answer is the sentinel.