"Similar Destinations" challenge

I am currently solving the Similar Destinations challenge on HackerRank and am in need of some assistance in the code optimization/performance department. The task is to take a list of up to 1000 cities, each with up to 200 tags, and list the cities that have tags in common, starting with the groups of cities that have the most tags in common.

Sample Input

4
london:theatre,museums,monuments,food,parks,architecture,nightlife
amsterdam:museums,shopping,architecture,nightlife,cycling,food,walking
berlin:monuments,nightlife,food,architecture,city_trip
paris:shopping,food,monuments,architecture,gourmet,walking,museums
barcelona:architecture,shopping,beach,food,tapas,nightlife

Sample Output

amsterdam,paris:architecture,food,museums,shopping,walking
amsterdam,barcelona:architecture,food,nightlife,shopping
amsterdam,london:architecture,food,museums,nightlife
berlin,london:architecture,food,monuments,nightlife
london,paris:architecture,food,monuments,museums

I've managed to get my code working and returning the right results but it is failing at the final test case with a timeout error. The input is quite large so, that explains why the code is taking longer that expected.

I've attempted to think of different ways of pruning my (intermediate) result set but could not come up with something that I did not already have. I believe that the find function could use a bit more tweaking. I've tried my best to reduce the number of paths that the recursive function has to take but ultimately, it has to look at every destination in order to come up with the right results. However, I did terminate a recursive path if the number of tags in common between destinations were below the min limit. Is there anything else that I could do here? Would memoization help here?

```
static class Destination {
String dest;
List tags;

public Destination(String dest, List tags) {
this.dest = dest;
this.tags = tags;
}

@Override
public Stri

I've managed to solve the problem after a bit of selective profiling. It would seem that my initial hunch was right. The problem had less to do with the algorithm and more towards the data structures that I was using!

The culprit was in the find method. Specifically, when calling the retainAll method on two lists. I had forgotten the that it would take \$O(n^2)\$ time to iterate through two lists. That was why it was slow. I then changed list into a HashSet instead. As most of us know, a HashSet has an \$O(1)\$ time complexity when it comes to accessing its values. The retainAll method stayed but instead of finding the intersection between two lists, we now find the intersection between two sets instead! That managed to shave off a couple of seconds off of the total elapsed runtime and all the tests passed.

The find method now looks like this:

static void find(List commonKey, List commonTags, int index) {

    if (index >= allDest.size())
      return;

    if (commonTags.size()  tempKeys = new ArrayList(commonKey);
      List tags = allDest.get(i).tags;
      Set tempTagsSet1 = new HashSet(commonTags);
      Set tempTagsSet2 = new HashSet(tags);
      tempTagsSet1.retainAll(tempTagsSet2);
      List tempTags = new ArrayList(tempTagsSet1);

      if (tempTags.size() >= min)
        Collections.sort(tempTags);

      find(tempKeys, tempTags, i);

      if (tempTags.size() >= min) {
        if (!tagsTracker.contains(tempTags.toString())
            && !keysTracker.contains(tempKeys.toString())) {
          tagsTracker.add(tempTags.toString());
          keysTracker.add(tempKeys.toString());

          StringBuilder sb = new StringBuilder();
          for (int j = 0; j < tempKeys.size(); ++j) {
            sb.append(tempKeys.get(j));
            if (j + 1 < tempKeys.size())
              sb.append(",");
          }
          keysAndTags.put(sb.toString(), tempTags);
        }
      }
    }

 }

StackExchange Code Review Q#136467, answer score: 3