First bad build

Question

Your nightly backtest passed on build 1 but fails on build n. Builds are cumulative: once a build is bad, every later build is also bad. You have a function is_bad(v) that runs the backtest against build v, but each call takes twenty minutes.

n = 10, builds:  G G G B B B B B B B
is_bad(4) -> True, is_bad(3) -> False
answer: 4

Find the first bad build using $O(\log n)$ calls to is_bad.

Accepted Answer

The array of answers looks like G G G B B B, monotone. Binary search on the predicate: maintain the invariant that everything before lo is good and everything from hi onwards is possibly-first-bad. If mid is bad, the first bad build is at mid or earlier (hi = mid); if mid is good, it is strictly later (lo = mid + 1). The loop ends when lo == hi, which is the answer. Tracing the example (n = 10, first bad is 4): mid = 5 bad so hi = 5; mid = 3 good so lo = 4; mid = 4 bad so hi = 4; loop exits with lo = hi = 4. Four calls instead of ten. O(\log n) calls, O(1) space. Two classic bugs to avoid: hi…

First bad build

Your answer

More Coding questions