## Ultimate Technical Interview Question – The Standard Solution

January 24, 2008OK, 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.

very well explained. Good Job !

by J Singh March 20, 2008 at 8:22 pmcool man I was trying to find answer for a long time

by ankit August 14, 2008 at 5:12 pmIf you need more interview questions.

Go throgh these links

Php Interview Qeustions

C Interview Qeustions

Java Interview Qeustions

by Sam June 1, 2009 at 7:34 amhi,

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. 🙂

by Gaurava March 10, 2010 at 6:37 pmwhat FFs aare those..? r the first two T-ffs n 3rd one D-ff?

by beginner June 23, 2011 at 3:36 pm