1
\$\begingroup\$

Write a method numInCommon that takes two Lists of integers as parameters and returns the number of unique integers that occur in both lists. Use one or more Sets as storage to help you solve this problem.

For example, if one list contains the values [3, 7, 3, -1, 2, 3, 7, 2, 15, 15] and the other list contains the values [-5, 15, 2, -1, 7, 15, 36], your method should return 4 (because the elements -1, 2, 7, and 15 occur in both lists).

I'd like feedback on how to make this code better. Are there better ways to do it? If I wasn't following the prompt (e.g. no set required), how could I find the common elements in the laziest, most efficient, best optimized, etc. way? Last but not least, does my code have any major bugs?

public static int numInCommon(List<Integer> list1, List<Integer> list2) {
        if (list1.isEmpty() || list2.isEmpty()) {
            return 0;
        } else {
            Set<Integer> setCommon = new HashSet<Integer>();
            for (Integer val : list1) {
                // add the values of list1 to the set
                setCommon.add(val);
            }
            int common = 0;
            for (Integer val : list2) {
                if (setCommon.contains(val)) {
                    // if a value in list2 exists in the set, increase common
                    common++;
                    setCommon.remove(val);
                }
            }
            return common;
        }
    }
\$\endgroup\$
2
\$\begingroup\$

If you want to ignore the requirement of using a Set, you could use Java 8 Streams to solve the problem.

public static int numInCommon(List<Integer> list1, List<Integer> list2) {
    return (int) list1.stream()
        .distinct()
        .filter(i -> list2.contains(i))
        .count()
}

This is a four-step process:

  • Get a stream of list1 (if you are not used to streams you can think of this as a loop, but in reality a call to .stream() by itself is not looping)
  • Use .distinct() to ignore duplicate elements (that is, if the first list contains a number multiple times, it only processes it once. The .distinct() part uses a Set internally to keep track of which elements it has seen.
  • Use .filter to only keep the numbers that also occur in the second list.
  • .count() to count the number of seen elements. This returns a long which is why the entire result is typecast to an int here.

It's not until you call .count() that the loop is actually performed, this is because .count() is a "terminal operation".

I would recommend to read more about Streams on Oracle's website

\$\endgroup\$
  • \$\begingroup\$ Would it make sense to create a set out of list2 in order to make list2.contains() work in constant time? \$\endgroup\$ – RoToRa Nov 27 '17 at 11:18
  • \$\begingroup\$ @RoToRa If the size of the list is sufficiently big, then yes. Theoretically, the time complexity would be lower, but practically keeping it as a list can be faster (at least for smaller lists) \$\endgroup\$ – Simon Forsberg Nov 27 '17 at 18:40
5
\$\begingroup\$

I personally would shorten this greatly:

public static int numInCommon(List<Integer> list1, List<Integer> list2){
    if(list1.isEmpty() || list2.isEmpty()){
        return 0;
    }

    Set<Integer> setCommon = new HashSet<>(list1);
    setCommon.retainAll(list2);
    return setCommon.size();
}

Returning 0 at the start is good, but no need for the else block on the If code. Next task is to calculate the common elements - putting list1 into the set removes duplicates and then retainAll removes anything that isn't in list2. This leaves everythin in list1 and list2 without duplicates. Returning the size() counts the elements.

For performance - I'm taking the major assumption that HashSet is one of the quickest ways to check if an item exists and handle removal.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why use if(list1.isEmpty() || list2.isEmpty()){ as a special case? The rest of the code handles that case already. \$\endgroup\$ – Simon Forsberg Nov 26 '17 at 15:15
2
\$\begingroup\$

Two small thing that should be considered (however this does strictly speaking contradict the given task):

Since the method doesn't actually need the features of List, I'd using Collections for the parameters.

Also the method doesn't care about the content type of the lists either, so you could replace the content type with a generic parameter:

public static int <T> numInCommon(Collection<T> list1, Collection<T> list2) {
  Set<T> set = new HashSet<>(list1);
  // ...
}

or if you don't need to refer to the type in the method, just:

public static int numInCommon(Collection<?> list1, Collection<?> list2) {
  // ...
}
\$\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.