A Question from CLRS book:

(CLRS 11.1-4) 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 O(1) space; the operations SEARCH, INSERT and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time. (Hint: Use an additional 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.)

In SEARCH(K) - We can go to directly that Kth index, But we not sure about that garbage, We may access that garbage location and have Some Random behaviour or any other exception. That's why we using Stack, that's fine.

We are using Stack for validation of a slot in huge array, In most of the solution we are only storing the index of each other as value (i.e. index of Stack in a slot of huge array and index of that slot in Stack). This is just for validation, But where is that object with satellite data will go I mean how we can point that out via pointer? Hope you got my point.

Many thanks in Advance!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.