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.
