Compare Version Numbers | InterviewBit | Solution Explained
I explain the solution to the problem Compare Version Numbers on InterviewBit in detail. Problem Link.
0. Compare Version Numbers: Problem Discussion
0.0. IO Format
- Given: two strings which are version numbers, ver1 and ver2
- Goal:
- If ver1 > ver2 return 1,
- If ver1 < ver2 return -1,
- otherwise return 0.
0.1. Examples
1. Compare Version Numbers: Observations & Logic
1.0. Intuitions
- the versions are strings, and we need a way to compare the versions
- converting strings to integers will help us compare them
- we know that a version has different numbers split by ‘.’, so we can
- split the string by ‘.’ character
- map all the string values to an integer
- get the list
- we can do all that in python using one single line:
list(map(int, ver.split('.')))
All right! We have extracted the information out of the input. Now what?
We need a way to compare two items in the two lists, simultaneously. So, we can use the zip operator in python3.
class Solution:
def compareVersion(self, ver1, ver2):
ver1 = list(map(int, ver1.split('.')))
ver2 = list(map(int, ver2.split('.')))
for v1, v2 in zip(ver1, ver2):
if v1 > v2: return 1
elif v2 > v1: return -1
return 01.1. Implementation Issue
Here’s the thing though, zip only works well if the length of the iterables are the same. That is, only when len(v1) == len(v2) list.
In the case where there is a smaller list, zip will terminate with it.
For example, if we zip([1,2,3], [1,2,3,7]) we will terminate at 3! We will never get a chance to compare 7. So what do we do?
Here lies a key point: if one version is shorter in length to the other, we can append dummy zeroes to it!
For example, if we have a tricky case like [1,3,3,0,0,7] and [1,3,3], we need to be able to pad zeroes like so:
One way to not do this manually is to use zip_longest from itertools, as the implementation below will show.
2. Compare Version Numbers: Implementation
2.0. Code
from itertools import zip_longest
class Solution:
def compareVersion(self, ver1, ver2):
ver1 = list(map(int, ver1.split('.')))
ver2 = list(map(int, ver2.split('.')))
for v1, v2 in zip_longest(ver1, ver2, fillvalue=0):
if v1 > v2: return 1
elif v2 > v1: return -1
return 0
2.1. Code (without zip_longest)
class Solution:
def compareVersion(self, ver1, ver2):
ver1 = list(map(int, ver1.split('.')))
ver2 = list(map(int, ver2.split('.')))
i, j = 0, 0
m, n = len(ver1), len(ver2)
if m > n:
ver2.extend([0]*(m-n))
elif n > m:
ver1.extend([0]*(n-m))
for v1, v2 in zip(ver1, ver2):
if v1 > v2: return 1
elif v2 > v1: return -1
return 0
2.2. Complexity Analysis
- Time:
O(N), where N is the number of elements in the longest list, which can be the same order as the number of characters in the string:1.1.1 --> [1,1,1] - Space:
O(N), since we have to store the lists of integers of both the versions separately
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Comments
Leave a Reply
This site uses Akismet to reduce spam. Learn how your comment data is processed.
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this
Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.
A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.
Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.
To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.
Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.
This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.
Understanding why solar energy consultants assist clients via Matthew D’Agati.
Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8