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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
