First Bad Version

As I mentioned in my last post, over the past weekend my wife and I visited my younger son who lives in Madison, Wisconsin. At some point during a conversation personality types came up. We spent an hour or so on the subject. Towards the end my son’s wife mentioned an article on the subject she found by doing a web search. I asked her to send us the link. She did. I will read the article later today and will comment on my next post.

The technician that was going to fix the issue with our furnace showed up on time. I decided to watch him at work. He opened the furnace and cleared some dead wasps that had come in through the air intake tube. The furnace started to work. He spent some additional time cleaning contacts to increase the current flow.

It seems that our furnace is getting to the point that it will be needing a replacement soon. The technician gave us quotes for three different models. If the furnace continues to operate as intended we would be replacing it towards the end of Spring 2022.

Last night the furnace worked as expected. This morning I increased the temperature setting to the lower level. I li9ke to keep my office at 65F. The rest of the house is set to 68F during winter.

As I am typing this post the “Machine Learning for Algorithm Design” by Maria-Florina Balcan ACM webinar is starting. I will continue with this post as soon as I am done attending the 1-hour event.

OK, I am back. Would like to finish this post before lunch time.

Earlier today I selected the next problem in the series mentioned in the previous post which is LeetCode 278 First Bad Version. This problem is rated Easy.

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 returns whether version is bad. 
Implement a function to find the first bad version. 
You should minimize the number of calls to the API.

Constraints:

1 <= bad <= n <= 231 - 1

The idea is to locate the first bad version in a source code repository. We are given the total number of versions represented by the variable `n`. We need to determine which is the first bad version.

If interested in this problem, please visit the LeetCode website and read the current description of the problem.

Note that we will be making use of an API isBadVersion(version) which will return true or false indicating if the specified software version is bad or not. Personally I like the way this problem is defined. It makes it more interesting.

    public int firstBadVersion(int n) {
        
    }

We will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows computer. Because of this approach, we will have to develop a simple test scaffold which will collect the two input values, mimic the operation of the  isBadVersion API, pass the input argument to the function of interest and display the output. Note that the output should match the second input value which will be assigned to the `bad` variable. Of course, if you do not wish to develop the code on your computer, a better option is to use the on-line IDE provided by LeetCode. Note that the test scaffold is NOT PART OF THE SOLUTION!

The signature for the function of interest contains a single argument which holds the value of the total number of versions `n`. One of those versions is bad and the following ones will also be bad.

5
4
main <<< n: 5
main <<< bad: 4
<<< m: 3
<<< l: 4 r: 5
<<< m: 4
<<< l: 4 r: 3
main <<< output: 4


1
1
main <<< n: 1
main <<< bad: 1
<<< m: 1
<<< l: 1 r: 0
main <<< output: 1


11
3
main <<< n: 11
main <<< bad: 3
<<< m: 6
<<< l: 1 r: 5
<<< m: 3
<<< l: 1 r: 2
<<< m: 1
<<< l: 2 r: 2
<<< m: 2
<<< l: 3 r: 2
main <<< output: 3


17
15
main <<< n: 17
main <<< bad: 15
<<< m: 9
<<< l: 10 r: 17
<<< m: 13
<<< l: 14 r: 17
<<< m: 15
<<< l: 14 r: 14
<<< m: 14
<<< l: 15 r: 14
main <<< output: 15


17
16
main <<< n: 17
main <<< bad: 16
<<< m: 9
<<< l: 10 r: 17
<<< m: 13
<<< l: 14 r: 17
<<< m: 15
<<< l: 16 r: 17
<<< m: 16
<<< l: 16 r: 15
main <<< output: 16


17
17
main <<< n: 17
main <<< bad: 17
<<< m: 9
<<< l: 10 r: 17
<<< m: 13
<<< l: 14 r: 17
<<< m: 15
<<< l: 16 r: 17
<<< m: 16
<<< l: 17 r: 17
<<< m: 17
<<< l: 17 r: 16
main <<< output: 17

We are given two input values on separate lines. The first is `n` which holds the number of versions in the source code control system. The second value is the bad version which we need to find in the repository.

Our test scaffold seems to read both input lines, assign them to variables, and then display them to allow us to determine if all is well so far.

The messages that follow are used to help us to follow the binary search process. They are NOT PART OF THE SOLUTION.

Note that our test scaffold displays the version of the first bad code which should match the value of the `bad` variable. Let’s see how we could implement such a mechanism. Keep in mind that IT IS NOT PART OF THE SOLUTION.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read n ****
        int n = Integer.parseInt(br.readLine().trim());

        // **** read bad ****
        int bad = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();
        
        // ???? ?????
        System.out.println("main <<< n: " + n);
        System.out.println("main <<< bad: " + bad);

        // ???? set the bad version number ????
        vc = new VersionControl(bad);

        // **** call function of interest and display result ****
        System.out.println("main <<< output: " + firstBadVersion(n));
    }

Our test scaffold seems to match the description we came up with to explain what we should expect when processing a test case. Of course we need to pass the `bad` value to the class hosting the function we will use in the binary search to determine the location of the first bad code.

Note the call to instantiate a VersionControl class which IS NOT PART OF THE SOLUTION.

public class VersionControl {

    // **** ****
    public int bad;

    // **** ****
    public VersionControl() {}

    // **** ****
    public VersionControl(int bad) {
        this.bad = bad;
    }

    // **** API of interest ****
    public boolean isBadVersion(int n) {
        return n >= this.bad ? true : false;
    }

}

This is our implementation of the VersionControl class. We need to pass the `bad` variable to the constructor so it can be used by the isBadVersion function to determine if a previous version of the code is bad or not.

    // **** auxiliary function ****
    static VersionControl vc = null;        

We will declare this global object `vc` so we can use it in our function of interest which will be implementing a binary search. Once again, the vc object is just an artifact that is NOT PART OF THE SOLUTION.

    /**
     * Implement a function to find the first bad version. 
     * You should minimize the number of calls to the API.
     * 
     * 22 / 22 test cases passed.
     * Status: Accepted
     * Runtime: 12 ms
     * Memory Usage: 36.1 MB
     * 
     * Execution: O(n log(n)) - Space: O(1)
     */
    static public int firstBadVersion(int n) {
        
        // // **** sanity check(s) ****
        // if (n <= 1)
        //     return 1;
        // else if (vc.isBadVersion(1))
        //     return 1;

        // **** initialization ****
        int l = 1;
        int r = n;

        // **** look for the first bad version ****
        while (l <= r) {

            // **** compute mid ****
            int m = l + (r - l) / 2;

            // ???? ????
            System.out.println("<<< m: " + m);

            // **** check if bad version found ****
            // if (!vc.isBadVersion(m - 1) && vc.isBadVersion(m)) return m;

            // **** determine which way to go ****
            if (vc.isBadVersion(m))
                r = m - 1;          // go left
            else 
                l = m + 1;          // go right

            // ???? ????
            System.out.println("<<< l: " + l + " r: " + r);
        }

        // **** first bad version ****
        return l;
    }

Finally this is the implementation of the function of interest. Note that I started with a basic implementation of the binary search algorithm, and modified it in order to get a faster implementation that addresses the requirements of the problem at hand.

We start by performing some sanity checks. That part has been commented out at this time.

We need to initialize the `l` for left and the `r` for right variables which will be used to manage the range of values we are searching while the algorithm executes.

We then enter a loop.

In the loop we start by computing the middle point in the current range.

We could determine if this is the value we are searching for; but I decided to comment out the statement.

We then need to determine if we use the left or the right range.

When the condition on the while loop becomes false, we have the value of the first bad version of the code.

As you can see, I wrote an initial standard binary search algorithm and then made some changes to see if it would improve on the execution time.

As you can see in the comments section of the function of interest, the execution is O(n log(n)) and the space is O(1).

One more thing, if you wish to test this code on-line, make sure you remove the `vc.` from it.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John