first repeated element in an array???????

Go down

first repeated element in an array???????

Post  ish_mnnit on Wed Aug 13, 2008 11:41 am

give an algo in o(n) to find first repeated element in an array?
e.g.{1,2,3,4,2,1,5,6}
output=2

ish_mnnit

Posts : 4
Join date : 2008-08-10

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  Beagle on Sat Aug 16, 2008 5:45 am

giving it a try....

You can use Hash Tables.

in O(1) it will search the element present in the hash table and the moment any of it's entries list is appended for the first time you report that element as the first repeated element.

Beagle

Posts : 9
Join date : 2008-08-11

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  ankurgutpa on Sat Aug 16, 2008 6:03 am

no idea about hash table Crying or Very sad
plz elaborate a li'l cheers
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 30
Location : Tandon 72

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  Beagle on Sat Aug 16, 2008 6:06 am

yaar u can always search for hash tables on wikipedia, it's the idea that i have provided. and i think my idea is correct.

Beagle

Posts : 9
Join date : 2008-08-11

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  ankurgutpa on Sat Aug 16, 2008 6:14 am

what about implementation of so called HASH TABLES??
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 30
Location : Tandon 72

View user profile

Back to top Go down

^^^

Post  Beagle on Sat Aug 16, 2008 8:36 am

not getting your point.. do you want me to implement the hash table??

Beagle

Posts : 9
Join date : 2008-08-11

View user profile

Back to top Go down

@Beagle

Post  shivang on Sat Aug 16, 2008 11:00 pm

Yaar implement kaise karoge ye batao.....
just dont giv the hint...... Question Shocked
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  Beagle on Sun Aug 17, 2008 8:56 am

ok giving it a try...

From the domain of numbers specified, The hash table will be created(I don't exactly remember the process of creating a hash table) but it's from the domain of inputs from which it takes it's values.

Now having created your hash table, the values will be searched and inserted in O(1) time complexity.

Now the case arise that domain has repeated values(don't consider the domain of sets) so entering an existing value would create a problem(as it already exists), To overcome this problem a link is created to the value to be inserted like

1
2-2
3
4
5-5-5
and so on....
so when a link is created for the hash table for all the values,(that existed prior to the value that is being currently added) flag is raised denoting that a link has been created. The moment this is done for any value, report that to be as the first repeated element.

Correct me if wrong..... cheers

Beagle

Posts : 9
Join date : 2008-08-11

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  Dee2306 on Wed Aug 20, 2008 2:50 am

Do U Know How MAP works in C++.
It must be using Some Hash Function ...
You Can Do It .. this way too..
But the point is .. Check Out If It searches in O(1) time.. Arrow
avatar
Dee2306

Posts : 7
Join date : 2008-08-12
Age : 30

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  Beagle on Thu Aug 21, 2008 2:56 am

I can't say about map... but for hash tables i m pretty much sure that it searches in O(1) time, if the element is present only once, and O(n) [n is the number of times the element is repeated] otherwise.

Beagle

Posts : 9
Join date : 2008-08-11

View user profile

Back to top Go down

Re: first repeated element in an array???????

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum