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

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL