Home » Technical Interview Questions » Array Interview Questions » First Bad Version

First Bad Version


Reading Time - 2 mins

We all have heard the saying “Bad Apple Ruins The Bunch”.First Bad Version is a problem that beautifully illustrates the same. Today we have a problem which is First Bad Version. One of the interns has made an nth bad commit due to which commits from n+1 have all been facing merge conflicts. The task in hand is pretty simple. All we have to do is “search” for the first bad commit that leads to the downfall of our software. However, we can only check if ith commits isBadVersion() and we have very limited calls.

Taking it from the top. Let us look at a test case

Input

n=6 and version=3 is the faulty commit

isBadVersion(1)=false

isBadVersion(2)=false

isBadVersion(3)=true

Helping us detect the first bad version

Output

3

Approach-1

Linear Search

The first and easy approach that might come to our mind would be using a linear search.

We look through each of the elements starting from 0 one by one

Showing First Bad Version with calls for a sample array
Showing First Bad Version with calls for a sample array

Let us look at that by the code.

Implementation

Java Code For First Bad Version

public class Solution extends VersionControl
{
    public int firstBadVersion(int n) 
    {
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(isBadVersion(i))
        {ans=i;break;}
    }
    return ans;    
    }
}

C++ Code For First Bad Version

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution 
{
public:
    int firstBadVersion(int n) 
    {
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(isBadVersion(i))
        {ans=i;break;}
    }
    return ans;
    }
};

Complexity Analysis

The time complexity of the above approach=O(n)

READ  Guess The Word

Why?

  • Example-We had 5 versions
  • We go through each and every version until we encounter the third version and term it as bad
  • In the worst case, we end up going to the last element in the search of the bad one
  • Thus, leading the time complexity to O(n) i.e linear

This, however, leads to a timeout.

Approach-2

Binary Search

The linear search may give off a timeout for a few of the test cases which can efficiently be countered with the help of a binary search.

We look out for the mid element each time cutting the time involved considerably. Assuming we have 256 versions and 255th is the bad one.

The first mid=(0+256)/2=128. We check the 128th version.

  • If it is bad then we go and check the previous half.
    • We calculate 0+(128-0)/2=64 and repeat the process
  • The version if is good we check the later half.
    • We calculate 128+(256-128)/2=192 and repeat the process

We calculate the mid and check if the version is good or bad.

Let us look into the code.

Implementation

Java Code

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl 
{
    public int firstBadVersion(int n) 
    {
      int st=1;
      int en=n;
      int ans=n;
      while(st<=en)
      {
      int mid=st+(en-st)/2;
      if(isBadVersion(mid))
      {ans=mid;en=mid-1;}
      else
      st=mid+1;
      }
      return ans;
    }
}

C++ Code

class Solution 
{
public:
    int firstBadVersion(int n) 
    {
    int st=1;
      int en=n;
      int ans=n;
      while(st<=en)
      {
      int mid=st+(en-st)/2;
      if(isBadVersion(mid))
      {ans=mid;en=mid-1;}
      else
      st=mid+1;
      }
      return ans;    
    }
};
n=5

First Bad Version at  n=3
3

Complexity Analysis

Time complexity=O(log n)

  • In each search depending on the search, we search in the respective half
    • We are halving our search space each and every time we proceed on to the next search
    • Let us assume we make k calls
      • Till when do we make these calls?
      • Till we have only one search element we are looking at
      • Thus, 2^k=n
    • Taking log both sides k=log(n)
  • Thus, making the time complexity log(n)
READ  Maximum Product Subarray

We might consider a ternary search as well.

But in many cases, it has been proven that binary search works better than the ternary search. Thus, we should consider the above-suggested search mechanism.

References

Now that we have gone through the problem. Wanna check it out for more complex data structures?

Check the link below-

Searching a node in a Binary Search Tree

 

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions