Julia spent over 8+ hours to work on this algorithm, and finally, at the end of day, she knew that she had to read problem statement again and figured out a new idea. She found the solution and scored 40 of 40.
But, Julia likes to write down her journey, and reminds herself to be smart, be able to find optimal solution in first time.
Here is the problem statement:
https://www.hackerrank.com/contests/openbracket/challenges/fraudulent-activity-notifications
And then, her submissions:
1. First submission:
pass 2 test cases, 5 test cases - runtime error
https://gist.github.com/jianminchen/ed96f667ca20d4ce6e5da61315e17cd5
Over 3 hours work,
1. timeout issue - use binary search to replace linear search, and see if the timeout issue can be solved.
2. Add position/ remove position - try to implement O(1) insertion O(1) deletion algorithm
code has flaws, insert position (p1) / remove position (p2),
p1 >= p2 or p1 < p2.
3. Look into C# bulk copy, Array.Copy, not sure if Array.Copy can be O(1) instead of O(n), using bulk copy, look up stack overflow a few times.
2. Find bugs, and continue to write new code.
https://gist.github.com/jianminchen/3beb1b21d99a62eb607f9f3b40a61bee
add new function called binarySearchAdd
function customizedArrayCopy (line 181 - line 190) - try to fix bugs
discuss different cases - 90 lines of code, hard to write without a bug, and so many cases,
think about cyclomatic complexity, or execution path, how many execution path with this design.
Julia spent hours on this function customizedArrayCopy, and it is hard to spot error/ fix error
on this function.
(Oct. 26, 2016, customizedArrayCopy function - If two case (line 267 - line 288), else, there are
3 nested statement: if/else if/else (line 289 - line 342); so, in total, 5 cases, line 252 - line 346;
This function is breaking SRP - single responsibility principle. The function spanning almost 96 lines
of code, Julia has to take more than 6 hours to write/ debug/ reason. This is not the code for
HackerRank contest!)
..., continuously submitted 9 times, score 0.
9th submission:
https://gist.github.com/jianminchen/0b7fe2b10b324e710066128682992c74
10th submission: score 40 out of 40, using bucket sort.
https://gist.github.com/jianminchen/5e85135f68bc9be02be7f7390647ae00
Timeline analysis:
7:45am - start to read problem statement
9:00am - first submission, pass 2 test cases, but timeout on other 5 test cases,
Binary search can improve time complexity from O(n) to O(logn)
Work on binary search algorithm
10:11am reviewed binary search function code
10:24am found bugs related to Add position vs Remove position
10:40am look up Java AddRange, C# bulk copy
... (Julia likes to play with Array.Copy, and other things - logic thinking if/ else. But to be a competitive programmer, Julia has to learn to sharpen her thoughts, work on optimal solution instead.)
12:00 - 9:30pm - work on the coding, try to write bug-free code, mess with ideas using Array.Copy, naively thinking about bulk copy - Time Complexity O(1)
9:30pm - gave up all the solutions, read problem statement and find a new idea:
9:30pm - 10:07 write a bucket sort algorithm, without too much effort, succeed.
Time complexity:
O(N^2) -> O(NlogN) -> O(N), N is the number of days.
Previous work on distribution sort, bucket sort:
1. Leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm
http://juliachencoding.blogspot.ca/2015/06/leetcode-maximum-gap-no-164.html
2. Radix Sort - a distribution sort
http://juliachencoding.blogspot.ca/2016/05/radix-sort-distribution-sort.html
3. Leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm
http://juliachencoding.blogspot.ca/2015/06/leetcode-distribution-sort-algorithm.html
Encouraging ending notes:
Can you give out a summary for the practice?
Answer:
10th submission: score 40 out of 40, using bucket sort.
https://gist.github.com/jianminchen/5e85135f68bc9be02be7f7390647ae00
line 141 and line 142:
int SIZE = 201;
int[] dPriorDays = new int[SIZE];
Just use space to trade off time, reduce time complexity from two loops on n - number of days to
one loop on n (2*10^5), and one loop on SIZE (201) which is also constant tim O(1). Basic facts:
n^2 will be around 4*10^10, it will be around 40 billion. The time complexity is shortened to 1 of 1000. Things to work on:
Spend 2 hours to read this mentoring business in IT business -
http://www.theeffectiveengineer.com/blog/secret-to-growing-software-engineering-career |
No comments:
Post a Comment