Build regression detection
A release engineer holds a chronological history of nightly builds. builds carries each build's label in the order it ran, and passed carries the parallel verdict of the smoke suite, true when that build was clean. A regression landed once and was never reverted, so passed is monotone: every clean verdict comes before every failing one, and the history never goes back to clean. The team wants to know which build introduced it. Given builds and passed, return the label of the earliest failing build. Return an empty string when every build in the history was clean, and an empty string for an empty history. The two lists are always the same length. Reproducing a verdict costs a full suite run, so the team wants a bisect that consults a handful of them rather than every one.
first_failing_build(builds: list[str], passed: list[bool]) → str[["nightly-101","nightly-102","nightly-103","nightly-104"],[true,true,false,false]]out"nightly-103"[["nightly-201","nightly-202"],[true,true]]out""[["nightly-301"],[false]]out"nightly-301"State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[["nightly-101","nightly-102","nightly-103","nightly-104"],[true,true,false,false]]"nightly-103"not run yetsample[["nightly-201","nightly-202"],[true,true]]""not run yetsample[["nightly-301"],[false]]"nightly-301"not run yetsample