interview questions

G

googler

Guest
Hello folks,

I am preparing for interviews for ASIC/logic design engineer position.
I came across a few questions for which I couldn't find a solution.

1. Using 3 registers and two two-bit full adders, how to count to 9
given that one clock cycle is only enough the delay of a full adder.

2. Given memory with 2n+1 values with n elements appearing twice in
different areas of the memory and 1 value appearing once. Design low
delay circuit that finds this 1 value.

If you know of other interesting/difficult interview questions, please
share.

Thanks.
 
googler <pinaki_m77@yahoo.com> wrote:

I am preparing for interviews for ASIC/logic design engineer position.
I came across a few questions for which I couldn't find a solution.

1. Using 3 registers and two two-bit full adders, how to count to 9
given that one clock cycle is only enough the delay of a full adder.
So you want a state machine with 10 states? (It doesn't say what
code to count to 9 in.) A two-bit full adder and register easily
makes a four-state state machine. Two should be able to do 16
states, so the problem is to find one with only 10 states.

2. Given memory with 2n+1 values with n elements appearing twice in
different areas of the memory and 1 value appearing once. Design low
delay circuit that finds this 1 value.
As AT&T has patented this operation, I can't tell you about it.

-- glen
 
On Sep 12, 4:08 am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
googler <pinaki_...@yahoo.com> wrote:
I am preparing for interviews for ASIC/logic design engineer position.
I came across a few questions for which I couldn't find a solution.
1. Using 3 registers and two two-bit full adders, how to count to 9
given that one clock cycle is only enough the delay of a full adder.

So you want a state machine with 10 states?  (It doesn't say what
code to count to 9 in.)   A two-bit full adder and register easily
makes a four-state state machine.  Two should be able to do 16
states, so the problem is to find one with only 10 states.

2. Given memory with 2n+1 values with n elements appearing twice in
different areas of the memory and 1 value appearing once. Design low
delay circuit that finds this 1 value.

As AT&T has patented this operation, I can't tell you about it.

-- glen

1. Sorry, I don't get it. You mean a 2-bit full adder and one register
(1-bit wide) can be used to make a 4-state state machine? I thought we
need two registers for that.

2. Does having a patent prevent others from knowing about it? I
thought a patent only prevents the use of the idea..
 
googler <pinaki_m77@yahoo.com> wrote:

2. Given memory with 2n+1 values with n elements appearing twice in
different areas of the memory and 1 value appearing once. Design low
delay circuit that finds this 1 value.
(snip, then I wrote)

As AT&T has patented this operation, I can't tell you about it.

2. Does having a patent prevent others from knowing about it? I
thought a patent only prevents the use of the idea..
OK, it is patent 4197590.

-- glen
 
On Sep 12, 11:34 am, glen herrmannsfeldt <g...@ugcs.caltech.edu>
wrote:
googler <pinaki_...@yahoo.com> wrote:
2. Given memory with 2n+1 values with n elements appearing twice in
different areas of the memory and 1 value appearing once. Design low
delay circuit that finds this 1 value.

(snip, then I wrote)

As AT&T has patented this operation, I can't tell you about it.
2. Does having a patent prevent others from knowing about it? I
thought a patent only prevents the use of the idea..

OK, it is patent 4197590.

-- glen

Not sure if the patent mentions about it (couldn't find it in the 26
pages, maybe I missed it there).

Here is my solution, perhaps not the best one. If anybody has better
ideas, please feel free to suggest.

Assuming single port memory. It uses two pointers. The first pointer
PTR1 points to the current address (starting with 0) while the second
pointer PTR2 traverses the memory below the current address. If the
data pointed to by PTR2 matches that of PTR1, we swap mem[PTR2] and
mem[PTR1+1], then we increment PTR1 by 2 and repeat the process.
Otherwise, if no data matches with mem[PTR1], then the word at PTR1 is
the one we are looking for.
 
googler <pinaki_m77@yahoo.com> wrote:

(snip)
Here is my solution, perhaps not the best one. If anybody has better
ideas, please feel free to suggest.

Assuming single port memory. It uses two pointers. The first pointer
PTR1 points to the current address (starting with 0) while the second
pointer PTR2 traverses the memory below the current address. If the
data pointed to by PTR2 matches that of PTR1, we swap mem[PTR2] and
mem[PTR1+1], then we increment PTR1 by 2 and repeat the process.
Otherwise, if no data matches with mem[PTR1], then the word at PTR1 is
the one we are looking for.
Consider adding up all the numbers, and testing the sum for even or odd.
An odd sum means that the singleton is odd. That is a hint.

-- glen
 
googler <pinaki_m77@yahoo.com> writes:

Here is my solution, perhaps not the best one. If anybody has better
ideas, please feel free to suggest.
Funny nick that you gave yourself. I basically copied your original
question into a Google search and found answers within two minutes.

Regards,
Marcus

--
note that "property" can also be used as syntactic sugar to reference
a property, breaking the clean design of verilog; [...]

(seen on http://www.veripool.com/verilog-mode_news.html)
 

Welcome to EDABoard.com

Sponsor

Back
Top