4
\$\begingroup\$

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<String> tags;

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

    @Override
    public String toString() {
      return dest;
    }
  }

  static List<Destination> allDest = new ArrayList<Destination>();
  static int min;
  static Set<String> keysTracker = new HashSet<String>();
  static Set<String> tagsTracker = new HashSet<String>();
  static Map<String, List<String>> keysAndTags = new HashMap<String, List<String>>();

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

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

    if (commonTags.size() < min)
      return;

    if (tagsTracker.contains(commonTags.toString()) || keysTracker.contains(commonKey.toString())) {
      return;
    }

    String dest = allDest.get(index).dest;
    commonKey.add(dest);

    for (int i = index + 1; i < allDest.size(); ++i) {

      List<String> tempKeys = new ArrayList<String>(commonKey);
      List<String> tags = allDest.get(i).tags;
      List<String> tempTags = new ArrayList<String>(commonTags);
      tempTags.retainAll(tags);

      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);
        }
      }
    }

  }

  public static void main(String[] args) {
    init();
    sort();
    calculate();
    answer();
  }

  static void init() {
    Scanner s = new Scanner(System.in);

    min = s.nextInt();
    s.nextLine();

    String line;
    while (s.hasNextLine()) {
      line = s.nextLine();
      if (line.isEmpty())
        break;
      String[] tokens = line.split(":");

      String dest = tokens[0];

      tokens = tokens[1].split(",");

      List<String> tags = new ArrayList<String>();
      for (int j = 0; j < tokens.length; ++j)
        tags.add(tokens[j]);
      Collections.sort(tags);

      Destination d = new Destination(dest, tags);
      allDest.add(d);
    }

    s.close();
  }

  static void sort() {
    Collections.sort(allDest, new Comparator<Destination>() {

      @Override
      public int compare(Destination d1, Destination d2) {
        return d1.dest.compareTo(d2.dest);
      }

    });
  }

  static void calculate() {
    for (int i = 0; i < allDest.size() - 1; ++i) {

      find(new ArrayList<String>(), new ArrayList<String>(allDest.get(i).tags), i);

    }
  }

  static void answer() {
    List<Map.Entry<String, List<String>>> mapInListForm = sortAnswer();

    for (Map.Entry<String, List<String>> entry : mapInListForm) {
      System.out.print(entry.getKey() + ":");
      for (int i = 0; i < entry.getValue().size(); ++i) {
        System.out.print(entry.getValue().get(i));
        if (i + 1 < entry.getValue().size())
          System.out.print(",");
      }
      System.out.println();
    }
  }

  static List<Map.Entry<String, List<String>>> sortAnswer() {
    List<Map.Entry<String, List<String>>> mapInListForm =
        new LinkedList<Map.Entry<String, List<String>>>(keysAndTags.entrySet());
    Collections.sort(mapInListForm, new Comparator<Map.Entry<String, List<String>>>() {
      public int compare(Map.Entry<String, List<String>> e1, Map.Entry<String, List<String>> e2) {

        if (e1.getValue().size() > e2.getValue().size()) {
          return -1;
        } else if (e1.getValue().size() < e2.getValue().size()) {
          return 1;
        }
        return e1.getKey().compareTo(e2.getKey());

      }
    });
    return mapInListForm;
  }

I have not been able to figure out a solution for this yet, unfortunately. Do let me know if any of you have trouble following my code (i.e. it's not up to par, it's messy, or etc.) and I'll do my best to correct it. I did try to structure my code as nicely as possible so that it was OK enough to follow thus, explains my lack of comments. Anyway, as for the problem at hand, I am leaning towards my incorrect usage of Java API that's slowing down the code. It's a stretch though. Still, I'll try looking into that before moving on to other ideas.

\$\endgroup\$
3
\$\begingroup\$

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<String> commonKey, List<String> commonTags, int index) {

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

    if (commonTags.size() < min)
      return;

    if (tagsTracker.contains(commonTags.toString()) || keysTracker.contains(commonKey.toString())) {
      return;
    }

    String dest = allDest.get(index).dest;
    commonKey.add(dest);

    for (int i = index + 1; i < allDest.size(); ++i) {

      List<String> tempKeys = new ArrayList<String>(commonKey);
      List<String> tags = allDest.get(i).tags;
      Set<String> tempTagsSet1 = new HashSet<String>(commonTags);
      Set<String> tempTagsSet2 = new HashSet<String>(tags);
      tempTagsSet1.retainAll(tempTagsSet2);
      List<String> tempTags = new ArrayList<String>(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);
        }
      }
    }

 }
\$\endgroup\$

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.