HackerRank: string algorithm - Reverse Shuffle Merge (II) - next - forming a partial correct idea

April 2, 2016

  Problem statement is here.   

  Introduction

Julia likes to share her experience, advance level on HackerRank. It is not bad in the weekend, spend 2 hours messing around the ideas/ hackerRank, come out a clear greedy algorithm. The hackerRank definitely helps Julia to shape her idea from start to end.

Practice talk 

  First two hours work - failed twice, detail here in the blog.     

  Here is the idea after 2 hours intensive work:
of course, "abc" is the smallest one in lexicographical order, but the possible string formats:
  *a*b*c*, not *abc*, now * means any number of any chars.

 Let us count how many of a, b, c can be skipped when we do linear scan of a string.

 Now, it should be very easily to introduce greedy algorithm.

 For example, if linear scan from left to right, visiting char b, then, we have to check how many b's left can be skipped, if it is bigger than 0, we have to check any char before b has anything left or not. For example, if a still has some number left to skip; we hold on b, just skip current b.

 Otherwise, count current b into the string we are looking for, and decrease the number count of b (recording how many b can be skipped).

Use an example to explain:
  a2b2c2 case,
 ba*, the half should be a1b1c1,
 so, skip first char 'b', since greedy algorithm / let 'a' go first.

 Give it a try, implement the idea:

 Some statistics: advanced algorithm 4+ hours - A mountain - "Sea to sky Gondola" to climb

Spent 9:47 am - 11:47 am, wrote code, but still failed most of case; only pass "eggegg";
Hard to concentrate, and think about the issue - this reverse is tricky!

Here is the C# solution - 3 rd failed try. Code is here.

Baby hacker is crying, still score zero: 4 hours work. Code is here.

Now, it is 1:47 pm, another 2 hours with music, the code was submitted, now score 16.67/ 50. Still need to work on more before Julia plan to read other people's solution:

Some statistics: advanced algorithm 6+ hours - A mountain - Sea to sky Gondola to climb. Code is here. 

Need to stop, go to enjoy outdoor activities!

Baby hacker is showing off her baby steps, the report of test cases pass/ fail on Hackerrank is here.

Try to fix the error, give up - the design has another flaw,
test case:
djjcddjggbiigjhfghehhbgdigjicafgjcehhfgifadihiajgciagicdahcbajjbhifjiaajigdgdfhdiijjgaiejgegbbiigida
i=50, s[i] = 'g', the design let 'g' skip, but
i=52, s[i] = 'i', 'i' has to be added to the output, no more skip.

<-  Julia, think about stack, use some data structure to do reverse work <- such a great workout! Release all my stress and headache, and be humble!

5:12 pm, statistics: Another 3 hours, total: 9+ hours 

Follow up 

May 3, 2017

HackerRank: string algorithm - Reverse Shuffle Merge (I) - First step: Failed twice

March 31, 2016

  Problem statement is here.

 Introduction

 The algorithm is in advanced category. 8:17 am - 10:08 am. Document 2 hours work as a hacker, Julia. First time, Julia thinks that hacker is a good name!

 Practice Talk

Start from 8:19 am, 9:18, tried twice, passed one test case, failed others with wrong answer;  then, need to pay attention to reverse string word.

Spent more than 20 minutes to think, but could not figure out the solution. Have to stop here. Write down the analysis first. Come back later.

The naive solution is to count string in each char in "abc...z", and then, half of count will construct a new string.

For example, if the string counting: a2b2c2
then, the string A is one of strings {abc, bac, cba, bac, aca, cab}

Of course, "abc" is the smallest one in lexicographical order, but the possible string formats:
  abc***
  *abc**
  **abc*
  ***abc

Or, go through each possible string - find the minimum one, smart way to compare with previous one, keep the smallest one.

Assuming that the string is matching.

Got the idea. Linear solution.  From 8:19 am - 8:45 am, more than 20 minutes to come out the idea.

9:00 am -
Two functions - one function is to count the number to determine that count for each char is even. Another step is to go over the string, take substring(i, 3).

20 minutes to write a code, a bug to fix: wrong answer
Need to make sure that substring count matching count first, otherwise, skip it! 
  
9:15 am, bug is not fixed; and then, notice that the string has to be reversed! 

10:16 am, still not fixed. Julia, this is a greedy algorithm, why is the greedy part? You missed merge part in the construction merge(reverse(A), shuffle(A)). So, you have to redesign the algorithm.

Conclusion

1. Design algorithm - advanced - know why it is advanced, examine the idea and see if you can make it first; Otherwise, waste time to write code

Two hours, failed two tries! A new hacker is getting her valuable lesson using 2 hours.

Here is the C# code.

Follow up 

Blog review on May 3, 2017