Sept. 18, 2016
Problem statement
Julia's C# solution is
here.
Here is the timeline Julia worked on the problem solving:
Section 1:
/* 7:08pm - start to read the problem statement
*
* 7:47pm start to write down her approach
* start position is increasing
* How to find word match?
*
* Time complexity -
* Data structure
* Space complexity:
*
* 7:55pm start to code
*
* 10:04pm start to conduct testing
*/
Section 2:
Copy the code from previous practice - substring search, using Boyer algorithm to speed up, avoid timeout issues.
/*
* 8:24pm
* copy code from blog:
* http://juliachencoding.blogspot.ca/2016/04/hackerrank-string-function-calculation_10.html
*
* 8:36 prepare to exit the function
*/
private static bool findUsingBoyerAlgo(string substring, string s, ref int start)
Section 3:
/*
* 9:02pm - start to code
* 9:43pm - still work on the calculation of cost
* - try to think about how many chars to be removed - second step
* 9:57pm use brute force solution first
*/
public static string calculateCost(IList<Match> data,
string message
)
Section 4:
/*
* 10:19pm
* Summary of submission:
* 40.80/60
* Wrong answer for test case: 11, 15
* Try to fix the bug
*/
Summary:
1.
40 minutes to read the problem statement
2.
2 hours coding - including eating a dinner - 20 minutes
55 minutes to work on calculation of cost, looked into interval algorithm, and then, figured out using brute force solution instead.
2. 10:04pm testing
Score 40.80/ 60
Decided to give up bug fix, and then, moved on next question.
Study C# submission - 60 out of 60
1. Use
Trie
2. C#: use
dynamic programming.
Related to
Leetcode 72: "Edit Distance"
3. Study the blog:
Levenshtein Distance wiki
4. Study Java 8 solution - use
Rabin Karp algorithm search class, DP
5.
C++ code - Learn from the best, competitive programmer
6. C++ -
KMP algorithm, DP
7. The programmer - 5 Gold - rank 32/1700
a
Googler, a
blog.
Talk about Google code review - in Chinese, link is
here.
