Skip to main content

17. First Bad Version

easyAsked at Databricks

Find the first broken build in a sequence — a canonical binary-search probe that mirrors how Databricks bisects failing notebook versions or regressed MLflow runs in a CI pipeline.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You have n versions labeled 1 through n. A provided API isBadVersion(version) returns true if the version is bad. All versions after the first bad one are also bad. Find the first bad version while minimizing API calls.

Constraints

  • 1 <= bad <= n <= 2^31 - 1

Examples

Example 1

Input
n = 5, bad = 4
Output
4

Explanation: isBadVersion(3) returns false, isBadVersion(4) returns true, so 4 is the first bad version.

Example 2

Input
n = 1, bad = 1
Output
1

Approaches

1. Linear scan

Call isBadVersion for each version from 1 to n and return the first true. O(n) API calls — unacceptable at scale.

Time
O(n)
Space
O(1)
function solution(isBadVersion) {
  return function(n) {
    for (let i = 1; i <= n; i++) {
      if (isBadVersion(i)) return i;
    }
  };
}

Tradeoff:

2. Binary search

Maintain lo and hi. When mid is bad, the answer may be mid or earlier; when good, the answer is strictly after mid. Use integer midpoint to avoid overflow.

Time
O(log n)
Space
O(1)
function solution(isBadVersion) {
  return function(n) {
    let lo = 1, hi = n;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (isBadVersion(mid)) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    return lo;
  };
}

Tradeoff:

Databricks-specific tips

Databricks evaluates this as a proxy for distributed-system reasoning: can you minimize expensive remote calls (isBadVersion ~ a network round-trip to a coordinator)? Explicitly narrate the overflow-safe midpoint formula — they catch candidates who write (lo + hi) / 2 and ask what happens at 2^31.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill First Bad Version and other Databricks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →