Skip to main content

17. First Bad Version

easyAsked at Square

Find the first firmware release that broke POS terminal compatibility — Square ships hundreds of hardware versions and uses binary search to pinpoint the exact SDK version that introduced a payment-flow regression without re-running every build.

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

Problem

You are a product manager and currently have n versions [1, 2, ..., n]. An API isBadVersion(version) returns whether a given version is bad. You want to find the first bad version. Minimize the number of calls to the API.

Constraints

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

Examples

Example 1

Input
n = 5, bad = 4
Output
4

Explanation: isBadVersion(3) = false, isBadVersion(4) = true, isBadVersion(5) = true. First bad version is 4.

Example 2

Input
n = 1, bad = 1
Output
1

Approaches

1. Linear scan

Call isBadVersion from 1 upward until it returns true. Works but O(n) API calls — disqualifying at Square 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

Converge lo/hi on the first bad version. Key: use lo + Math.floor((hi - lo) / 2) to avoid integer overflow at 2^31 - 1 range.

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:

Square-specific tips

Square specifically checks the overflow guard: mid = lo + (hi - lo) / 2 vs mid = (lo + hi) / 2. With n up to 2^31 - 1, the naive formula overflows a 32-bit integer. Calling that out before writing code signals that you think about production constraints, not just correctness.

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 Square interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →