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