Google Python Challenge #2.a
Elevator Maintenance
This is a follow up to my experience with Google’s online coding challenge, you know the one that suddenly appears when you are googling python stuff and wrecks havoc in your perfectly planned week 🙂
If you need an introduction please check my original post where I go through the first question:
⚠️ Spoilers/Warnings: If you get an invitation and decide to accept it I encourage you to try your best to solve the challenges by yourself, least you ruin your opportunity for an interview. If you are going to copy paste this or another answer from Stack Overflow I have no say in the matter and I think this is another place where coding interviews get it wrong, there are only so many ways to solve a problem and coding is more and more a mix of communal group think and personal creativity but I digress. At the very least I hope you seek to understand the technical problem and be able to explain it in your voice, which is what I think these tests want.For the rest of us, this is just a coding riddle which either you love, hate or are trying to get better at.
After finishing the last challenge and requesting a new one you’ll get an ominous message along with a new folder/challenge:
Here it is:
Elevator Maintenance
====================
You've been assigned the onerous task of elevator maintenance - ugh! It wouldn't be so bad, except that all the elevator documentation has been lying in a disorganized pile at the bottom of a filing cabinet for years, and you don't even know what elevator version numbers you'll be working on.
Elevator versions are represented by a series of numbers, divided up into major, minor and revision integers. New versions of an elevator increase the major number, e.g. 1, 2, 3, and so on. When new features are added to an elevator without being a complete new version, a second number named "minor" can be used to represent those new additions, e.g. 1.0, 1.1, 1.2, etc. Small fixes or maintenance work can be represented by a third number named "revision", e.g. 1.1.1, 1.1.2, 1.2.0, and so on. The number zero can be used as a major for pre-release versions of elevators, e.g. 0.1, 0.5, 0.9.2, etc (Commander Lambda is careful to always beta test her new technology, with her loyal henchmen as subjects!).
Given a list of elevator versions represented as strings, write a function answer(l) that returns the same list sorted in ascending order by major, minor, and revision number so that you can identify the current elevator version. The versions in list l will always contain major numbers, but minor and revision numbers are optional. If the version contains a revision number, then it will also have a minor number.
For example, given the list l as ["1.1.2", "1.0", "1.3.3", "1.0.12", "1.0.2"], the function answer(l) would return the list ["1.0", "1.0.2", "1.0.12", "1.1.2", "1.3.3"]. If two or more versions are equivalent but one version contains more numbers than the others, then these versions must be sorted ascending based on how many numbers they have, e.g ["1", "1.0", "1.0.0"]. The number of elements in the list l will be at least 1 and will not exceed 100.Test cases
==========
Inputs:
(string list) l = ["1.1.2", "1.0", "1.3.3", "1.0.12", "1.0.2"]
Output:
(string list) ["1.0", "1.0.2", "1.0.12", "1.1.2", "1.3.3"]
Inputs:
(string list) l = ["1.11", "2.0.0", "1.2", "2", "0.1", "1.2.1", "1.1.1", "2.0"]
Output:
(string list) ["0.1", "1.1.1", "1.2", "1.2.1", "1.11", "2", "2.0", "2.0.0"]
So basically you are given a list of manual versions and you need to order them based on certain rules, as often is the case writing down everything and starting small usually helps, let’s start simple and make some scaffolding.
# Throw pythons sorted function and see what happens..versions = ["2.0","1.0","5.0","3.0"]def solution(l):
return sorted(l)print(solution(versions))# >> ['1.0', '2.0', '3.0', '5.0']
Unfortunately if we throw the 2 test cases to our solution we don’t get the expected answer:
Exp = Expected# versions = ["1.1.2", "1.0", "1.3.3", "1.0.12", "1.0.2"]
Got: ['1.0', '1.0.12', '1.0.2', '1.1.2', '1.3.3’]
Exp: ["1.0", "1.0.2", "1.0.12", "1.1.2", "1.3.3"]# versions = ["1.11", "2.0.0", "1.2", "2", "0.1", "1.2.1", "1.1.1", "2.0"]Got: ['0.1', '1.1.1', '1.11', '1.2', '1.2.1', '2', '2.0', '2.0.0’]
Exp: ["0.1", "1.1.1", "1.2", "1.2.1", "1.11", "2", "2.0", "2.0.0"]
This problem is deceptively easy to understand for us humans but takes a little thinking through for us to explain it to the computer, in the first case 1.0.12 gets sorted before 1.0.2 because sorted places it first , probably because it doesn’t parse the version by the point and treats it like a string, so the strategy to follow now becomes somewhat clear, parse each string as number, then sort, let us parse…
⚠️ NOTE: Somewhere buried in the requirements which I didn't print and vaguely remember, there is the mention that your code will be tested using a very specific version of python: Python 2.7.13, some of the following coding snippets won't run on a different version, but you can substitute list comprehension for regular loops, so;parsed = [e.split(".") for e in l]can be rewritten as:parsed = []
for e in l:
parsed.append(e.split("."))
See also: Python ComprehensionAnd if you need to setup a different python environment like I did I recommend conda
# Parse by dot with split:versions = ["1.0.12", "1.0.2"]def solution(l):
parsed = [e.split(".") for e in l]
return parsedprint(solution(versions))# >> [['1', '0', '12'], ['1', '0', '2']]
We now need to cast the strings into numbers int :
# Cast parsed list elements in to ints:def solution(l):
parsed = [e.split(".") for e in l]
toSort = [map(int, e) for e in parsed]for i,version in enumerate(toSort):
print(list(toSort[i]))solution(versions)# >> [1, 0, 12]
[1, 0, 2]
With the pre processing done, let’s now see if the sorting issue is corrected:
def solution(l):
parsed = [e.split(".") for e in l]
toSort = [map(int, e) for e in parsed]
sortedINTs = sorted(toSort)
return sortedINTsprint(solution(versions))# >> [[1, 0, 2], [1, 0, 12]]
It looks good, all we have to do now is reintegrate each list item into a versioning format (dot separate ) after sorting…
def solution(l):
parsed = [e.split(".") for e in l]
toSort = [map(int, e) for e in parsed]
sortedINTs = sorted(toSort)
sortedJoined = [('.'.join(str(ee) for ee in e)) for e in sortedINTs]
return sortedJoined# >> ['1.0.2', '1.0.12']
All that is left is to throw a bunch of test cases and see how it fares…
versions = ["1.1.2", "1.0", "1.3.3", "1.0.12", "1.0.2"]Got: ['1.0', '1.0.2', '1.0.12', '1.1.2', '1.3.3’]
Exp: ["1.0", "1.0.2", "1.0.12", "1.1.2", "1.3.3"]
versions = ["1.11", "2.0.0", "1.2", "2", "0.1", "1.2.1", "1.1.1", "2.0"]Got: ['0.1', '1.1.1', '1.2', '1.2.1', '1.11', '2', '2.0', '2.0.0']
Exp: ["0.1", "1.1.1", "1.2", "1.2.1", "1.11", "2", "2.0", "2.0.0"]Couple of extra tests with edge cases:versions = ["1.1.1","1.1.11","1.1.9"]
Exp ?: ['1.1.1', '1.1.9', '1.1.11']
Got: ['1.1.1', '1.1.9', '1.1.11']versions = ["1.1.1","1.0.8","1.0.9", "1.0.0", "1", "2"]
Exp ?: ['1', '1.0.0', '1.0.8', '1.0.9', '1.1.1', '2']
Got: ['1', '1.0.0', '1.0.8', '1.0.9', '1.1.1', '2']
And submitting it to advance the challenge…
Real World Versioning
While trying out things I wondered what libraries were there for versioning and if using one would work, I couldn’t get it to work in the heat of the moment but now here without the pressure of the deadline I found out that it is pretty trivial :
from distutils.version import StrictVersion,LooseVersionversions = ["1.11", "2.0.0", "1.2", "2", "0.1", "1.2.1", "1.1.1", "2.0"]sortedVersions = sorted(versions, key=LooseVersion)
print(sortedVersions)# Got: ['0.1', '1.1.1', '1.2', '1.2.1', '1.11', '2', '2.0', '2.0.0']
# Exp: ["0.1", "1.1.1", "1.2", "1.2.1", "1.11", "2", "2.0", "2.0.0"]No idea if this passes tests, but you can use it for your real world versioning needs 🙂Note: Under StricVersion this fails because of the 2 version number which is not allowed see more here:http://epydoc.sourceforge.net/stdlib/distutils.version.StrictVersion-class.html
Conclusions and confessions.
I am going to level with you, soon after googling how versioning in python works I stumbled upon a StackOverflow question where a slightly different version of the above solution (more verbose with for loops) was given, no reference to Google’s foobar challenge was implied, but the version lists were the same I think..
The problem is that once you read someone else’s answer or even skim a solution, you will subconsciously make it your own, which is perfectly fine for your day to day work and figuring out riddles, but I have no idea how Google sees this, I know that some Leetcode sites require original answers, which once more makes me doubt technical questions, challenges and leetcode as a valid way to measure programers, after all there are only so many ways to answer each question…see also:
Regardless of the recruiting aspects this challenge was pretty garden variety and almost easy, but again I had the help of SO and pythons sorted ,map and split (along with list comprehension ). This challenge if anything can be used a crude tutorial/example and I hope you find some use for it.
Thanks for reading !
