Interview Question

Front End Engineer Interview

-Folsom, CA

Facebook

If you have 500 revisions of a program, write a program that will find and return the FIRST bad revision given a isBad(revision i) function.

Answer

Interview Answers

7 Answers

1

function findBadVersion(n) { let min = 0,max = n, mid; while(min < max){ mid = min + Math.floor((max-min)/2); if(isBadVersion(mid)){ max = mid; }else{ min = mid+1; } } return min; };

Anonymous on

0

I don't understand how a Binary Search would work in this case; given just an array of revisions, and a pure function that simply takes one revision, and returns true or false. Based on the Binary Search being akin to `git bisect`, the docs state, "You use it by first telling it a "bad" commit that is known to contain the bug, and a "good" commit that is known to be before the bug was introduced." - https://git-scm.com/docs/git-bisect I don't see that we already know which revision is bad (or one that is good), as that is what is being asked of us to find. It would seem to me a breakable loop would solve this. ``` console.clear(); const testFind = false, // [true|false] For testing purposes only. isBad = rev => testFind, // Stub for given requirement (would otherwise import). findBadFirst = (revisions) => { // Using () for clarity and consistency. const revFound = { 'found': false }; // Using object to avoid a Type conflict. for (let r = 0; r < revisions.length; r++) { // Using `for` so we can break. if (isBad(revisions[r])) { revFound.found = true; revFound['revision'] = revisions[r]; break; } } return revFound; }; // Testing... const store = { 'revisions': [ { 'item': 1 } ] }, foundOut = findBadFirst(store.revisions); console.log('Found: ', foundOut.found); console.log('Rev: ', foundOut.revision ? foundOut.revision : 'None (all good!)'); ```

Keith D Commiskey on

0

```` const findBadRevision = (start, end)=>{ if(start>end) return -1; let mid = parseInt((start+end)/2); if(isBad(mid)){ if(mid==0 || (!isBad(mid-1))) return mid; return findBadRevision(start, mid); } return findBadRevision(mid+1, end); } ````

Kal on

0

Vanilla binary search like some. folks have posted is wrong. It doesnt. return the min version when a bad commit occurred. If b==bad, g==good take this sequence [gbbb]. midpoint=2. Any nswer which checks isBad(mid) && !isBad(mid-1) before returning mid will work

smk on

1

Yeah, binary search. very similar to what git bisect does.

Anonymous on

0

Hashmap? Since we are already provided with a key, it takes constant time to lookup using the key.

Gantavya on

4

Binary Search algorithm.

Anonymous on

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.