gray code

April 21, 2016

Work on algorithm called "gray code".

1) Given two words, find if second word is the round rotation of first word.
For example: abc, cab
return 1
since cab is round rotation of abc

Example2: ab, aa
return -1
since aa is not round rotation for aa

2) Given two hexadecimal numbers find if they can be consecutive in gray code
For example: 10001000, 10001001
return 1
since they are successive in gray code

Example2: 10001000, 10011001
return -1
since they are not successive in gray code.

problem statement source:

http://www.geeksforgeeks.org/amazon-interview-experience-set-137-assessment-test-sde/

Read the blog:
http://www.cnblogs.com/lautsie/p/3909927.html

choose some questions to work on, practice!
http://www.cnblogs.com/lautsie/tag/hackerrank/

try this one - see if the content is related to gray code
https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences

Leetcode gray code:
https://leetcode.com/problems/gray-code/

Two solutions:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-gray-code.html

http://fisherlei.blogspot.ca/2012/12/leetcode-gray-code.html

Question and answer time:
Q: Julia, tell me what you know about gray code. 
Answer:
1. Gray code is very specific for the one to build up using previous results. 
    To extend, append all the number in the set in reverse order, with number adding 2^n, n is the number in binary format length. 

2. Let us work on some coding:
n = 0: 0
n = 1: 0, 1

n = 2: 00, 01, 11, 10  (0, 1, 3, 2)

n = 3: 000, 001, 011, 010, 110, 111, 101, 100 (0, 1, 3, 2, 6, 7, 5, 4)

C++: 

 vector<int> grayCode(int n) {
        vector<int> greySeq;
        if(n<0) return greySeq; // julia's comment:
        greySeq.push_back(0);   // first, start from n=0, 0
        int inc = 1;            // incremental value is 1, 2^n, n =0;  
        for(int i=1; i<=n; i++) { // loop starting value: 1
            for(int j=greySeq.size()-1; j>=0; j--) // reverse order iteration
                greySeq.push_back(greySeq[j]+inc); // add incremental value for each one
            inc <<= 1;  // inc = inc *2  or inc <<=1; 
        }
        return