## Thursday, October 20, 2016

### Fraudulent Activity Notification - OpenBracket Code Sprint - HackerRank

Oct. 20, 2016

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:

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

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

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?