Facebook

  www.facebook.com
  www.facebook.com

Interview Question

Software Engineer Interview

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
Answer

Interview Answer

6 Answers

2

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
0

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
0

Yes, thanks for the correction

Anonymous on May 2, 2012
1

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
0

http://manpages.ubuntu.com/manpages/lucid/man1/svn-bisect.1.html

Anonymous on May 7, 2012
0

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.