Technical interviews for Software Engineers are notorious for obscure questions. The goal for the interviewer is to observe how you approach a problem and to try to understand your thought process. The better you can convey your thought process in words while coming up with a correct solution to the problem, the better your chances are at scoring a follow-up interview.

Here is one question that I recently came across while interviewing for a Silicon Valley company. It goes something like this:

At first glance, this sounds a bit daunting. All this talk about lights and neighbors etc. But, let’s take a minute to break this down. To simplify the problem, let’s ignore the whole “state of the lights on day n” thing and let’s figure out how to determine the lights for tomorrow given the state today. Also, lets figure out how we can best model this problem.

So, we know that we want to take an array which represents the state of the lights on a given day. Since each light can either be only on or off, it makes sense that we just use an array of 1s and 0s for the respective states. So, our input array might look something like this:

state = [0, 1, 0, 1, 0, 1, 1, 0]

In this scenario, the lights are off, on, off, on, off, on, on, off. Intuitively we can look at this and see exactly which lights should be on the next day. But how can we do this with code?

The naive approach would be to do some sort of loop and to determine whether light i should be on, look at both i – 1 and i + 1. That approach would work but we would need special handling for the 0th and 7th positions since there is no i – 1 for the former and no i + 1 neighbor for the latter. That code might look something like this:

tomorrows_lights = [0, 0, 0, 0, 0, 0, 0, 0]

# Handle special cases. Only on if neighbor is off
tomorrows_lights[0] = int(not state[1])
tomorrows_lights[1] = int(not state[6])

i = 1
while i < 8:
    tomorrows_lights[i] = int(state[i - 1] == state[i + 1])
    i += 1

This isn’t too atrocious. I’m taking advantage of Python falsy values to populate either a 1 or a 0 in the appropriate places. While this is functional, I’d argue that there is a better solution.

Since we are dealing with 1s and 0s here, the use of bitwise operators is an option that can be explored. So let’s convert the input array into a bitwise representation.

lights = functools.reduce(lambda a, b: (a << 1) | b, state)

This one liner effectively converts the input array into an 8 bit integer. For each item in the state array, the value is shifted one position to the left and appends either a 0 or a 1 from the state array. So, our input array of [0, 1, 0, 1, 0, 1, 1, 0] becomes 86 or 01010110.

Now we can use bitwise operators to determine if both neighbors are on quite easily. If we perform a left shift and a right shift and then perform a bitwise AND operation of the shifts, a 1 will only show up if both neighbors had their lights on. For example,

left_shift = lights << 1    #10101100
right_shift = lights >> 1.  #00101011
tomorrows_lights = left_shift & right_shift #00101000

This handles the case of both neighbors being in an initial state of ON. But how can we determine if both neighbors were OFF? Well, pretty easily actually. If both neighbors were OFF, then the left and right shifts will both have 0s for the same bit. So, lets take a bitwise OR of the two and see what that yields:

left_shift | right_shift # 10101111

Notice that the lights that should come ON are in the two places where there are zeroes. To get this to the proper state then, we could perform an XOR with the mask 0xFF

(left_shift | right_shift) ^ 0xFF # 01010000 

By combining this with the previous AND operation, we obtain the solution for tomorrow’s lights. We can combine these operations onto a single line to make the code a bit more concise.

left_shift = lights << 1    #10101100
right_shift = lights >> 1.  #00101011
tomorrows_lights = (left_shift & right_shift) | ((left_shift | right_shift) ^ 0xFF) & 0xFF

Notice that to ensure that only the bottom 8 bits are set, we perform an AND with 0xFF.

Ok, so these 3 lines of code do all of the heavy lifting. In order to generalize this and define a function that can find the light sequence for some arbitrary day in the future, we will stick this bit in a loop and perform this bit manipulation for each day.

def get_light_sequence_on_day_n(n, state):
    lights = functools.reduce(lambda a, b: (a << 1) | b, state)
    while n > 0:
        left_shift = lights << 1    #10101100
        right_shift = lights >> 1.  #00101011
        lights = (left_shift & right_shift) | ((left_shift | right_shift) ^ 0xFF) & 0xFF
        n -= 1
    return lights

Our function is close to finished but the return value right now is a number and the requirements ask for an array representing the state of the lights. To do so, we need to create an inverse operation to the reduce statement on the first line of this function. The solution I came up with for this is to first format the return value as a binary string using Python’s string format method, iterate over that string using map, and then return the resulting list. That looks like this:

list(map(lambda n: int(n), "{0:08b}".format(light_sequence)))

So, the finished function looks in only 8 lines long, fairly easy to understand, and is a bit more elegant than using for loops and handling edge cases.

def get_light_sequence_on_day_n(n, state):
    lights = functools.reduce(lambda a, b: (a << 1) | b, state)
    while n > 0:
        left_shift = lights << 1    #10101100
        right_shift = lights >> 1.  #00101011
        lights = (left_shift & right_shift) | ((left_shift | right_shift) ^ 0xFF) & 0xFF
        n -= 1
    return list(map(lambda n: int(n), "{0:08b}".format(light_sequence)))

Check out the full source on my GitHub. If you have any suggestions, leave them in the comments. Thanks for reading and stay tuned for more.