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

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.

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:

10th submission:  score 40 out of 40, using bucket sort.

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

2. Radix Sort - a distribution sort

3. Leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm

Encouraging ending notes:
Can you give out a summary for the practice?

10th submission:  score 40 out of 40, using bucket sort.

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 -

No comments:

Post a Comment