Katkat
Back

Find the First Bad Version in a Monotonic Release History

QualcommSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

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

Input: bad = [False, False, True, True, True]
Output: 2

Input: bad = [False, False]
Output: -1

Input: bad = [True]
Output: 0