Algorithm Question:

Please do not write a real program.

The answer should be an explaination of your algorithm or pseudocode. Try to answer clearly and concisely. Thank you very much.

Question:

Say that elements have two keys. key 1 is not unique, namely, there are may be many elements with the same key 1 . But each element also has key 2 so that the second keys are pairwise disjoint. The keys are numbers.

Show how to implement the following operations: F ind(S, key 1 (x), key 2 (x)) that finds the unique element with these two keys. Also, implement Insert(S, k 1 , k 2 ) that adds into S an elements with first key k 1 and second key k 2 . Finally the data structure should be able to do Delete(S, k 1 ) with k 1 some valid first key. This means that you want to remove all whose first key is k 1 .

Remark: It is possible to do all the above so that every operation will take much less than (n).