Three difficult HackerRank problems – and how to solve them
To get a job as a computer programmer on Wall Street or in the City, you may have to pass a HackerRank test. Last time we looked, Goldman Sachs, Morgan Stanley, Bank of America, Bloomberg, BNY Mellon and Deutsche Bank were all signed-up, as was the hedge fund Two Sigma. There are typically three types of problems that you’ll have to deal with: multiple-choice questions, a SudoRank exercise and a coding exercise. Here are tips for how to solve the latter.
Searching for a 10 lines long paragraph in Google is not an acceptable option, especially since the HackerRank website disables copy/paste in the description area. A workaround is to search for the title of the exercise, which uniquely identifies a question on HackerRank and will be mentioned in related solutions posted online, making it perfect for being indexed by Google, according to The HFT Guy, a London-based developer who has worked at high-frequency trading shops.
Often for basic exercises the first result is the question, and the second result is the solution, which seems easy, but you have to double-check that the solution is correct. In addition, you can rarely find solutions to the most challenging coding exercises online, especially since firms usually write their own questions and exercises.
Here are some of the more difficult sample HackerRank coding exercises and solutions from Martin Kysel, a Cambridge, Massachusetts-based software engineer at NuoDB, which runs an elastic SQL database for cloud applications.
HackerRank ‘Insertion Sort Advanced Analysis’ Solution
Insertion Sort is a simple sorting technique. Sometimes arrays may be too large for you to wait around for insertion sort to finish, so Kysel suggests another way that you can calculate the number of times Insertion Sort shifts each element when sorting an array.
If ki is the number of elements over which the ith element of the array has to shift, then the total number of shifts will be k1 +k2 +…+kN.
Time complexity is O(N*log(N)) and space complexity is O(1).
There are more solutions with nlogn time for this challenge. Kysel decided to use Binary Indexed Trees as they are a data structure I am not that familiar with. The other solution includes a modified merge-sort that is posted as the problem editorial. BITs are effective for computing cumulative frequencies in log(N) time and are therefore perfectly suited for this problem. They assume a full tree and therefore are bound to the maximal range defined in the problem specification.
[caption id="attachment_307151" align="alignnone" width="300"] Source: MartinKysel.com[/caption]
HackerRank ‘Matrix Rotation’ Solution
In the Algo Matrix Rotation exercise, you are given a 2D matrix, a, of dimension MxN and a positive integer R. You have to rotate the matrix R times and print the resultant matrix. Rotation should be in a counter-clockwise direction.
Time complexity is O(N×M) and space complexity is O(NxM).
There is just lots of code, but the actual solution is pretty simple, according to Keysel. First, you extract layers to simplify the logic. Then, you rotate the layers similarly to the Codility Rotation challenge.
[caption id="attachment_307152" align="alignnone" width="195"] Source: MartinKysel.com[/caption]
HackerRank ‘Sherlock And Valid String’ Solution
To complete the Sherlock and Valid String exercise, you need to know that a “valid” string is a string S such that for all distinct characters in S each such character occurs the same number of times in S.
Time complexity is O(N) and space complexity is O(1).
Keysel optimized this solution to the minimal case that passes all tests on HackerRank. It seems that each character occurs one or two times. The logic of Keysel’s solution is based on character counts.
If they are all equal, then all characters occur exactly N times and there is no removal needed.
If two or more have less or more characters, then there is no way to fix the string in just one removal.
If exactly one character has a different count than all other characters, then Keysel says to remove this character completely to fix S.
[caption id="attachment_307153" align="alignnone" width="300"] Source: MartinKysel.com[/caption]
Have a confidential story, tip, or comment you’d like to share? Contact: email@example.com
Bear with us if you leave a comment at the bottom of this article: all our comments are moderated by actual human beings. Sometimes these humans might be asleep, or away from their desks, so it may take a while for your comment to appear. Eventually it will – unless it’s offensive or libelous (in which case it won’t).
Photo credit: alvarez/GettyImages