I will keep this post short. First make sure you take a look at the original puzzle - link here.
The shortest sequence is 6 bits long and is “100110″ (or its inverse “011001″). The smallest amount of bits needed to determine a direction is 5, i.e. any 5 consecutive bits seen by the snail could help him determine the direction home.
Allow me to quote from Martin Gardner’s excellent, excellent book Mathematical Carnival (chapter 17):
When a mathematical puzzle is found to contain a major flaw - when the answer is wrong, when there is no answer, or when, contrary to claims, there is more than one answer or a better answer - the puzzle is said to be "cooked".
From the number of hits, it looks like the last post was quite popular. Therefore, I decided to give the problem some more thought and to try to find more minimal solutions - or as defined in the above quote “to cook this problem”.
My initial hunch was to try and utilize an SR latch somehow. After all it is a memory element for the price of only two gates. I just had a feeling there is someway to do it like that.
I decided to leave the count-to-3 circuitry, cause if we want to do a divide by 3, we somehow have to count…
Here is what I first came up with:
The basic idea is to use the LSB of the counter to set the SR flop and to reset the SR flop with a combination of some states and the low clock.
Here is the timing diagram that corresponds to the circuit above.
But! not everything is bright. The timing diagram is not marked red for nothing.
In an ideal world the propagation time through the bottom NOR gate would be zero. This would mean that exactly when the S pin of the SR latch goes high the R pin of the flop goes low - which means both pins are never high at the same time. Just as a reminder, if both inputs of an SR latch are high, we get a race condition and the outputs can toggle - not something you want on your clock signal. Back to the circuit… In our case, the propagation time through the bottom NOR gate is not zero, and the S pin of the latch will first go high, then - only after some time, the R pin will go low. In other words we will have on overlap time where both R and S pin of the latch will be high.
Looking back at the waveform, it would be nice if we could eliminate the second pulse in each set of two pulses on the R pin of the latch (marked as a * on the waveform). This means we just have to use the pulse which occurs during the “00″ state of the counter.
This is easy enough, since we have to use the “00″ from the counter and the “0″ from the clock itself - this is just the logic for a 3 input NOR gate!
The complete and corrected circuit looks like this now:
And the corresponding waveform below. Notice how the S and R inputs of the SR latch are not overlapping.
OK, so I am getting tons of email with requests to post a solution for this question which was initially posted here.
I am going to post now what I consider the “standard minimal solution”, but some of you have come up with some neat and tricky ways, which I will save for future a post.
The basic insight was to notice that if you are doing a divide by 3 and wanna keep the duty cycle at 50% you have to use the falling edge of the clock as well.
The trick is how to come up with a minimal design, implementing as little as possible flip-flops, logic and guaranteeing glitch free divided clock.
Most solutions that came in, utilized 4 or 5 flip flops plus a lot more logic than I believe is necessary. The solution, which I believe is minimal requires 3 flops - two working on the rising edge of the clock and generating a count-to-3 counter and an additional flop working on the falling edge of the clock.
A count-to-3 counter can be achieved with 2 flops and a NOR or a NAND gate only, as depicted below. These counters are also very robust and do not have a “stuck state”.
The idea now is to use the falling edge of the clock to sample one of the counter bits and generate simply a delayed version of it.
We will then use some more logic (preferably as little as possible) to combine the rising edge bits and falling edge bit in a way that will generate a divide by 3 output (with respect to out incoming clock).
The easiest way (IMHO) to actually solve this, is by drawing the wave forms and simply playing around. Here is what I came up with, which I believe to be the optimal solution for this approach - but you are more than welcome to question me!
and here is also the wave form diagram that describes the operation of the circuit, I guess it is self-explanatory.
One more interesting point about this implementation is that it does not require reset! The circuit will wake up in some state and will arrive a steady state operation that will generate a divide by 3 clock on its own. We discussed some of those techniques in the past when talking about ring counters - link to that post here.
Your company is pretty tight on budget this year and it happens to have only Muxes to design with.
You are required to design a circuit equivalent to the one below, using only Mux structures.
It’s been a while since I posted a nice puzzle and since I know they are so popular, here is a relatively simple one. It was used in job interviews btw (the last line will boost the amount of views for this post…)
A snail leaves his warm house and takes a crawl through the forest leaving behind him on the ground a trail of “0″s and “1″s. He takes a very complicated route crossing his path several times. At one point he becomes tired and disoriented and wishes to go back home. He sees his own path of “0″s and “1″s on the ground which he is about to cross (i.e. not the trail ending in his tail) and wonders whether to follow the trail towards the left or towards the right.
What is the shortest repeating code of “0″s and “1″s he should leave as he crawls in order to easily and deterministically track the way back home? What is the minimum amount of bits he needs to observe (or the sample length of the code)?
Take the clock frequency circuit I posted about here. As I mentioned the XOR gate at the output might cause some duty cycle distortion with some libraries, due to the fact that most XOR gates are not built to be symmetrical with respect to transition delay.
Now, assume your library has a perfectly symmetrical NAND gate. Could you modify the circuit so the XOR will be replaced by a NAND gate and still have a clock frequency at the output (You are of course allowed to add more logic on other parts of the circuit).
If not, give a short explanation why not. If yes send a circuit description/diagram.
This one was solved pretty quickly. Basically I was trying to trick you. The idea was to try to create the impression an infinite amount of memory is necessary to hold all the 0–>1 and 1–>0 transitions. In practice there cannot be 2 consecutive 0–>1 transitions (or vice versa) since if the input goes from 0 to 1 before the next 0–>1 transition it must change to a 0 and thus have a 1–>0 transition!
The FSM can have only three states: “exactly one more 0–>1″, “equal amount of 0–>1 and 1–>0″ or “exactly one more 1–>0″.
It’s time for puzzle #7.
An FSM receives an endless stream of “0″s and “1″s. The stream can not be assumed to have certain properties like randomness, transition density or the like.
Is it possible to build a state machine, which at any given moment outputs whether there were more 0–>1 or 1–>0 transitions so far?
If yes, describe briefly the FSM. If no, give a short proof.
I had countless interviews, with many different companies, large corporations and start ups. For some reason in almost all interviews, which were done in Israel, a single question popped up more often than others (maybe it is an Israeli High-Tech thing…).
Design a clock divide-by-3 circuit with 50% duty cycle
The solution should be easy enough even for a beginner designer. Since this is such a popular question, and since I am getting a decent amount of readers lately, I thought why not make a small challenge - try to find a solution to this problem with minimum hardware.
Please send me your solutions by email - can be found on the about me page.
Here are the block diagrams for the solution of the MinMax problem.
You are currently browsing the archives for the Interview Questions category.
