Monday, November 14, 2016

HackerRank codesprint - Array construction - after contest (series 2 of 5)

Nov. 14, 2016

Problem statement:
https://www.hackerrank.com/contests/university-codesprint/challenges/array-construction/submissions/code/7825209


Study C# submissions:
1. perfect solution with full score 80
https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

Julia spent more than one hour to read code, but she could not understand the design. So, she decided to work on debugging, add output text info to figure out the design.

Here are workout she did and then figured out the algorithm:

Study more than 2 hours on one of solutions, using recursive solution; but Julia still are not clear about the solution. Need to work on more! Do not give up! Try it every day 10 minutes. It should be easy! 


Julia's work (3+ hours) Try very hard to understand the clever solution by debugging 

-  From the above C# solution:
https://gist.github.com/jianminchen/096ebc5bc1769b83b38ec6eeaabbc7c5

-->   add some debug information to understand the algorithm 

add debugging information to the source code 


-> Here is the log file to understand the algorithm design:

Question 1:
Use your own words to guess how to design the algorithm through debugging process?

Answer:

still confused about line 118, line 119:

118  int newSum     = sum + i * (n - p);

119  int newDiffSum = diffsum + (i * p - sum) * (n - p);

Question 2: What does (n-p) stand for? Can you explain it in one sentence?

Let us work on one more change first:


so, decided to track n-p value on line 118.
C# code with debug info (stage II):


Actionable Items:

1. Run test cases, and compare the time difference 
First, comment out code on line 36, time out on test case 4.

Write a new blog on this testing adventure.
http://juliachencoding.blogspot.ca/2016/11/hackerrank-university-codesprint-array_18.html


2. Study all C# solutions:

2.1. perfect solution with full score 80

2.2. perfect solution with full score 80

2.3. score half score 40

3. understand one term: constructive algorithm
Constructive algorithm: (preprocessing, and then, lookup)
(HackerRank - array construction is a constructive algo.)

Great idea to push hard - cannot get it wrong! that is the attitude for advanced level algorithm involved mathematical analyse.

No comments:

Post a Comment