Google Interview Question

This was a question for a hardware engineer interview, I didn't go for the interview but someone I know did.

So here's the question, you have an infinite bitstream coming at you one bit at a time, everytime a new bit arrives you have to decide whether the current bit stream you already have is a multiple of three or not.

For example, first bit is '1', well it's not a multiple of three, next is another '1', so what you have so far is '11' and it is 3 so it's a multiple of three, say next you get '0' so you have '011' and again it's still a multiple of three, if the next one is '1' you'll have '1011' which is eleven and it is not a multiple of three and so on.

The thing with this problem is that you can't use brute force because at one time the bitstream becomes very long, remember that it is an infinite bitstream, you won't have enough bits to do arithmetic, everything will overflow under brute force.

The way I'd solve this problem is to use what is called congruence in mathematics, I only know this since I've recently dabbled in number theory for fun.

A congruence is slightly different from modulo, in modulo you only get a remainder of a number, for example, 4 modulo 3 is 1 but in congruence what we have is

a = b (mod c)

I should've used an equivalent sign rather than an equal sign but I don't know how to do it in this blog so equal sign it is.

What the above means is a = b + cx, where a,b,c,x are all integers, or another way is (a - b) = cx, the difference between a and b is a multiple of c.

This means that 4 = 1 (mod 3) but it's also true that 4 = 7 (mod 3). For our problem what we need is

2 = -1 (mod 3)

This is because a bit stream is just a sum of various powers of 2, i.e.,

a string a bits =  sum of 2^m = sum of (-1)^m (mod 3) where m runs from 0 till the length of the stream - 1.

This means that if m is odd then 2^m is -1 and if m is even 2^m is +1 (mod 3).

Thus to solve this problem you'll just need a variable that will toggle from positive to negative and vice versa every time a new bit arrives and you'll multiply this variable with the arriving bit, you then add this result to the current sum. If the sum is zero (mod 3) then you'll know that it is a multiple of three otherwise it is not.

This sum will not overflow because you'll just care about mod 3, let's see how this all works, say first bit is '1' followed by '0', and '1', and another '1'

Initialization: sum = 0 sign = +1
First bit: sum = sum + 1 x (+1)
                      = 0 + 1
                      = 1 (mod 3)
               sign = -1
Second bit: sum = sum + 0 x (-1)
                           = 1 (mod 3)
                   sign = +1
Third bit: sum = sum + 1 x (+1)
                        = 1 + 1
                        = 2
                        = -1 (mod 3)
                sign  = -1
Fourth bit: sum = sum + 1 x (-1)
                          = -1 - 1
                          = -2
                          = 1 (mod 3)
                  sign = +1

In our example above the bitstream we have was never a multiple of three, i.e. what we have above in decimal was 1, 1, 5, 13 and therefore the sum was never zero, if the next two bits are '0' and '1' we will have a multiple of three because then we'll have 45 in decimal and the method above will produce a sum of 0.

I think this is quite an unfair question unless you know congruence although this was definitely a Google Interview Question that I can answer with confidence, too bad I wasn't the interviewee :)