trilogy

These are from Trilogy Interview.

(i)Given Finite numbers of sets say S1 , S2 , S3 .... SM . Design an algorithm Find the element such that , it is a member of largest number of sets


(ii)Design a data structure for which Insertion , Deletion and Searching Takes O(1) time . The Data Structure must be such that it holds at the most N Keys. It must throw exception FUll() when there is no more space .(Dont assume anything about type,values... etc of keys )




well my idea is to use array indexed from [Smallest element...........Largest element]and then count the frequency of each elements . And then we can element with Larget frequency .

Largest and Smallest are the Largest and Smallest elements of the set X = { S1 Union S2 Union S3 U .... SM } , The Time complexity is O(N) , N=|S1|+|S2|+|S3|.....|SM| . But this idea is not good , if the numbers are not uniformly distributed in the range smallest to Larget , or if number of elements are less compared to the size of the range.


Another Idea is to use BST ( or AVL Tree )with a Frequency Counter for each node. which is O(NlogN)

Are there any Better Solutions... ? I Guess there are.