edited by
3,723 views
27 votes
27 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.
edited by

2 Answers

33 votes
33 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

27 votes
27 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

Related questions

28 votes
28 votes
5 answers
1
Kathleen asked Sep 12, 2014
8,843 views
A $2-3$ tree is such thatAll internal nodes have either $2$ or $3$ childrenAll paths from root to the leaves have the same lengthThe number of internal nodes of a $2-3$ t...
26 votes
26 votes
3 answers
4
go_editor asked Apr 24, 2016
3,564 views
Suppose we have a database consisting of the following three relations:$$\begin{array}{|c|c|} \hline \text {FREQUENTS} & \text {(CUSTOMER, HOTEL)} \\\hline \text {SERVES}...