More efficient solution on coding task using Stream API?

Question

I recently had a technical interview and got small coding task on Stream API.
Let's consider next input:

public class Student {
    private String name;
    private List<String> subjects;
    //getters and setters
}

Student stud1 = new Student("John", Arrays.asList("Math", "Chemistry"));
Student stud2 = new Student("Peter", Arrays.asList("Math", "History"));
Student stud3 = new Student("Antony", Arrays.asList("Music", "History", "English"));

Stream<Student> studentStream = Stream.of(stud1, stud2, stud3);

The task is to find Students with unique subjects using Stream API.
So for the provided input expected result (ignoring order) is [John, Anthony].

I presented the solution using custom Collector:

Collector<Student, Map<String, Set<String>>, List<String>> studentsCollector = Collector.of(
        HashMap::new,
        (container, student) -> student.getSubjects().forEach(
                subject -> container
                        .computeIfAbsent(subject, s -> new HashSet<>())
                        .add(student.getName())),
        (c1, c2) -> c1,
        container -> container.entrySet().stream()
                .filter(e -> e.getValue().size() == 1)
                .map(e -> e.getValue().iterator().next())
                .distinct()
                .collect(Collectors.toList())
);
List<String> studentNames = studentStream.collect(studentsCollector);

But the solution was considered as not optimal/efficient.
Could you please share your ideas on more efficient solution for this task?

UPDATE: I got another opinion from one guy that he would use reducer (Stream.reduce() method). But I cannot understand how this could increase efficiency. What do you think?

Answer 1

Here is another one.

// using SimpleEntry from java.util.AbstractMap
Set<Student> list = new HashSet<>(studentStream
    .flatMap(student -> student.getSubjects().stream()
        .map(subject -> new SimpleEntry<>(subject, student)))
    .collect(Collectors.toMap(Entry::getKey, Entry::getValue, (l, r) -> Student.SENTINEL_VALUE)
    .values());
list.remove(Student.SENTINEL_VALUE);

^{(Intentionally using a sentinel value, more about that below.)}

The steps:

1. Set<Student> list = new HashSet<>(studentStream
   

   We're creating a HashSet from the Collection we're going to collect. That's because we want to get rid of the duplicate students (students with multiple unique subjects, in your case Antony).

2. .flatMap(student -> student.subjects()
       .map(subject -> new SimpleEntry(subject, student)))
   

   We are flatmapping each student's subjects into a stream, but first we map each element to a pair with as key the subject and as value the student. This is because we need to retain the association between the subject and the student. I'm using AbstractMap.SimpleEntry, but of course, you can use any implementation of a pair.

3. .collect(Collectors.toMap(Entry::getKey, Entry::getValue, (l, r) -> Student.SENTINEL_VALUE)
   

   We are collecting the values into a map, setting the subject as key and the student as value for the resulting map. We pass in a third argument (a BinaryOperator) to define what should happen if a key collision takes place. We cannot pass in null, so we use a sentinel value¹.
   At this point, we have inverted the relation student ↔ subject by mapping each subject to a student (or the SENTINEL_VALUE if a subject has multiple students).

4. .values());
   

   We take the values of the map, yielding the list of all students with a unique subject, plus the sentinel value.

5. list.remove(Student.SENTINEL_VALUE);
   

   The only thing left to do is getting rid of the sentinel value.

---

¹ We cannot use null in this situation. Most implementations of a Map make no distinction between a key mapped to null or the absence of that particular key. Or, more accurately, the merge method of HashMap actively removes a node when the remapping function returns null. If we want to avoid a sentinel value, then we must implement or own merge method, which could be implemented like something like this: return (!containsKey(key) ? super.merge(key, value, remappingFunction) : put(key, null));.

Answer 2

Another solution. Looks kind of similar to Eugene.

Stream.of(stud1, stud2, stud3, stud4)
    .flatMap( s -> s.getSubjects().stream().map( subj -> new AbstractMap.SimpleEntry<>( subj, s ) ) )
    .collect( Collectors.groupingBy(Map.Entry::getKey) )

    .entrySet().stream()
    .filter( e -> e.getValue().size() == 1 )
    .map( e -> e.getValue().get(0).getValue().getName() )
    .collect( Collectors.toSet() );