2
\$\begingroup\$

This is new code based on some new ideas to reduce calls to is_bad_version. Refer to the previous version of the code discussion from here.

Any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated. My major idea is divide and conquer like a binary search/quick select.

Problem:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Source code:

def is_bad_version(number):
    if number == 0:
        return False
    else:
        return True


def find_first_bad_index(numbers):
    start = 0
    end = len(numbers) - 1
    if start == end:
        if is_bad_version(numbers[start]):
            return start
        else:
            raise Exception('all good!')
    while start < end:
        mid = start + (end - start) / 2
        if is_bad_version(numbers[mid]):
            end = mid
        else:
            start = mid + 1
    if start == end:
        if is_bad_version(numbers[start]):
            return start
        else:
            raise Exception('all good!')

if __name__ == "__main__":
    print find_first_bad_index([0,0,0,1,1,1,1,1])
    print find_first_bad_index([0,0,0,0,0,0,0,1])
\$\endgroup\$
7
  • 1
    \$\begingroup\$ raise Exception('all good!'), what an interesting exception. lol. \$\endgroup\$ – Dair Dec 18 '16 at 3:41
  • 2
    \$\begingroup\$ Are you aware of bisect? Also is_bad_version could just return number, as 0 is false-y and 1 is truth-y. \$\endgroup\$ – jonrsharpe Dec 18 '16 at 8:35
  • 1
    \$\begingroup\$ @jonrsharpe: Did you ever wish bisect(sequence, x, lo=0, hi=len(a)) had a key like sorted(iterable[, key][, reverse])? \$\endgroup\$ – greybeard Dec 18 '16 at 9:11
  • 1
    \$\begingroup\$ @greybeard "...it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups)." \$\endgroup\$ – jonrsharpe Dec 18 '16 at 9:19
  • 1
    \$\begingroup\$ @jonrsharpe: (Qoute from in Other Examples of bisect use Claiming something not to make sense just because one hasn't found an inefficient design is a strong statement. (Think of python supporting memoisation per decorator.) \$\endgroup\$ – greybeard Dec 18 '16 at 9:28
5
\$\begingroup\$

Document your code in the code. If trying to stick to all pertaining PEPs gets too much, have a look at Code Documentation Advice.

If you don't want to go with bisect
(noteworthy simplifications/improvements (esp. over/of VersionWrap), anyone? Please edit.)

from bisect import bisect
from functools import total_ordering


class NoBadVersion(Exception):
    """Home brewed exception to diferentiate from other
    kind of exceptions and avoid too generic except clauses.
    """


@total_ordering
class VersionWrap:
    """Support version designator comparison"""
    __slots__ = 'version', 'bad'
    def __init__(self, v, b = None):
        self.version = v
        self.bad = b
    def is_bad(self):
        if self.bad is None:
            self.bad = is_bad_version(self.version)
        return self.bad
    def __eq__(self, other):
        return other.is_bad() == self.is_bad()
    def __lt__(self, other):
        return not self.is_bad() and other.is_bad()


def find_first_bad_index(numbers):
    """Find the first bad version

    Assumes is_bad_version(numbers[i]) implies
     is_bad_version(numbers[i+n]) for every natural number n.
    numbers is a sequence of version designators,
    suitable as parameters to is_bad_version().

    Returns the lowest b such that is_bad_version(numbers[b])
    """
    firstNonGood = bisect([VersionWrap(vd) for vd in numbers],
                          VersionWrap(None, False))
    if firstNonGood == len(numbers):
        raise NoBadVersion('none bad!')

    return firstNonGood

, stay with

"""Find the first bad version

Keep number of calls to is_bad_version() at minimum.
"""


class NoBadVersion(Exception):
    """Home brewed exception to diferentiate from other
    kind of exceptions and avoid too generic except clauses.
    """


def is_bad_version(number):
    """dummy for an external predicate costly to evaluate"""
    return number


def find_first_bad_index(numbers):
    """Find the index of the first bad version

    Assumes is_bad_version(numbers[i]) implies
    is_bad_version(numbers[i+n]) for every natural number n.
    numbers is a sequence of version designators,
    suitable as parameters to is_bad_version().

    Returns the lowest b such that is_bad_version(numbers[b])
    """
    start = 0
    end = len(numbers)

    while start < end:
        mid = start + (end - start) // 2
        if is_bad_version(numbers[mid]):
            end = mid
        else:
            start = mid + 1

    if start == len(numbers):
        raise NoBadVersion('none bad!')
    return start


if __name__ == "__main__":
    numbers = [1] * 7
    for good in range(len(numbers)+1):
        print(find_first_bad_index(numbers))
        numbers[good] = 0
\$\endgroup\$
4
  • \$\begingroup\$ Hi greybeard, love your code of the raw implementation of find_first_bad_index, vote up! But I am confused about the version using bisect, bisect is using binary search method to divide/conquer to search some values, correct? How it related to find first index? (I understand you can use bisect to find 0 or 1, but how do you control to find the first 1 -- if we think 1 is bad?) \$\endgroup\$ – Lin Ma Dec 20 '16 at 7:03
  • 1
    \$\begingroup\$ bisect [implements] binary search: divide&conquer to s̶e̶a̶r̶c̶h̶ ̶s̶o̶m̶e̶ ̶v̶a̶l̶u̶e̶s̶>return i bisecting the sequence s such that all(val <= x for val in s[lo:i]) and all(val > x for val in a[i:hi]) how do you control to find the first: see the differences between bisect_left() and bisect_right(). \$\endgroup\$ – greybeard Dec 20 '16 at 10:08
  • \$\begingroup\$ Thanks, but I do not see you call bisect_left and bisect_right? \$\endgroup\$ – Lin Ma Dec 22 '16 at 6:49
  • \$\begingroup\$ I can choose between bisect_left(), bisect_right() and its alias bisect(). I chose bisect() to credit [jonrsharpe's suggestion ](codereview.stackexchange.com/questions/150173/…) and built the key accordingly - with bisect_left(), it would have been VersionWrap(None, True) (find the index where an inserted item would be immediately to the left of all bad versions). \$\endgroup\$ – greybeard Dec 22 '16 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.