## Ultimate Technical Interview Question – The Standard Solution

January 24, 2008

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.

1. very well explained. Good Job !

2. cool man I was trying to find answer for a long time

3. If you need more interview questions.
Php Interview Qeustions

C Interview Qeustions

Java Interview Qeustions

4. hi,

The solution is not seems to be optimal,

u don’t need 3rd flop at all, Take clk, cntr_msb and cntr_lsb as input and design a logic. 🙂

5. what FFs aare those..? r the first two T-ffs n 3rd one D-ff?