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
No comments:
Post a Comment