Gray Code Generator

I suppose I could finally talk about it!  I had my Google interview last July.  Was an embarassement (and to myself too).  This was the final question in my interview (with none other than Lars Rassmussen).  The question was the typical one – “there is a room from which at any time only one person can either enter or exit the room – and not at the same time.  So how would you model all the states the room can be in without repetitions”.

“Simple, isnt that just Graycode?” I blurt out.  At which point I was asked to write an algorithm to actually generate all graycodes for a n-bit string.   And this was where I floundered.  Mind you I had just been through 3 and a half hours and writing an algorithm was the last thing on my mind.  It wasnt that I hadnt known how to do it, I just blanked out then then and there – half an hour close to the finish of the interview and I had lost focus.  Stupid stupid me.

Anyway I just got back from a swim and for some reason the demon of the failed interview reared its ugly head and so I figured Id attempt it here (atleast to get some closure, sob sob).  Here goes.

Here are possible gray codes for N = 1, 2, 3 and 4:

N = 1 N = 2 N = 3 N = 4
0 00 000 0000
1 01 001 0001
11 011 0011
10 010 0010
110 0110
111 0111
101 0101
100 0100
1100
1101
1111
1110
1010
1011
1001
1000

Anyway this is only one combination. Any bit could be changed in generating the sequence. The pattern here is that the first half and the second half of the code are “kind of” the same but with the first bit being 0 and 1 respectively and the rest of the bits being reverse of each other.

ie with N = 2,
first half = 00 and 01
second half = 11 and 10

So a simple algorithm would be (in pseudo-haskell):

gc 1, reverse = ["1", "0"] if reverse, else ["0", "1"]
gc N, True =
      ["1" + x for x in gc(N - 1, True) ] ++ ["0" + x for x in gc(N - 1, False) ]
gc N, False =
      ["0" + x for x in gc(N - 1, False) ] ++ ["1" + x for x in gc(N - 1, True) ]

Problem with the above is the storage required in the recursion to store the graycodes for N – 1 (and that too twice). So in python we could avoid this with generators like:

def graycode(numbits, reverse = False):
    if numbits = 1:
        if reverse:
            yield "1"
            yield "0"
        else:
            yield "0"
            yield "1"
    else:
        if reverse:
            # all the "1"s start first
            gcprev = graycode(numbits - 1, True)
            for code in gcprev:
                yield "1" + code

            gcprev = graycode(numbits - 1, False)
            for code in gcprev:
                yield "0" + code
        else:
            # all the "0" start first
            gcprev = graycode(numbits - 1, False)
            for code in gcprev:
                yield "0" + code

            gcprev = graycode(numbits - 1, True)
            for code in gcprev:
                yield "1" + code

and finally an auxilliary function to print out the codes:

def gcgen(numbits, reverse = False):
    for codes in graycode(numbits, reverse):
        print "Code: ", codes

And that was 15 minutes of thinking. Damn it why didnt it come to me last year? Could have been the difference between a googler and foogler!!! Unless ofcourse it didnt really matter and they simply thought I was just a dick@#$D!!!

Advertisements

3 thoughts on “Gray Code Generator

    • ha ha i know mate… well got a free drink from them anyway :D:D so wasnt a total waste of time … hmm just thinking… was sydj on at that time? cant remember… but yeah would have been good for the venues!!

      whats goin on with you these days mate? hows the startup goin?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s