HackerRank competition debriefing, Week of Code 32

My HackerRank profile: link

(Disclaimer, I’m in no way affiliated to HackerRank.com, this is not paid publicity or anything, just me doing a write up on the competition I entered there.)

Spoiler

I tried 4 of the 6 challenges, 2 easy, 2 medium.
The 2 easy ones are 100% completed, and the 2 medium challenges I have working solutions but not optimal algorithms that cause timeout.

My rank is 1777 out of 8449 people trying to solve the challenges.

This puts me roughly in the first 21%, which isn’t bad considering I haven’t even had time to try the 2 hard ones. But I guess it becomes increasingly harder to gain rank so we will see next time if I can improve on that score. (And to improve I’ll have to learn!)

My HackerRank profile: link

What is HackerRank?

I’ll quote the HackerRank FAQ here

HackerRank is a place where programmers from all over the world come together to solve problems in a wide range of Computer Science domains such as algorithms, machine learning, or artificial intelligence, as well as to practice different programming paradigms like functional programming.

It also provides weekly/monthly competitions (and also job offers) that you can participate in. The duration of the competitions range from 1 hours for the shortest, to 1week.

The competition

The competition I entered this week was the “Week of Code 32”. It lasts a full week, and is composed of 6 problems, 1 unlocked every day from Monday to Saturday, and with increasing difficulty. You are awarded points for solving the problem, the easier the problem is, the less points you earn for solving it.

The difficulty doesn’t come only from solving the problem, but solving them efficiently as we will see after. Test cases reviewing the solution you submit are timed, and if you exceed the time limit, it is as if you failed to answer. Clever algorithms and data structures are needed.

The problems

The first 2 challenges were easy, just warmup problems like duplicate a string and sort a list to achieve some computations on them. Nothing fancy and the time requirement were not too hard so not too hard to write a solution earning the maximum points. I will not talk about that here, but about the 2 medium challenges.

The First Challenge: Geometric Trick

Here I’ll give you problem text then I’ll explain what I’ve done.

Consider a string s of length n consisting of the character in the set {a,b,c}.  We want to know the number of different (i,j,k) triplets (where 0<=i,j,k<n) satisfying two conditions.

• s[i] = “a”, s[j] = “b”, s[k] = “c”
• (j + 1)² = (i + 1)(k + 1)

We consider two triples (i,j,k), and (x,y,z), to be different if  and only if (i!=x) or (j!=y), or (k!=z).

Given n and s, find and print the number of different (i,j,k) triples.

My approach

You can find the code here.

My approach for this particular problem was as such. I first had the idea for an algorithm quite straightforward but most likely not efficient. So I decided to implement it, judging that I’d need only 1 hours approximately to get it running. So here I’ll describe the naive approach.

Naive way

I went the naive way. I put in a list the indexes of all the letters ‘a’ , in another list the indexes of all the letter ‘b’, and finally in a list the indexes of all the letter ‘c’. (We gonna call those lists “indexA, indexB, indexC” respectively).

Then I nest 3 loops, over IndexA, indexB, indexC and I see if I can satisfy the condition     (j + 1)² = (i + 1)(k + 1) [with i being an element of IndexA, j an element of indexB, and k and element of indexC].

This is highly inefficient but really easy to code.

	/**
	* Consider a string s of length n with alphabet {a,b,c}.
	* We look for the number of different triplet (i,j,k) where 0<=i,j,k<n, satisfying!
	* – s[i] = "a", s[j] = "b", s[k] = "c"
	* – (j + 1)² = (i + 1)(k + 1)
	* @param s A string we look the triplet in
	* @return Number of different triplets such as enonced above.
	*/
	public static int geometricTrick(String s){
	//extract index for a,b and c in lists
	List<Integer> indexA = new ArrayList<>(s.length());
	List<Integer> indexB = new ArrayList<>(s.length());
	List<Integer> indexC = new ArrayList<>(s.length());
	//here we fill the lists created just above
	for(int i=0;i<s.length();i++){
	if(s.charAt(i)=='a')
	indexA.add(i);
	if(s.charAt(i)=='b')
	indexB.add(i);
	if(s.charAt(i)=='c')
	indexC.add(i);
	}
	//and then we try to find indexes satisfying the condition
	int res = 0;
	for(int tmpA:indexA)
	for(int tmpB:indexB)
	for(int tmpC:indexC)
	if(((tmpB+1)*(tmpB+1))==((tmpA+1)*(tmpC+1)))
	res++;
	return res;
	}

view raw

GeometrickTrick.java

hosted with ❤ by GitHub

Worst Case Time Complexity Analysis

• Creating and filling the list. Putting the indexes in the lists is done in one pass over the string, so O(n) with n the size of the string. The sum of the numbers of the elements in the 3 list is n.
  Adding to the end of a list is O(m), with m the size of the list but with the ArrayList, it’s O(n) amortized, so O(1) most of the time and O(n) if we need to resize the underlying array.  Here we created the ArrayList with enough space, wasting memory but at least we know we wont have to resize the list so add is O(1).
  So the total cost of the operation is O(n)*O(1) => O(n)
• Nested loops: Here we have nested loop, killer of performance…
  Looping around a loop take time related to thes size of the list. Lets say size of indexA is sizeA, indexB is sizeB and indexC is sizeC. Wha we do inside the nested loop is some mathematical operation, so maybe not fast but constant or O(1) regarding time complexity.
  So we get O(sizeA * sizeB * sizeC). If the letter are evenly distributed (which we will assume it is, or close to it), sizeA = sizeB = sizeC = n/3 (I write equal but I mean roughly equal). So we get O(n/3 * n/3 * n/3) => O(n^3/9)=>O(n^3) because constants doesn’t matter when we look into asymptotic complexity.O(n^3) is very bad, here when we look at the input size we moslty want something close to O(n*log n). Still very wide road to reach it.(I assumed sizeA = sizeB = sizeC = n/3, but it could have been sizeA=n/10, sizeB=n/2, sizeC= 9n/10, the asymptotic time complexity stay the same because constante are too small to have an impact when n gets very very large.)

Space Complexity Analysis

• Creating the list: we have 3 list of size n, which is the size of the input string. So 3n * size of an int + overhead for the list
• An int for the result, and 3 temporary int for the loops, nothing big.

So for the space complexity, additionally to the String s of size n, we have 3n * size of int + overhead for list + 4 int which is mostly equal to 3n*size of int (32bits in java) => 96n with 0<= n < 5*10^5 (input size limit specified by the challenge).

It’s not very good because I could probably do it with only n*size of int space, but it gives me a little bit more performance for not resizing array of the ArrayList so not a problem.

Results

With this approach, I got 3 points out of the maximum being 36.45. Only 2 tests cases were passing, everything else was timing out. Time to try something better.

My 2nd try

Here is the code of my second try.

	public static int geometricTrickv2(String s){
	Set<Integer> indexA = new HashSet<>(s.length());
	Set<Integer> indexC = new HashSet<>(s.length());
	List<Integer> indexB = new ArrayList<>();
	for(int i=0;i<s.length();i++){
	if(s.charAt(i)=='a')
	indexA.add(i);
	if(s.charAt(i)=='b')
	indexB.add(i);
	if(s.charAt(i)=='c')
	indexC.add(i);
	}
	int res = 0;
	for(int tmpB:indexB){
	int powB = (int)Math.pow((double)(tmpB+1),2);
	//Set<Integer> factors = new HashSet<>();
	for(int i=2;i<=Math.sqrt((double)powB);i++){
	if(powB%i==0){
	if(i != powB/i)
	if(indexA.contains(i-1)&&indexC.contains(powB/i-1))
	res++;
	if(indexC.contains(i-1)&&indexA.contains(powB/i-1))
	res++;
	else
	if(indexA.contains(i-1)&&indexC.contains(i-1))
	res++;
	}
	}
	}
	return res;
	}

view raw

GeometricTrick.java

hosted with ❤ by GitHub

Explanation

First thing: I build 2 HashSet with the indexes of the letter ‘a’ and ‘c’ and a list of the indexes of the letter ‘b’ in the string s.

Then, I’ll work with the given condition (j+1)² = (i+1)(k+1), which can be seen as:

• find i and k such as i+1 and k+1 are complementary divisor of (j+1)²

(By complementary I mean: say you have 25, his divisors are 1,5 and 25. 1 and 25 are complementary in the way that 1*25 = 25, 5*5=25 but 1*5!=25. so 1 and 25 are complementary, 5 is complementary with himself but (1 and 5) and (5 and 25) are not complementary )

To find all the divisor of n, I only need to search up until sqrt(n). (It’s a property I remember from high school, hope I didn’t screw up) because I can calculate the divisor and their complementary counterpart on the same iteration.

Then once I am calculating those divisor, I need to check if they are in the HashSet containing the indexes of ‘a’ and ‘c’, and satisfying the condition.

Worst Case Time Complexity Analysis

At first I thought this algorithm was O(n * sqrt(n)) with n being the length of String s.
My analysis was that I loop over all the indexes of the letter “b” so O(n) and then find all his divisors O(sqrt(n)) so O(n * sqrt(n)). But in fact, while it’s true I’m looping over indexes of “b”, I’m looking for the divisors of index of “b” squared! so O(n * sqrt(n*n)) => O(n²). Which is faster than previously but still really bad! This error of judgement was pointed out by ratchet_freak   , props to him!

Results

This time I got 9 points instead of 3, good but still not great.
The challenge did end just 1hour after I posted my new answer  so that was my final submission.

How to do better?

I then tried to find something better but could find on my own so I asked on stackexchange codereview

You can see the accepted answer use a good mathematical trick to lower the bound to O(n * sqrt(n)) (for real this time) and the writer of the answer told me to use String.charAt() instead of storing indexes in HashSet as the operation is O(1) in String because the behind the scene it is an array. So this save also a lot of memory!

Really great answer by ratcher_freak, I do recommend you go see his answer to my post.

Conclusion

Doing a competition was fun! It really motivates me to learn a bit faster than usual and gives a feeling of progression/accomplishment when you go up on the ladder solving a new challenge! I also learned some good tricks that I’ll try my best to apply for the next competition! Hope it inspired you as well to give it a try, HackerRank got some very short or very long competition, but there are a lot of website proposing the same kind of competition so try it out!

Also tell me in the comment if you know a better algorithm, in O(n log n) or O(n)!
I’d be really curious to see how to get there!