Jobs

Interviews

Discussions

First Bad Version

Easy

Asked by:

More companies

12 views

Topics:

Binary Search

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 1:

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.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

1 <= bad <= n <= 2³¹ - 1

Try coding it in LeetCode

First Bad Version

Easy

Asked by:

12 views

Topics:

Binary Search

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 1:

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.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

1 <= bad <= n <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for 'n', the number of versions?
Is `isBadVersion(version)` guaranteed to be defined for all versions between 1 and n (inclusive)?
If no version is bad, what value should I return?
Is 'n' always a positive integer?
Could you provide some example inputs and expected outputs to illustrate edge cases?

Brute Force Solution

Approach

Imagine we need to find the first broken toy in a row of toys. The brute force approach involves checking each toy one by one, starting from the beginning, until we find the first broken one.

Here's how the algorithm would work step-by-step:

Start with the very first toy.
Check if that toy is broken.
If it is broken, we've found the first broken toy, so we're done.
If the first toy is not broken, move on to the next toy in the row.
Check if this second toy is broken.
Continue checking each toy, one after another, until you find the first broken one.

Code Implementation

def first_bad_version_brute_force(number_of_versions, is_bad_version):
    for current_version in range(1, number_of_versions + 1):
        # Iterate through each version to find the first bad one
        if is_bad_version(current_version):

            # If the current version is bad, it's the first bad version
            return current_version

    # All versions are good.  This should not happen based on the problem constraints
    return number_of_versions + 1

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through each toy, one by one, from the first toy until a broken toy is found. In the worst-case scenario, all toys before the first broken toy are not broken, meaning we might have to check almost all 'n' toys. Therefore, the time complexity is directly proportional to the number of toys 'n', resulting in O(n).

Space Complexity

O(1) – The plain English explanation describes iterating through toys one by one without storing them or intermediate results in any data structure. Only a single variable implicitly serves as a current toy index. Therefore, the space used remains constant, irrespective of the number of toys (N).

Optimal Solution

Approach

The key idea is to use a process of elimination to quickly find the first bad version. We repeatedly cut the search area in half based on whether the middle version is good or bad, similar to searching for a word in a dictionary.

Here's how the algorithm would work step-by-step:

Start by considering all versions from the very first to the very last.
Check the version in the middle of the current range.
If the middle version is bad, we know that the first bad version must be somewhere before or at the middle. Discard the second half.
If the middle version is good, we know that the first bad version must be somewhere after the middle. Discard the first half.
Repeat steps 2-4, each time focusing on a smaller and smaller range of versions.
Eventually, you will be left with only one version. This is the first bad version.

Code Implementation

def first_bad_version(number_of_versions):
    left_version = 1
    right_version = number_of_versions

    while left_version < right_version:
        middle_version = left_version + (right_version - left_version) // 2

        # If mid is bad, the first bad version
        # must be in the left half, including mid.
        if isBadVersion(middle_version):

            right_version = middle_version

        # If mid is good, the first bad version
        # must be in the right half, excluding mid.
        else:

            left_version = middle_version + 1

    # left_version and right_version converge to the first bad version
    return left_version

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses binary search to find the first bad version. In each step, it halves the search space by comparing the middle version to determine whether the first bad version lies in the left or right half. This halving process continues until the search space is reduced to a single element, which is the first bad version. Therefore, the number of operations is proportional to the number of times n can be divided by 2 until it reaches 1, which is log base 2 of n. Hence the time complexity is O(log n).

Space Complexity

O(1) – The algorithm employs a binary search approach, repeatedly halving the search range without allocating significant extra memory. It primarily uses a few variables to track the start and end points of the search interval. The space required for these variables remains constant irrespective of the number of versions, N. Thus, the auxiliary space complexity is O(1) because only a fixed amount of extra space is used.

Edge Cases

Case	How to Handle
n = 1 and the first version is bad	The binary search should converge to 1 and return 1.
n = 1 and the first version is good	The algorithm should handle this gracefully, potentially returning n+1 or throwing an exception if the problem guarantees a bad version exists.
All versions are bad	The binary search should converge to 1 as the first bad version.
All versions are good	The algorithm should handle this gracefully, potentially returning n+1 or throwing an exception if the problem guarantees a bad version exists.
n is a very large number leading to potential integer overflow in (low + high) / 2	Use (low + (high - low) / 2) or (low/2 + high/2) to calculate the middle point to avoid overflow.
The first bad version is the last version (n)	The binary search should converge to n and return n.
isBadVersion() always throws an exception	The calling function should include error handling around the isBadVersion() function call.
n is zero or negative	Return an appropriate error code or throw an exception as n cannot be zero or negative for the versioning context.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for 'n', the number of versions?
Is `isBadVersion(version)` guaranteed to be defined for all versions between 1 and n (inclusive)?
If no version is bad, what value should I return?
Is 'n' always a positive integer?
Could you provide some example inputs and expected outputs to illustrate edge cases?

Brute Force Solution

Approach

Imagine we need to find the first broken toy in a row of toys. The brute force approach involves checking each toy one by one, starting from the beginning, until we find the first broken one.

Here's how the algorithm would work step-by-step:

Start with the very first toy.
Check if that toy is broken.
If it is broken, we've found the first broken toy, so we're done.
If the first toy is not broken, move on to the next toy in the row.
Check if this second toy is broken.
Continue checking each toy, one after another, until you find the first broken one.

Code Implementation

def first_bad_version_brute_force(number_of_versions, is_bad_version):
    for current_version in range(1, number_of_versions + 1):
        # Iterate through each version to find the first bad one
        if is_bad_version(current_version):

            # If the current version is bad, it's the first bad version
            return current_version

    # All versions are good.  This should not happen based on the problem constraints
    return number_of_versions + 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering all versions from the very first to the very last.
Check the version in the middle of the current range.
If the middle version is bad, we know that the first bad version must be somewhere before or at the middle. Discard the second half.
If the middle version is good, we know that the first bad version must be somewhere after the middle. Discard the first half.
Repeat steps 2-4, each time focusing on a smaller and smaller range of versions.
Eventually, you will be left with only one version. This is the first bad version.

Code Implementation

def first_bad_version(number_of_versions):
    left_version = 1
    right_version = number_of_versions

    while left_version < right_version:
        middle_version = left_version + (right_version - left_version) // 2

        # If mid is bad, the first bad version
        # must be in the left half, including mid.
        if isBadVersion(middle_version):

            right_version = middle_version

        # If mid is good, the first bad version
        # must be in the right half, excluding mid.
        else:

            left_version = middle_version + 1

    # left_version and right_version converge to the first bad version
    return left_version

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 1 and the first version is bad	The binary search should converge to 1 and return 1.
n = 1 and the first version is good	The algorithm should handle this gracefully, potentially returning n+1 or throwing an exception if the problem guarantees a bad version exists.
All versions are bad	The binary search should converge to 1 as the first bad version.
All versions are good	The algorithm should handle this gracefully, potentially returning n+1 or throwing an exception if the problem guarantees a bad version exists.
n is a very large number leading to potential integer overflow in (low + high) / 2	Use (low + (high - low) / 2) or (low/2 + high/2) to calculate the middle point to avoid overflow.
The first bad version is the last version (n)	The binary search should converge to n and return n.
isBadVersion() always throws an exception	The calling function should include error handling around the isBadVersion() function call.
n is zero or negative	Return an appropriate error code or throw an exception as n cannot be zero or negative for the versioning context.