The world’s leading publication for data science, AI, and ML professionals.

My Google Foobar journey

Level 2.1 – Elevator Maintenance

WALK-THROUGH

Level 2.1 – Elevator Maintenance

FooBar Completion Screenshot ( image by author: Pratick Roy )
FooBar Completion Screenshot ( image by author: Pratick Roy )

Index

  1. My Google FooBar Journey: Level 1 – Getting the Invitation.
  2. My Google FooBar Journey: Level 2.1 – Elevator Maintenance. (This one)
  3. My Google FooBar Journey: Level 2.2 – Gearing Up for Destruction.

The Story So far

You survived a week in Commander Lambda’s organization, and you even managed to get yourself promoted. Hooray! Henchmen still don’t have the kind of security access you’ll need to take down Commander Lambda, though, so you’d better keep working. Chop chop!

So now I had Level 2 access, but defeating Commander Lambda was still a long ways off. The next obstacle in my quest to free my bunny brethren, my next immediate key to progression, was a rather fun challenge.

Elevator Maintenance

At a cursory level, this is quite a simple one really; the devil is hidden in the edge cases. I initially started with a really unclean solution to force myself through, and for the most part it worked. However, I simply couldn’t crack open some of the test cases, no matter how many more hacks I introduced.

So I took a deep breath and a got good night’s sleep. Next morning, I got up, drank some coffee, and refactored the code. It passed all test cases in one shot.

A small tangent on good code

Before I get to the code, here is something I want to stress, always try to write Clean Code. I know it’s not really necessary in a competitive coding environment, in-fact sometimes it becomes detrimental to the cause. In future levels, I have taken many shortcuts that I would never write in a production environment, and would never let any one whose code I am reviewing write. They made my life easier, and the code ran faster, and so I went with it, and you should too in your fooBar journey, but here is the important point, you should feel guilty about doing that.

If you can write working but unclean code without fear of the great man above[1], then you maybe a great coder, but you will be a terrible developer.

If you disagree with this, I’d strongly suggest you to read a post I wrote a while back, and even after reading that if you disagree feel free to drop me a note/comment and we can discuss this further.

What is good code?

Now back to the problem at hand

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 solution(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 solution(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 – Input: Solution.solution({"1.11", "2.0.0", "1.2", "2", "0.1", "1.2.1", "1.1.1", "2.0"}) Output: 0.1,1.1.1,1.2,1.2.1,1.11,2,2.0,2.0.0

Input: Solution.solution({"1.1.2", "1.0", "1.3.3", "1.0.12", "1.0.2"}) Output: 1.0,1.0.2,1.0.12,1.1.2,1.3.3

The problem statement is fairly straight forward. Given a list of versions, sort them in ascending order with order of precedence : major > minor > revision. This is simple enough, let’s come to the edge cases.

  • Minor and revision numbers are optional
  • If two or more versions are equivalent but one version contains more numbers than the others, then these versions must be sorted in ascending order based on how many numbers they have.

Before addressing these, lets first see the solution code

Before running down the code, let’s first discuss a common coding construct.

Comparator[2].

Simply put a comparator always takes the form:

Now if you observe, here we are not using any if statements to make the comparison, but simply subtracting the two hash-codes.

This subtraction is actually a simple and common convention to achieve this. For example consider two ints, a and b, then

a - b < 0, if a is smaller
a - b == 0, if a and b is same
a - b > 0, if a is larger

which exactly echos our desired output.

This becomes super useful with sorting, as the Java Standard Library provides sort functions that can sort a collection of any object based on a comparator. We will be making use of this concept not once but twice in our code.

Code Rundown

So with comparators out of the way. lets rundown the code and cover the above mentioned edge cases

  • First we sort the array based on a custom comparator.
  • Inside our comparator, we first split the versions to its major, minor and revision types.
  • Again, we write another comparator ( this time without the pomp of inheritance, but basically it does the same thing ), for comparing the specific version types.
  • We compare the version types in the required precedence of major > minor > revision. If at any stage, both are not equal, we simply return the output of the inner comparator. If they are, we move on to the next type. If at the end, there is no difference (Edge case 2), we sort based on the version subtype counts.
  • In our inner comparator, we first check if the specific version subpart exists in either of the versions (Edge case 1). If it does not we default it to 0, else we pick it up and then compare them as we would do in any integer comparator.

An Important Takeaway

In the above section, I gave a rundown of the code to help beginners understand the core concepts, but for anyone who has spent any decent part of their lives dabbling in front of an IDE, did I need to?

What the code is doing is doing is super clear without the need for any documentation. Sure, it could be even better, we could add enums to make the version types more clear, and use properly named private methods to make the edge case handlings more intuitive. But what we should appreciate here, is that following clean code principles, handling of edge cases are no longer ugly outliers that break the flow of thought, but are natural extensions to it.

Now coming to the fact that I did not make it as clean as I could have, makes me feel super guilty. So let’s do some penance.

I won’t give a rundown here as frankly it’s not needed. Moreover I would encourage you to only look at the solution method, and see if you can understand the flow without needing to see the implementation of Version and VersionType, which is why I have kept them at the bottom. If you can understand what the code is doing by only having to read about 1/4th of codebase, then my job here is done!


In my next post, I’ll go into the second challenge for Level 2: Gearing Up for Destruction. When I do, I will link it here. To be notified of the same, consider following me on medium and subscribing to get an email of the same sent straight to your inbox!

Click Here To Subscribe 🙂


Sources, Footnotes & Further Reading Links


Related Articles