September 30, 2015

We have talked a lot about many design principles. If you think you are well-prepared, let me give you a real interview question in this article. I was asked to solve this question during my interview at Cisco, and I was able to answer it. You can use it as a good practice.

Question: Given a single-bit streaming input, how do we report (mod 5) results of the stream? An example is shown in the following table:

Take a try before you read the solution. I will now introduce how I solved this problem during the interview.

First of all, let us denote the previous stream as X and the current stream as Y. Appending a binary digit "0" to X means Y=2X, while appending a binary digit "1" means Y=2X+1. This suggests that there might be a relation for X (mod 5) and Y (mod 5). This is actually the key to this problem: you need to find the output based on a previous output!

Second, we should also notice the possible outputs are only 0, 1, 2, 3, and 4. We are now looking for a mapping from the previous output {0, 1, 2, 3, 4} to the new output {0, 1, 2, 3, 4}. The mapping depends on the input binary digit:

• If the binary input is "0", Y=2X, the mapping in decimal is: {0, 1, 2, 3, 4} → {0, 2, 4, 1, 3}. This mapping means, if X (mod 5) = 0/1/2/3/4, then Y (mod 5) = 0/2/4/1/3.

• If the binary input is "1", Y=2X+1, the mapping in decimal is: {0, 1, 2, 3, 4} → {1, 3, 0, 2, 4}.

Isn't the corresponding architecture obvious? We just use two lookup tables, each consisting of 5 slots (with 3 address bits). Depending on the input binary digits, we access one of the two tables; when we access the table, we use the previous output as the address bits. This solution can be easily verified.