First Bad Version
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Versions 1..n are good, then bad from some point on. With a function isBadVersion(v), find the first bad one using as few calls as possible.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1The answer is the boundary between good and bad. How many calls does a day-by-day scan need?
- Hint 2If the middle version is bad, is the first bad one at the middle or before?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The milk was fresh when you bought it on day 1 and is spoiled today, day 100. On which day did it first go bad? You do not smell it every day. Smell on day 50: still fresh? Then it went bad later. Spoiled? Then it went bad on day 50 or earlier. This is exactly how developers use git bisect to find the first broken commit.
- The obvious way
Call isBadVersion for 1, 2, 3, ...: O(n) calls.
- The key insight
The answers to "is it bad?" look like good, good, ..., bad, bad. Test the middle version: if it is bad the first bad one is the middle or earlier (keep the middle); if it is good the first bad one is later. Halve until one version remains.
- The algorithm
- Search range: version 1 to version n.
- Test the middle version.
- Bad? The first bad is the middle or earlier: range ends at the middle.
- Good? The first bad is later: range starts just after the middle. Stop when the range is one version.
Watch it run
Examplen = 5 versions, the first bad one is version 4
Test the middle, version 3: good. So the first bad is later; versions 1 to 3 are out.
range: versions 4 to 5
Where people slip
- Do not do high = middle - 1 on a bad version: the middle itself may be the answer.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def first_bad_version(n, is_bad_version):
low, high = 1, n
while low < high:
middle = (low + high) // 2
if is_bad_version(middle):
high = middle # the middle might be the first bad one
else:
low = middle + 1 # first bad is later
return lowNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.