325 views
0 votes
0 votes
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct address dictionary on a huge array. Each stored object should use $\mathcal{O}(1)$ space; the operations $SEARCH$, $INSERT,$ and $DELETE$ should take $\mathcal{O}(1)$ time each; and initializing the data structure should take $\mathcal{O}(1)$ time. (Hint: Use an additional array, treated somewhat like a stack whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
3
akash.dinkar12 asked Apr 4, 2019
846 views
Suppose that a dynamic set $S$ is represented by a direct-address table $T$ of length $m$. Describe a procedure that finds the maximum element of $S$. What is the worst-c...
0 votes
0 votes
0 answers
4