Author |
Topic: Propose a data structure (Read 1228 times) |
|
pharaoh
Newbie
Gender: 
Posts: 50
|
 |
Propose a data structure
« on: Jan 10th, 2007, 6:44am » |
 Quote  Modify
|
Devise a data structure to contain n elements (in random order) for which complexity of the following operations should be O(1):
Initialization
Insertion of an element
Deletion of an element
Finding a element
Deleting all elements
|
|
 IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Propose a data structure
« Reply #1 on: Jan 10th, 2007, 7:07am » |
Quote Modify
|
That's impossible.
Certainly the last, you can get N elements lost in O(1) time (pretent they don't exist any longer), but you can't properly dispose of them in O(1) time, freeing the associated memory.
Unless N is a constant, obviously.
It might be possible if it would suffice that the datastructure only references/points to the n elements (that would alleviate the freeing problem, as the elements exist outside the datastructure).
But even then, I very much doubt you can do it anything other than on average (hashtable).
|
| « Last Edit: Jan 10th, 2007, 7:07am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Propose a data structure
« Reply #2 on: Jan 10th, 2007, 7:19am » |
Quote Modify
|
I have read it somewhere or heard from someone..this is possible by using 3 arrays, I dont remember the details though. Does the '3 array' ring bells for anyone? I am trying to remember and/or rework this for few of hours now with no luck.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Propose a data structure
« Reply #3 on: Jan 10th, 2007, 10:04am » |
Quote Modify
|
Okay lets forget deletion for time being....
can some one propose O(1) data structure for other operations listed above? Lets think of deletions as initialization with 0.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Propose a data structure
« Reply #4 on: Jan 10th, 2007, 11:02am » |
Quote Modify
|
int A[MAXINT/32];
insert( int i )
{
A[ i/32 ] |= 1 << (i%32);
}
etc.
Also, the binary trie.
|
|
IP Logged |
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Propose a data structure
« Reply #5 on: Jan 10th, 2007, 11:15am » |
Quote Modify
|
I am not sure I understand this fully in the current context.. 
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Propose a data structure
« Reply #6 on: Jan 10th, 2007, 1:34pm » |
Quote Modify
|
It's a bitmap of the entire range. 0 = not in the set; 1= in the set. Insert, delete, and read an element are o(1) in the usual sense. Zeroing the entire array takes time, although it's constant time  .
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Propose a data structure
« Reply #7 on: Jan 11th, 2007, 3:18pm » |
Quote Modify
|
This seems similar, but it looks like you're asking for something else.
If your elements can take on M different values, and an array of length M is feasible, then it should be okay. Otherwise, though, I don't know how you could possibly do a find by value in worst-case constant time.
|
|
IP Logged |
|
|
|
andyhugb
Newbie
Posts: 6
|
|
Re: Propose a data structure
« Reply #8 on: Oct 11th, 2007, 2:06am » |
Quote Modify
|
This problem seems to that, 11.1-4, CLRS
|
|
IP Logged |
|
|
|
GowriKumar
Junior Member
 
Gender:
Posts: 55
|
|
Re: Propose a data structure
« Reply #9 on: Oct 24th, 2007, 10:51am » |
Quote Modify
|
on Jan 10th, 2007, 7:07am, towr wrote:That's impossible.
Certainly the last, you can get N elements lost in O(1) time (pretent they don't exist any longer), but you can't properly dispose of them in O(1) time, freeing the associated memory.
Unless N is a constant, obviously.
It might be possible if it would suffice that the datastructure only references/points to the n elements (that would alleviate the freeing problem, as the elements existhttp://discuss.techinterview.org/default.asp?interview.11.313828.14 outside the datastructure).
But even then, I very much doubt you can do it anything other than on average (hashtable). |
|
The reference paper for the solution is here:
http://citeseer.ist.psu.edu/briggs93efficient.html
An efficient representation of sparse sets.
And a related discussion on this topic:
http://discuss.techinterview.org/default.asp?interview.11.313828.14
|
|
IP Logged |
www.gowrikumar.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Propose a data structure
« Reply #10 on: Oct 24th, 2007, 11:15am » |
Quote Modify
|
An intriguing solution; but as I said, when you delete all elements, you actually just get them lost, they're still in the data-structure until they're overwritten.
Worse yet, if those elements were objects containing pointers to external data that ought to have been cleaned up, you've sprung a memory leak.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print