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.

https://www.hackerrank.com/contests/june-world-codesprint/challenges/aorb


 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
https://gist.github.com/jianminchen/f4d8761ca6126052e3df792212861436

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
https://gist.github.com/jianminchen/c8501eabdb774710c100a1aa06049d8e

Read blogs:
From high school:
http://tarawa.github.io/

From Tsinghua University:
http://maskray.me/

https://threads-iiith.quora.com/

http://heliang.me/blog/?page_id=488

http://heliang.me/blog/?tag=%E9%9D%A2%E8%AF%95

https://threads-iiith.quora.com/

https://www.hackerrank.com/roba

https://www.linkedin.com/in/changhai-zhou-823ba265

https://github.com/maximizedchang/projecteuler/tree/master/Java%20Files

http://yufeizhao.com/olympiad.html






No comments:

Post a Comment