Facebook Interview Question Senior Software Development Engineers
Country: India
1. "why are you checking the first element before the binary search?" -
Only for acceleration this case: bug has been present since the beginning.
2. "what case this condition will be true? (e == s )" -
When array has only one element.
The idea here is correct, but your implementation leaves out a few details.
Note that there are three comparisions against revs[mid], when there only needs to be one.
The correct implementation for the binaryFindBugs method is as follows:
public static int binaryFindBugs(int[] revisions, int start, int end) {
if (start == end || start - end == 1) return revisions[start];
int mid = (start + end) / 2;
if (isBug(revisions[mid]) {
// Note that we check [start, mid - 1] because we've already checked revisions[mid] and we're moving left (decreasing).
return binaryFindBugs(revisions, start, mid - 1);
} else {
// Note that we check [mid + 1, end] because we've already checked revisions[mid] and we're moving right (increasing).
return binaryFindBugs(revisions, mid + 1, end);
}
}
How would binary search be faster than linear search? It is not like if we find that if middle version of the range didn't introduce bug we can eliminate upper half or lower half. We will have to do linear search from bottom or top of the range.
Actually it's possible to do modified binary search such that we always end up at the last occurrence. This can be done by going to the interval containing the current index and upper half of the array every time the current number is <= to the version number with the bug, which avoids linear search.
public class Branch{
public int findBug(int[] branch){
if(branch == null || branch.length == 0){ //if branch is null or empty, no bugs
return -1
} else if(isBug(branch[0])){ //checks if the bug is the only element in array, or first element of array
return branch[0];
} else { //runs if branch is length > 1, linear search. Can't do binary because there is no comparison to eliminate left/right half
int bugVersion;
for(int i = 0; i < branch.length; i++){
if(isBug(branch[i]))
bugVersion = branch[i];
}
if(bugVersion)
return bugVersion;
else
return -1;
}
}
}
This is a good start, but there's some work to be done here. First, in terms of your class design, things are a bit funky. The classname is Branch, which provides the assumption that it represents a branch. In that case, I would give Branch the method Branch.isBuggy() -> boolean, and create another class, BranchSet (or RevisionSet) which essentially wraps a Set<Branch>. In that class, I would define the method BranchSet.findBug() -> Branch.
In the second half of the code, you note that we can't preform binary search because there is no comparison to eliminate the left/right half, but there are assumptions that are safe to make that DO allow us to eliminate halves of the search. Let's assume that bugs are introduced linearly, such that if we introduce a bug in rev x, it will be contained in all revisions following x. This assumption is safe to make because we are primarily concerned with our implementation of binary search.
As such, if a bug is not found in the middle, we can eliminate the revisions [start, middle], and assume that the buggy revision lies between (middle, end], making binary search a prime choice to solve this problem.
The same approach with corrections, need to return v[start] as its lowest version where bug could have been introduced.
Also in the else, we can start from mid+1
static int findbugIntroduced(int[] v,int start, int end)
{
if(start == end || end-start == 1) return v[start];//return the lowest, where the bug is introduced
int mid = (start+end)/2;
if(isBug(v[mid]))//then introduced in lower version or mid
{
return findbugIntroduced(v,start,mid);
}else
{
return findbugIntroduced(v,mid+1,end);//can do mid+1 as mid doesnt have bug
}
}
- Ann January 24, 2015int findBugs(int[] versions) { if (versions == null || !isBug(versions[versions.length - 1])) return -1; // no bugs if (isBug(versions[0])) return versions[0];// versions[0]; return binaryFindBug(versions, 0, versions.length - 1); } static int binaryFindBug(int[] v, int s, int e) { if (e == s || e-s == 1) return v[e]; int mid = (s+e)/2; if (isBub(v[mid])) { return binaryFindBug(v, s, mid); } else { return binaryFindBug(v, mid, e); } }