Use Berkeleydb concept. On 15-Nov-2010 8:24 PM, "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.
