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|
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!!!