Hi Gene,
This works. Thanks for your suggestion.
Regards,
Vaibhav
On Tue, Nov 16, 2010 at 8:51 AM, Gene <gene.ress...@gmail.com> 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 <agrvaib...@gmail.com> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
