i guess you dont require first hash at all.............create a hash map that maps a letter to a set of keys now once you have all your sets you can just compare the input set with your the formed sets.......
On Tue, Nov 16, 2010 at 8:51 AM, Gene <[email protected]> wrote: > Your description is imprecise. I guess you mean the answer is "B," > not "D" as you said. The following may be based on an improper > reading of your description. For example I'm assuming that each > letter maps to each int at most once. And each set of ints maps to > exactly one letter. > > Your method is on the right track, but you're missing the punch line. > > Read the input and use it to create a hash that maps letters to sets > of integers. As you read a pair n|X, add n to the set corresponding > to the letter X. > > After you've read all the data, make a pass over the first hash to > create a second hash that maps sets of integers to letters. > > Looking up sets in this will require O(k) where k is the length of the > integer set being looked up, i.e. the cost of computing the hash > function. > > Here is a little Perl program that does all this. Perl is not a great > language choice because the only way to hash the integer sets is to > convert to a string. Java and similar hash containers will let you do > the hashing without a type conversion, which is more efficient. > > use strict; > > our $ltr_to_iset = {}; > our $iset_to_ltr = {}; > > sub build_tables { > while (<>) { > my ($i, $ltr) = /(\d+)\|([a-z]+)/i; > push @{$ltr_to_iset->{$ltr}}, int($i); > } > while ( my ($ltr, $iset) = each(%$ltr_to_iset) ) { > $iset_to_ltr->{ join(",", sort { $a <=> $b } @$iset) } = $ltr; > } > } > > sub lookup { > my $iset = shift; > return $iset_to_ltr->{ join(",", sort { $a <=> $b } @$iset) }; > } > > sub main { > build_tables; > print lookup([2,1,4,3,5]) . "\n"; > print lookup([1,2,3,4,6]) . "\n"; > } > > main; > > genes-macbook-pro:Projects$ perl lu.pl < data.txt > A > B > > > On Nov 15, 9:53 am, vaibhav agrawal <[email protected]> wrote: > > Hello All, > > > > I have a problem, which needs to be solved for lesser time complexity. > Here > > it goes: > > > > There is a file having two columns: id and key as under: > > 1|A > > 2|A > > 3|A > > 4|A > > 5|A > > 1|B > > 2|B > > 3|B > > 4|B > > 6|B > > and so on... > > > > Now, we want to lookup a bunch of ids(constant 5) to get a key, that > means > > if we lookup on id as {2,1,4,3,6}, then we should get return key as 'D' > and > > so on... > > > > I am proposing a solution for this as under: > > Construct two hashes: > > First hash(based on above data):(Hash Key=>Hash Set) > > 1=>{A,B} > > 2=>{A,B} > > 3=>{A,B} > > 4=>{A,B} > > 5=>{A} > > 6=>{B} > > > > Second hash(based on above data):(Hash Key=>Hash Set) > > A=>{1,2,3,4,5} > > B=>{1,2,3,4,6} > > > > Now, for the given example ids as {2,1,4,3,6}, we will start looking up > > first element '2' into first hash, and got the list {A,B}, so the desired > > key could be either A or B. > > Now, let's consider A first using second hash, we got a list of ids > > {1,2,3,4,5}, now match these ids with the inputted bunch(2,1,4,3,6}, > which > > is not matching. Now consider B, which got list of ids as (1,2,3,4,6}, > which > > matches with the input and hence the answer is B. > > > > Is there any way in which it can be further optimized for speed? > > > > Thanks, > > Vaibhav > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
