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.
You are given two strings ‘Version1’ and ‘Version2’ representing the version numbers. Your task is to compare them and find out which one of them is the latest version.

Note:

The input strings consist of digits and dots only and both the strings are started and terminated by a digit. There are no leading zeros and no zeros following a dot in both the strings except in the case of zero itself.

For Example:

Version1 = “1.23.45”, Version2 = “1.23.456” The first two parts of both the strings are the same. The third part of Version2 is greater than the third part of Version1, thus string Version2 is of the latest version.

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow. The first line of each test case contains the string ‘Version1’. The second line of each test case contains the string ‘Version2’.

Output format:

For each test case, print 1 if version 1 is latest, -1 if version 2 is latest and 0 if both versions are the same. Print output of each test case in separate lines.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

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.

You are given two strings ‘Version1’ and ‘Version2’ representing the version numbers. Your task is to compare them and find out which one of them is the latest version.

Note:

The input strings consist of digits and dots only and both the strings are started and terminated by a digit. There are no leading zeros and no zeros following a dot in both the strings except in the case of zero itself.

For Example:

Version1 = “1.23.45”, Version2 = “1.23.456”

The first two parts of both the strings are the same. The third part of Version2 is greater than the third part of Version1, thus string Version2 is of the latest version.

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains the string ‘Version1’.

The second line of each test case contains the string ‘Version2’.

Output format:

For each test case, print 1 if version 1 is latest, -1  if version 2 is latest and 0 if both versions are the same.

Print output of each test case in separate lines.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= |Version1| <= 10000 
1 <= |Version2| <= 10000

Time limit: 1 second

Accepted Answer

1. Applied binary search on the data
2. Returned first matching item

Accepted Answer

Using Recursion

The idea is to use a recursive approach to compare the versions. Here we will start iterating through both the strings to extract the number till we reach a dot (or the end of the string) and we will compare both the numbers. If they are the same, we will recursively compare the remaining string. If they are different, we will find out which one of them is bigger and will return the result of the comparison as our answer.

To compare the number represented as strings, we will need to design a function.

The working of comparison function can be understood as:

If the length of string Version1 is greater than the length of string Version2 -
- In this case, the number in string Version1 is greater.
If the length of string Version2 is greater than the length of string Version1 -
- In this case, the number in string Version2 is greater.
If the length of string Version1 is equal to the length of string Version2 -
- Here we will traverse both the strings and find the first different character pair and compare them and output the result. If no such character pair exists, then we will return 0 as both the strings are the same.

Space Complexity: OtherExplanation:

O(min(N, M)), where M is the length of the string Version1 and N is the length of string Version2.

The recursion depth will be min(N, M) in the worst-case scenario.

Time Complexity: OtherExplanation:

O(N + M), where M and N are the lengths of the string Version1 and Version2, respectively.

As in the worst case, all the characters of both strings will be iterated, the overall time complexity will be O(N + M).

C++ (g++ 5.4)

/*

    Time Complexity: O(N + M)

    Space complexity: O(min(N, M))



    where N and M are lengths of strings A and B respectively.

*/





int helper(string &a, string &b, int start1, int start2)

{

    while (start1 < a.length() && a[start1] != '.') 

    {

        start1++;

    }



    while (start2 < b.length() && b[start2] != '.') 

    {

        start2++;

    }





    // Finding the greater one among start1 and start2 

    if (start1 > start2) 

    {

        return 1;

    } 

    else if (start1 < start2) 

    {

        return -1;

    }





    // Comparing both the strings character by character 

    for (int i = 0; i < start1; i++) 

    {

        if (a[i] > b[i]) 

        {

            return 1;

        } 

        else if (b[i] > a[i]) 

        {

            return -1;

        }

    }



    // Check if we reached end of both strings 

    if (start1 == a.length() && start2 == b.length()) 

    {

        return 0;

    }



    // Check if we reached end of string a

    if (start1 == a.length()) 

    {

        return -1;

    }



    // Check if we reached end of string b

    if (start2 == b.length()) 

    {

        return 1;

    }



    return helper(a, b, start1 + 1, start2 + 1);

}





int compareVersions(string a, string b)

{

    int start1 = 0, start2 = 0;



    return helper(a, b, start1, start2);

}

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space complexity: O(min(N, M))



    where N and M are lengths of strings A and B respectively.

'''



def helper(a, b, start1, start2):



    while start1 < len(a) and a[start1] != '.':

        start1 += 1



    while start2 < len(b) and b[start2] != '.':

        start2 += 1





    # Finding the greater one among start1 and start2 

    if start1 > start2:

        return 1



    elif start1 < start2:

        return -1





    # Comparing both the strings character by character 

    for i in range(start1):

        if a[i] > b[i]:

            return 1



        elif b[i] > a[i]:

            return -1





    # Check if we reached end of both strings 

    if start1 == len(a) and start2 == len(b):

        return 0



    # Check if we reached end of string a

    if start1 == len(a):

        return -1



    # Check if we reached end of string b

    if start2 == len(b):

        return 1



    return helper(a, b, start1 + 1, start2 + 1)





def compareVersions(a, b):



    start1, start2 = 0, 0



    return helper(a, b, start1, start2)

Java (SE 1.8)

/*

    Time Complexity: O(N + M)

    Space complexity: O(min(N, M))



    where N and M are lengths of strings A and B respectively.

*/



public class Solution 

{

    public static int helper(String a, String b, int start1, int start2)

    {

        while (start1 < a.length() && a.charAt(start1) != '.') 

        {

            start1++;

        }



        while (start2 < b.length() && b.charAt(start2) != '.') 

        {

            start2++;

        }





        // Finding the greater one among start1 and start2 

        if (start1 > start2) 

        {

            return 1;

        } 

        else if (start1 < start2) 

        {

            return -1;

        }





        // Comparing both the strings character by character 

        for (int i = 0; i < start1; i++) 

        {

            if (a.charAt(i) > b.charAt(i)) 

            {

                return 1;

            } 

            else if (b.charAt(i) > a.charAt(i)) 

            {

                return -1;

            }

        }



        // Check if we reached end of both strings 

        if (start1 == a.length() && start2 == b.length()) 

        {

            return 0;

        }



        // Check if we reached end of string a

        if (start1 == a.length()) 

        {

            return -1;

        }



        // Check if we reached end of string b

        if (start2 == b.length()) 

        {

            return 1;

        }



        return helper(a, b, start1 + 1, start2 + 1);

    }

    

    public static int compareVersions(String a, String b) 

	{

        int start1 = 0, start2 = 0;



    	return helper(a, b, start1, start2);

    }

}

Accepted Answer

Using Iteration

The idea is to use an iterative approach to compare both strings. The approach is similar to the previous approach just that we will be doing it in an iterative manner.

We will use four pointers ‘start1’, ‘end1’ (pointing to string Version1) and ‘start2’, ‘end2’ (pointing to string Version2) all initialised to 0. We will move ‘end1’ to the first dot to the right of ‘start1’ (or the end of the string if no such dot exists) and we will move ‘end2’ to the first dot to the right of ‘start2’ (or the end of the string if no such dot exists).

If :

‘end1’ > ‘end2’
- String Version1 denotes the latest version.
‘end2’ > ‘end1’
- String Version2 denotes the latest version.
‘end2’ == ‘end1’
- In this case, we will compare both the strings from their respective start points to endpoints and output the result of the comparison.
- If both the parts are equal, we will move ‘start1’ to ‘end1’ and ‘start2’ to ‘end2’ and compare the remaining strings iteratively.
- If we reach the end of both the strings without terminating this means that both the strings are equal and we will return 0 in this case.

Space Complexity: O(1)Explanation:

O(1)

Since constant space is required.

Time Complexity: OtherExplanation:

O(N + M), where M and N are the lengths of the string Version1 and Version2, respectively.

As in the worst case, all the characters of both strings will be iterated. Hence, the overall time complexity will be O(N + M).

C++ (g++ 5.4)

/*

    Time Complexity: O(N + M)

    Space complexity: O(1)



    where N and M are lengths of string A and B respectively.

*/





int compareVersions(string a, string b)

{

    int start1 = 0, start2 = 0, end1 = 0, end2 = 0;



    while (true)

    {

        while (end1 < a.length() && a[end1] != '.') 

        {

            end1++;

        }



        while (end2 < b.length() && b[end2] != '.') 

        {

            end2++;

        }



        // Finding the greater one among end1 and end2 

        if (end1 > end2) 

        {

            return 1;

        } 

        else if (end1 < end2) 

        {

            return -1;

        }



        // Comparing both the strings character by character

        for (int i = start1; i < end1; i++) 

        {

            if (a[i] > b[i]) 

            {

                return 1;

            } 

            else if (b[i] > a[i]) 

            {

                return -1;

            }

        }



        // Check if we reached end of both strings 

        if (end1 == a.length() && end2 == b.length()) 

        {

            return 0;

        }



        // Check if we reached end of string a

        if (end1 == a.length()) 

        {

            return -1;

        }



        // Check if we reached end of string b

        if (end2 == b.length()) 

        {

            return 1;

        }



        // Updating values of all the four pointers

        start1 = end1;

        start2 = end2;

        end1++;

        end2++;

    }

}

Java (SE 1.8)

/*

  	Time Complexity: O(N + M)

  	Space complexity: O(1)



  	where N and M are lengths of string A and B respectively.

*/



public class Solution 

{

    public static int compareVersions(String a, String b) 

	{

        int start1 = 0, start2 = 0, end1 = 0, end2 = 0;



        while (true)

        {

            while (end1 < a.length() && a.charAt(end1) != '.') 

            {

                end1++;

            }



            while (end2 < b.length() && b.charAt(end2) != '.') 

            {

                end2++;

            }



            // Finding the greater one among end1 and end2 

            if (end1 > end2) 

            {

                return 1;

            } 

            else if (end1 < end2) 

            {

                return -1;

            }



            // Comparing both the strings character by character

            for (int i = start1; i < end1; i++) 

            {

                if (a.charAt(i) > b.charAt(i))

                {

                    return 1;

                } 

                else if (b.charAt(i) > a.charAt(i)) 

                {

                    return -1;

                }

            }



            // Check if we reached end of both strings 

            if (end1 == a.length() && end2 == b.length()) 

            {

                return 0;

            }



            // Check if we reached end of string a

            if (end1 == a.length()) 

            {

                return -1;

            }



            // Check if we reached end of string b

            if (end2 == b.length()) 

            {

                return 1;

            }



            // Updating values of all the four pointers

            start1 = end1;

            start2 = end2;

            end1++;

            end2++;

        }

    }

}

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space complexity: O(1)



    where N and M are lengths of string A and B respectively.

'''



def compareVersions(a, b):



    start1, start2, end1, end2 = 0, 0, 0, 0



    while True:

        while start1 < len(a) and a[start1] != '.':

            start1 += 1



        while start2 < len(b) and b[start2] != '.':

            start2 += 1





        # Finding the greater one among start1 and start2 

        if start1 > start2:

            return 1



        elif start1 < start2:

            return -1





        # Comparing both the strings character by character 

        for i in range(start1):

            if a[i] > b[i]:

                return 1



            elif b[i] > a[i]:

                return -1





        # Check if we reached end of both strings 

        if start1 == len(a) and start2 == len(b):

            return 0



        # Check if we reached end of string a

        if start1 == len(a):

            return -1



        # Check if we reached end of string b

        if start2 == len(b):

            return 1



        # Updating values of all the four pointers

        start1 = end1

        start2 = end2

        end1 += 1

        end2 += 1



    return

You are given two strings ‘Version1’ and ‘Version2’ representing the version numbers. Your task is to compare them and find out which one of them is the latest version.

Note:

For Example:

Input format:

Output format:

Note:

Constraints:

Top Microsoft Corporation interview questions & answers

Top HR questions asked in Microsoft Corporation