Sunday, June 26, 2016

AorB - HackerRank workout example

June 26, 2016

 A small problem related to AorB problem, and get some workout on bit manipulation. Still work on desigining a well-defined problem - something small enough, meaningful enough.

 The coding is time consuming, but it is good workout.

Try to put together a meaningful, small function:

           HexaDecimal Char update
           For example, A = 1000
           A | B = C,
           C = 0111
           Then, 4th bit 1 in A should be set to 1.
           number is 1, A' = 0000; assuming that B will provide first 3 bits of 1. 
           Another example, A = 1100,
           A | B = C,
           C = 0111,
           then, 4th bit 1 in A should be set to 0
           function return is 1, A' = 0100; assuming that B will take care first 3 bits of 1.
           1. count how many bits to update (only bit with value 1)
           2. return A's new value A'
           3. Work on bits from left to right, lowest significant bit first
           4. Assume the value > 0, and value < 10^ 50000
           Work on HexaDecimal string,
           For example, D8, work on '8' first, 4 bits 1000, from right to left;
           and then, work on 'D', 1101 - 13
           edge case:
           A= "8D",
           C = "E",
           C is short in length, one char only.

Practice 1: with a bug

Question and Answer:
The design has issues, here is the detail:
function updateHexaDecimal_Remove1s (line 55 - 75) has 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 61 -65, 'D' is compared to 'A'. The design cannot handle difference length correctly.

Practice 2: with bug fix

Read blogs:
From high school:

From Tsinghua University:

No comments:

Post a Comment