Compare Versions

Moderate
0/80
profile
Contributed by
1 upvote
Asked in companies
MicrosoftExpedia GroupLinkedIn

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1.2.4
1.2.3
10.2.2
10.2.2
Sample Output 1:
1
0
Explanation For Sample Input 1:
For the first test case:
The first two parts of both the strings are the same but the third part of the 1st string is bigger than that of the 2nd string. Hence our answer is 1.

For the second test case:
As both the versions are identical in this case, the answer will be 0 in this case.
Sample Input 2:
2
123.45
123
1.999
10
Sample output 2:
1
-1
Hint

Think of a recursive comparison approach.

Approaches (2)
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:

 

  1. If the length of string Version1 is greater than the length of string Version2 -
    • In this case, the number in string Version1 is greater.
  2. If the length of string Version2 is greater than the length of string Version1 -
    • In this case, the number in string Version2 is greater.
  3. 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.
Time Complexity

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).

Space Complexity

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.

Code Solution
(100% EXP penalty)
Compare Versions
Full screen
Console