More efficient solution on coding task using Stream API?

  • A+
Category:Languages

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?

 


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

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 -> Pair.of(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 value1.
    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.


1 We cannot use null. Most implementations of a Map make no distinction between a key mapped to null or the absence of that particular key.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: