Archive for the ‘Interview Questions’ Category

h1

Interview Question – BCD Digit, Multiplied by 5

December 21, 2008

A while back, someone sent me the interview question I am about to describe, asking for help. I think it serves a very good example of observing patterns and not rushing into conclusions.
I will immediately post the answer after describing the problem. However, I urge you to try and solve it on your own and see what you came up with. On we go with the question…

Design a circuit with minimum logic that receives a single digit, coded BCD (4 wires) and as an output gives you the result multiplied by 5 – also BCD coded (8 wires).

So, I hope you got a solution ready at hand and you didn’t cheat 😉 .

Let’s first make some order and present the input and required outputs in a table (always a good habit).

Looking for some patterns we can see that we actually don’t need any logic at all to solve this problem!!

You will be amazed how many people get stuck with a certain solution and believe it is the minimal one. Especially when the outcome is one or two single gates. When you tell them it can be done with less, they will easily find the solution. IMHO there is nothing really clever or sophisticated about this problem, but it demonstrates beautifully how it is sometimes hard for us to escape our initial ideas and approaches about a problem.

Coming to think of it, this post was more about psychology and problem solving than digital design – please forgive…

Advertisements
h1

Puzzle #13 – A Google Interview Question

July 25, 2008

The following puzzle was given to me by a friend who claimed it was given in a Google interview. If you can confirm or debunk this claim just post a comment – until then I am sure the headline will generate some traffic 🙂 .

The original question as it was given to me was:
Given an array with 2n+1 integer elements, n elements appear twice in arbitrary places in the array and a single integer appears only once somewhere inside. Find the lonely integer with O(n) operations and O(1) extra memory.

Now let’s transform this to a more digital-design-like problem. Given an SRAM of depth N and some arbitrary width K, which is filled with 2n+1 non zero values (for completeness – the rest of the 2^N – (2n+1) are all zeroes). n elements appear twice – in different places in the SRAM, while a single value appears only once.

Design a circuit with the minimum amount of hardware to find the value which appears only once.

h1

Puzzle #12 – Count and Add in Base -2

June 3, 2008

It has really been a long time since a new puzzle appeared on the blog.
This one is a neat little puzzle that was pretty popular as an interview question. I tried to expand on it a bit, so let’s see where this goes.

The basic idea is: can you count in base -2? There is no typo here – it is minus 2. So far the original puzzle, now my small contribution…
Once you realize how to do this, try to build a logical circuit that performs addition directly (i.e. no conversions) in base -2.

Good luck!

h1

Puzzle #10 – Mux Logic – Solution

May 29, 2008

Puzzle #10 – Mux Logic, still didn’t get an official solution so here goes.
If you are not familiar with the puzzle itself, as usual I ask you to follow the link and reread its description.

To solve this puzzle let’s first take a look at the combinational parts of the circuits. If we could build an OR gate and a NOT gate from MUXes it would be enough to make any combinational circuit we wish (this is because OR and NOT are a complete logic system, same as AND and NOT, or just NOR or NAND).
The figure below shows how to build NOT, OR and AND gates from a single MUX.

Next in line we have to somehow build the flipflop in the circuit. We could build a latch from a single MUX quite easily if we feedback the output to one of the MUX inputs. The figure below will make everything clearer. Notice that we could easily construct a latch which is transparent while its clock input is high or low by just changing the input the feedback wire is connected to.
We then use two latches, one transparent low the other transparent high to construct a flipflop.

As a final note, some use the versatility of the MUX structure to their advantage by spreading MUX structures as spare cells. Later if an ECO is needed one can build combinational as well as sequential elements just from those single MUX structures.

h1

Puzzle #9 – The Snail – Solution

March 27, 2008

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.

h1

Ultimate Technical Interview Question – Take 2

January 31, 2008

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:

div_by_3_sr_1_cir.png

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.

div_by_3_sr_1_wave.png

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.

div_by_3_sr_1_prob.png

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:

div_by_3_sr_2_cir.png

And the corresponding waveform below. Notice how the S and R inputs of the SR latch are not overlapping.

div_by_3_sr_2_wave.png

h1

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

count_to_3.png

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!

clk_div_by_3.png

and here is also the wave form diagram that describes the operation of the circuit, I guess it is self-explanatory.

clk_div_by_3_wave.png

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.