Facebook
4.5 of 5 676 reviews
www.facebook.com Menlo Park, CA 5000+ Employees

Facebook Software Engineer Interview Question

"Say you use SVN for source control..you have several revisions of a file...R1, r2, r3..etc..Someone checked in a bug and the revision became bad..need t find the first bad revision..gave a function findBadRevision(int goodRevision, int badRevision) so for e.g the revisions were GGBB and function passes in 0,4 so the first bad revision is 2. There exists a function boolean hasBug(int revision) which will tell us if a certain revision has a bug. can assume good revision < bad revision"
Tags: algorithm
Add Tags [?]
Answer Flag Question

Part of a Software Engineer Interview Review - one of 1,062 Facebook Interview Reviews

Answers & Comments

2
of 2
votes
start with binary search approach and take the mid as

boolean foundBad = false;
while(!foundBad)
{
       int revision = (goodrevision+badrevision)/2;
       foundBad = hasBug(revision);
       goodrevision = revision;
}
return revision;
- Interview Candidate on Apr 28, 2012 Flag Response
0
of 0
votes
Sorry but the solution is wrong
If the first bad revision is earlier than the mid your code will return the mid.
Example: GGBBBBB - If we'll start indexing from 1 and the function will be called with goodrevision=1 and badrevision=7 your code will return (7+1)/2 = 4. (Right answer is 3...).
Binary search is the right approach and an iterative impl' can be:

       public static int findBadRevision(int goodRevision, int badRevision) {
        while (true) {
            int mid = (goodRevision + badRevision) / 2;
            if (hasBug(mid)) {
                if (mid == 0 || !hasBug(mid-1)) {
                    return mid;
                }
                badRevision = mid;
            } else {
                goodRevision = mid;
            }
        }
    }
- ??? on May 2, 2012 Flag Response
0
of 0
votes
Yes, thanks for the correction
- Anonymous on May 2, 2012 Flag Response
1
of 1
vote
The above code also has a flaw.

Trying GGGGB will go into infinite loop. Using standard binary search we use

badRevision = mid -1;

and goodRevision = mid + 1;
- Fayyaz on May 5, 2012 Flag Response
0
of 0
votes
http://manpages.ubuntu.com/manpages/lucid/man1/svn-bisect.1.html
- Anonymous on May 7, 2012 Flag Response
0
of 0
votes
public int findBadRevision(int goodRevision, int badRevision) {
        int lastBadRev = -1;
        while(goodRevision <= badRevision) {
            int mid = (goodRevision + badRevision) / 2;
            if (hasBug(mid)) {
                lastBadRev = mid;
                badRevision = mid-1;
            }
            else {
                goodRevision = mid+1;
            }
        }
        return lastBadRev;
    }

Will return -1 if all GGGGG and 2 if BBBBBBB with (2,5) for example. For normal cases, will return index of first bad revision.
- hm on Jan 20, 2013 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Facebook interview questions and advice. All interview reviews posted anonymously by Facebook employees and interview candidates.