Given finder : List of map, key : String, Val : String.

On receiving super map : a map which is super set of one or more map in a finder, find map from finder list which has contains maximum elements from super map.

For instance

Map { Name = Adam, Qualification = Engg, Job = Manager , Country =  US, City = Seattle}

list of sub maps :

   List [ submap1 {Name = Adam, Job = Manager }, 
      submap2 {Name = Adam, Country = Us, city - Seattle}
      submap3 {Name = Adam, Country = Us, city - Seattle, Job = 
        manager, Nickname = bobby} ] , size = 10000+

Result should be submap2. Is there a way I could utilize Tries/BST to pre-process list of subsets for faster look ups. Given that I have list of subsets at compile time and on receiving some uper set I need to find the best sub map. Any pointers would be of great help.


The simplest solution is to loop through the list of submaps. For each submap you count the number of matches. You keep the submab with the highest number of matches.

No need to use fancy data structures like tries unless you actually have to. (E.g. you have some specific performance issues.)

  • Number of sub maps is >10k and dont want to iterate 10 k. I was thinking about proprocessing sulists and build indexes for items in map for faster lookups. – sidss Oct 30 '16 at 5:08
  • @sidss: You have to iterate through all submaps at least once reagardless of which solution you choose. – JacquesB Oct 30 '16 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.