Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

Interview Questions: How to find same contents in a FIFO

Status
Not open for further replies.
S

spartanthewarrior

Full Member level 2
Full Member level 2
Joined
Jun 13, 2007
Messages
122
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,296
Activity points
2,142
Hi All,

I have been asked a question in Interview.

I am having a FIFO which can store 10000 entries. All the entries stored are different except two which are same. How can I find out which two entries are same.

Next Question: How you will figure out which is the greatest one.
 

I have to search for 20000 entries in a FIFO.

Is there a shortcut in algorithm.

---------- Post added at 19:43 ---------- Previous post was at 19:41 ----------

Sorry 10000 entries, I have to look for and need to compare each one. Will be cumbersome.
 

spartanthewarrior said:
I have to search for 20000 entries in a FIFO.

Is there a shortcut in algorithm.

---------- Post added at 19:43 ---------- Previous post was at 19:41 ----------

Sorry 10000 entries, I have to look for and need to compare each one. Will be cumbersome.
Click to expand...

you can't search inside FIFO unless FIFO is designed accordingly which is very unlikely. you have to read and compare.
 

Ok, it is true we can't search inside FIFO. But in order to find out the 2 identical entries in FIFO, we have to read out the entire content of the FIFO before we do the search. Let's say the first entry and the last entry are the identical pair we are looking for. It is obvious that we have to buffer all the entries.

If the question changes to "only 2 entries are NOT the same with the rest of the entries", then the buffer size will be much smaller (5 entry buffer should be enough).

Any better algorithm?
 
This is something similar to like Databases we have

You have to search for name of 2 person, out of 20000 entries and only these two have same name.

Algo is not coming in to my mind.
 

please find the attached image.. comments are welcome
 
Hi OTIS,

Can you please tell me from where did you find this algorithm.
 

:) I did not get it from anywhere I made it myself. I used visio to draw it.
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top