Home » Interview coding problems/challenges

Finding First Bad Version

In this article, we are going to see how to solve the following searching problem in minimum time complexity? This problem can be featured in any interviews. Submitted by Radib Kar, on January 18, 2019

Problem statement

Suppose that IncludeHelp turns to be a product company & we have a product manager leading a team to develop a new product. Unfortunately, the latest version of our 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 we have n versions [1, 2, ..., n] and we want to find out the first bad one, which causes all the following ones to be bad.

Our product manager is given an API bool isBadVersion(version) which will return whether version is bad or not. He now wants to hire a programmer to implement a function to find the first bad version. There should be minimum number of calls to the API. Can you help him out?

Solution Approach

Of course this is a searching problem & for optimization we can do a binary search here. But now the question is, is there any other optimum searching method for search problem? The answer is yes.

It is binary search but the narrow down constant, K is not typically (low + high)/2 as in case of general binary search.

In this case the narrow down constant, K= low+(high-low)/2 resulting in much more optimized result.

Algorithm

We have already the API function bool isBadVersion(version)

Now to find the first bad version we generate another function:

low=lower bound variable
high=upper bound variable

FUNCTION findFirstBad( int low, int high)
    While(low<=high){
        1.  Set mid to the narrow down constant K, low+(high-low)/2;
        2.  IF (isBadVersion(mid))  //if it is bad
            //there can be two case
            //1.    This is no 1, so thdere is no other version previously 
            //      thus these must be the first one
            //2.    The immediate previous one is not bad, thus this is 
            //      the first bad one
            IF (mid==1 || !isBadVersion(mid-1))
                Return mid;
            ELSE
                //narrow down high as first bad one must be before this one
                high=mid-1;
            End IF-ELSE
        ELSE
            //since this is not bad, the lower bound must be > this version
            low=mid+1;
        END IF-ELSE
        3.  If not returned from while loop, no bad version exists at all
        Return -1;
    END WHILE
END FUNCTION

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

#define n 10

int A[n]= { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};

// declaration of isBadVersion API.
bool isBadVersion(int version){
	return A[version];
}

int findFirstBad(int low,int high){
	while(low<=high){
		//narrow down factor
		int mid=low+(high-low)/2;
		if(isBadVersion(mid)) {
			if(mid==0 || !isBadVersion(mid-1))
				return mid+1;
			else
				high=mid-1;
		}
		else
			low=mid+1;
	}
	return -1;	
}

int firstBadVersion(int i) {
	if(i==1){
		if(isBadVersion(i))
			return i+1;
		else
			return -1;
	}
	return findFirstBad(0,i);
}

int main(){
	cout<<"this is a functional problem,so main functiom hardcoded\n";
	//product versions
	//A[n]= { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
	//0=good product, 1=bad product
	cout<<"product versions are:\n";
	for(int i=0;i<n;i++){
		cout<<i+1<<"\t";
		if(A[i])
			cout<<"bad"<<endl;
		else
			cout<<"good"<<endl;
	}
	
	cout<<"First Bad version is:\n";
	cout<<firstBadVersion(n-1);
	
	return 0;
}

Output

this is a functional problem,so main functiom hardcoded
product versions are:
1       good
2       good
3       good
4       good
5       good
6       good
7       bad
8       bad
9       bad
10      bad
First Bad version is:
7