The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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}{ll} \text{i. MEMBER $(X)$:}  &  \text{Check whether $X$ is in the set $S$ or not} \\
\text{ii. 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. ADD $(X)$:} & \text{Add integer $X$ to set $S$} \\
\text{iv. 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.
asked in DS by Veteran (52k points)
edited by | 834 views
No need of queue, only Hashtable. Also for delete queue can only from the front so how can it delete any specific integer?
Since space is not a problem, we can use direct address hash table.

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

2 Answers

+13 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$.
answered by Boss (33.8k points)
edited by
for the last operation dont we need to search the element X in queue
@Neal from Queue deletion is only possible from the FRONT only, not from the middle
Why do we even need queue.. All operations can be done in constant time using hashtable ryt..?
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

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

@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)
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.
Delete X means delete X data.It need not be the front of queue.

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


@ 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


searching will take O(n) time?
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


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

+8 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

answered by Boss (24.2k points)

is middle node delete in constant time?

No . right? It will be O(N)
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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,120 answers
71,034 users