June 26, 2016
HackerRank: AorB
problem statement
Quick summary of 3 practices
1st practice: failed all test cases except first one.
C# practice: only pass 1 test case, failed all other cases, score 0/ 50
2nd practice: fix the bug - major issue, but failed most test cases still.
Fix the above issue - comparison issue, but still failed most of test cases.
3rd practice: pass all test cases.
Work on the test case, fix the bug.
C# practice passes all test cases.
Long story short - 8 hours labor
So, starting from very beginning:
1st practice: failed all test cases except first one.
C# practice: only pass 1 test case, failed all other cases, score 0/ 50
Spent over hours, go over again and again the problem statement, and then play with HackerRank unknown test case, try to figure out what is wrong.
So, work on problems one by one, it takes hours up to 8 hours. Great workout!
Small problems first
Here are a list of problems to work on, very good workout:
1. Remove leading 0 in HexDecimal string, for example, "08" should be "8".
C# code.
2. Get a char from a binary number with 4 bits: 1111, return F; 1000, return 8.
C# code.
3. Get an integer value from HexDecimal char - for example, 'F', return 15; '9' return 9.
C# code
4. Work out a small problem - AorB - try to define a function, get count of bits to change from 1 to 0,
in A, based on AorB value.
C# code.
5. (
6/27/2016 added)
Write a function to do A or B calculation, A and B is bigger than 0, and smaller than 16^(50000)
Test case:
Hexadecimal: 1000 | 11000 = 11000
C# code
June 27, 2016
Question and Answer:
1. How is the practice?
The design has issues, here is the detail:
function getChangeBits_From0To1, getFirstNumberFirst1To0_LetSecondOneTake1, getBitNumber_From1To0_strVersion all have same fatal error:
Review the design: A|B = C
D8 A
A01 C
For example, A string "D8", AorB string "A01",
then, D should compare to 0, and 8 should compare to 1
So, the solution is to reverse the string.
8D A's reverse
10A C's reverse
But in the the code from line 397 - 399, 'D' is compared to 'A'. The design cannot handle difference lenght correctly.
That is the reason of failing most of test cases.
1. line 385 function getChangeBits_From0To1 has a bug:
inside the function,
line 395: the Hexadecimal char is not matching between from and AorB sum.
For example, A string "D8", AorB string "A01",
then, D should compare to 0, and 8 should compare to 1
But in the the code from line 397 - 399, 'D' is compared to 'A'. The design cannot handle difference length correctly.
That is the reason of failing most of test cases.
2. Same problem applies to funcation getFirstNumberFirst1To0_LetSecondOneTake1
3. And also, line 268 - line 282 can be shortened, remove if/else from line 279 - 291. Just update variable: afterAnd_From value
4. Same problem applies to function getBitNumber_From1To0_strVersion
2nd practice: fix the bug - major issue, but failed most test cases still.
Fix the above issue - comparison issue, but still failed most of test cases:
https://gist.github.com/jianminchen/15c0470a5bb86fb06bc30a4b83465313
Need to make this test case work, through test case provided by downloads:
input:
3
25
B631EB5AE
601C227E1
707AC8792
12
CAF7028FD
59B5AC1CE
CAF1B7B7F
3
81B9BB94E
8AB3CA95E
8BBBFB95E
output:
C8582
707A00790
8AF10287D
48B1B534E
B9BB94E
8BB3CA95E
3rd practice: pass all test cases.
Work on the test case, fix the bug. C# practice passes all test cases:
https://gist.github.com/jianminchen/cf823376a23a36304da82ca975f77fa1
Bug fix comparison - what to change:
2. How long is the practice and bug fix? What are major issues?
Time spent is much more than expected.
Major issue is about the design of function, too long to handle without a bug. Need to think about breaking into small function.
function getFirstNumberFirst1To0_LetSecondOneTake1 -
line 249 to 330, almost 100 lines. Need to redesign
the function, into multiple functions.
Warm up the algorithm, write another one in practice:
things to work on:
1. function name should be changed: (A|B = c AorB problem)
function name:
getFirstNumberFirst1To0_LetSecondOneTake1
new function name:
getGreedy_A1To0_BStayUpdateTo1 -> get_A_SmallestPossible
greedy algorithm to make A as small as possible
2. Use array to reduce the total of variables, and make the code less lines
3 variables: A, B, C 3 string
line 260 - line 262, string from, to, fromB,
Declare a string array with length [3],
0 - A
1 - B
2 - C
3. line 272 - line 274, 3 variables,
intFrom, intTo, intFrom_B,
use array to reduce variable to one
4. Line 279, array variable - arr - move defintion out of for loop (line 270 - 330)
5. Declare an array to store chars, and add a new function called toChar(int)
line 298, line 317, line 318
public static char tochar(int val, int powerof2){
return (char)(value/powerof2 + '0');
}
6. getCharFromBinaryNumber function name is too long, maybe, define a class BinaryNumber, and then add getChar api
