in DS edited by
2,153 views
23 votes
Suggest a data structure for representing a subset $S$ of integers from $1$ to $n$. Following operations on the set $S$ are to be performed in constant time (independent of cardinality of $S$).$$\begin{array}{cll} \text{i.}& \text{MEMBER $(X):$}  &  \text{Check whether $X$ is in the set $S$ or not} \\ \text{ii.} &
\text{FIND-ONE $(S):$} & \text{If $S$ is not empty, return one element of the set $S$}\\ & & \quad\text{(any arbitrary element will do)} \\ \text{iii.} & \text{ADD $(X):$} & \text{Add integer $X$ to set $S$} \\  \text{ii.} &  \text{DELETE $(X):$} & \text{Delete integer $X$ from $S$}  \end{array}$$Give pictorial examples of your data structure. Give routines for these operations in an English like language. You may assume that the data structure has been suitable initialized. Clearly state your assumptions regarding initialization.
in DS edited by
2.2k views

6 Comments

No need of queue, only Hashtable. Also for delete queue can only from the front so how can it delete any specific integer?
10
Since space is not a problem, we can use direct address hash table.

All operations O(1) time
4
Hash table n stack can also be used rt?
1

@
How FIND_ONE (S) will take O(1) time in DAT?

0

Direct address tables use arrays which are random access data structure, so, the key values (which are also the index of the array) can be easily used to search the records in O(1) time.

0
reshown by
What!  no best answer for this question even if was asked in gate. weird.
0

2 Answers

24 votes

A queue with a hashtable.

Intialize hashtable with $0$.

When inserting $X$ into the queue update $hashtable[X]=0$ to $hashtable[X]=1$.

  1. If $hashtable[X]=1$ then return true.
  2. Return the element at the front or rear of the queue.
  3. Add the element $X$ to the queue at the rear end and update $hashtable[X]=0$ to $hashtable[X]=1$.
  4. Delete the element $X$ from the front end of the queue and update $hashtable[X]=1$ to $hashtable[X]=0$.
edited by

15 Comments

for the last operation dont we need to search the element X in queue
1
@Neal from Queue deletion is only possible from the FRONT only, not from the middle
5
Why do we even need queue.. All operations can be done in constant time using hashtable ryt..?
6
How can we delete X, if X is not there at the front of the queue?

I think an array with size n is enough, where a[n] =n if n is present,otherwise set a[n]=-1
2

@Sourav Basu  

@Tuhin Dutta

In case of array or only a hash table,

how can we ensure part(ii) in constant time, because checking all slots in array or hash table to determine if it is empty or not will take O(n) time.

I think queue + hash table(or array)  both needed.

14
edited by
@Sourav Basu, for deleting we can first do a MEMBER( X ) and then easily delete it which will take const. time.

@VS,  Since any arbitrary element can be returned, so it is possible to do in const. time.

Now for implementation, we can implement the hash table using array or (array + linkedlist)
1
We can have a variable called lastElementAdded, and initially set it to -1, whenever we add an element X, we can update lastElementAdded=X

If lastElementAdded=-1 then array is empty, otherwise return lastElementAdded.
4
Delete X means delete X data.It need not be the front of queue.
1

'Sourav Basu  :- But what if that lastelement is deleted .

2

@ rahul sharma 5

if last element is deleted, then array and queue both will be empty.

@ Sourav Basu

Here delete and add can be done constant time by a queue

and Find-one and member operation can be done in constant time in a hash table

That is why queue and hash table both needed here

right?

1
searching will take O(n) time?
0
we want to insert an element X so it can be done in constant time using queue by adding to the rare of queue but in del(X) we need to delete integer X. Nowhere it is written that X will be in front node?
X can be at any arbitrary position so how point (iv) is true???
we can always make hash[X] = 0 but it will not always be present on front node
2

srestha 

By using queue ,we are restricting to deletion from front only.Delete(X) should delete X,no matter whether it is front of queue or not,X should be deleted.So,using queue it cannot be handled.See my answer below,i tried with DLL

3
@srestha mam . Its not neccessary that when lastelementAdded =-1 then our hastable  is empty. Suppose we inserted 3 elements into hashtable back to back and the elemnts are 1,2,3 now lastelementAdded =3 and now we delete 3 , so we update lastelementAdded to -1 since we don't have info about the rest of the elements in the hash table. So it will not work.
0

I am also having the same doubt that if queue is used with the hashtable then how the last point will satisfy .As we will have two cases here.

CASE 1: if the element X is inserted and it is the only element in the queue then when we perfrom  delete (X) then that element will get deleted in constant time.

CASE 2: if before inserting the element X there are some more elements in the queue then if we want to delete x for that we have to perform so many deletions (as in queue deletion will be done from the front always) . here in worst case it will take O(n).[considering n elements in the queue].

i have doubt in case 2..is this case even possible ? or we should only consider the CASE 1.(initially empty queue)

someone please clarify this !!

0
23 votes

We should use Hashing+ Doubly linked List. Let us say H is my hash table and each entry in hash table will either has NULL or it has the node address in which X is stored.Doubly linked list will have a head pointing to first node.We will do insertion at head always.

(i). MEMBER (X):

Goto H(X) and see if it is NULL or not.If NULL,then return false else true
(ii). FIND-ONE(S): Return front node from linked list.
(iii). ADD (X): Create a new node and store the address in the H(X).And then make this node as a head of linked list
(iv). DELETE (X): Goto H(X),Take the address of the node and set the prev and next nodes pointer in constant time and free the current node by marking H(X) as NULL.

Please let me know if anything is wrong

4 Comments

@rahul

is middle node delete in constant time?

No . right? It will be O(N)
1
Question do not ask to delete the middle node. Finding middle is not possible with hashing in the solution i gave.What question asks is to delete X. Now if you give X as the middle node then it will delete it. Goto H(X),it will have X node address.Change node next and previous neighbors and delete the node.

The problem with the selected answer is that it is using queue and from queue you can delete the intermediate nodes.And it can be the case that X element is lying in the middle of the queue which will not be deleted.
8


Can't we use chaining instead of Doubly Linked List??

0
Why can't we use hashtable denoting presence of elements in array and an array of size n to store the elements ?

Why we even need dynamic memory allocation if size is already known to be n ?
1

Related questions