algoadvance

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n], and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Clarifying Questions

1. What is the range of n?
   • Typically, n can be quite large, say up to (2^{31} - 1).
2. Are the versions numbered sequentially starting from 1 up to n?
   • Yes, versions are sequentially numbered from 1 to n.
3. Can the isBadVersion API call be costly?
   • Yes, the main goal is to minimize the number of API calls, suggesting isBadVersion might be costly.

Strategy

To find the first bad version efficiently, we can use a Binary Search algorithm. This approach helps in reducing the number of isBadVersion API calls by dividing the search space in half each time.

Binary Search Approach

1. Initialization:
   • Use two pointers, left starting at 1 and right starting at n.
2. Binary Search:
   • Calculate the middle point mid.
   • If isBadVersion(mid) is true, then the first bad version must be mid or to the left of mid, so we move the right pointer to mid.
   • If isBadVersion(mid) is false, then we move the left pointer to mid + 1 to search the right half.
3. Termination:
   • The loop repeats until left meets right, at which point left will be at the position of the first bad version.

Time Complexity

• The time complexity of the binary search approach is (O(\log n)), which is very efficient compared to a linear scan (O(n)).

Code Implementation

Here is the implementation in Python:

def firstBadVersion(n):
    left, right = 1, n
    
    while left < right:
        mid = left + (right - left) // 2
        
        if isBadVersion(mid):
            right = mid  # mid might be the first bad version
        else:
            left = mid + 1  # mid is definitely not the first bad version
    
    return left  # or right, since left == right

Final Notes

• The implementation assumes that isBadVersion is already defined or provided in the environment.
• The binary search ensures that we zero in on the first bad version efficiently, minimizing the number of calls to isBadVersion.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?