wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Propose a data structure
        
(Message started by: pharaoh on Jan 10^th, 2007, 6:44am)

Title: Propose a data structure
Post by pharaoh on Jan 10^th, 2007, 6:44am

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

Title: Re: Propose a data structure
Post by towr on Jan 10^th, 2007, 7:07am

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

Title: Re: Propose a data structure
Post by pharaoh on Jan 10^th, 2007, 7:19am

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.

Title: Re: Propose a data structure
Post by pharaoh on Jan 10^th, 2007, 10:04am

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.

Title: Re: Propose a data structure
Post by KWillets on Jan 10^th, 2007, 11:02am

int A[MAXINT/32];

insert( int i )
{
A[ i/32 ] |= 1 << (i%32);
}

etc.

Also, the binary trie.

Title: Re: Propose a data structure
Post by pharaoh on Jan 10^th, 2007, 11:15am

I am not sure I understand this fully in the current context.. ???

Title: Re: Propose a data structure
Post by KWillets on Jan 10^th, 2007, 1:34pm

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 :-).

Title: Re: Propose a data structure
Post by Eigenray on Jan 11^th, 2007, 3:18pm

[link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1071733019]This[/link] 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.

Title: Re: Propose a data structure
Post by andyhugb on Oct 11^th, 2007, 2:06am

This problem seems to that, 11.1-4, CLRS

Title: Re: Propose a data structure
Post by gowrikumar on Oct 24^th, 2007, 10:51am

on 01/10/07 at 07:07:04, 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

Title: Re: Propose a data structure
Post by towr on Oct 24^th, 2007, 11:15am

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.