3
\$\begingroup\$

Here is the sample Students json am processing

{
"students": [
{
  "firstName": "Veena",
  "lastName": "Butteris",
  "email": "vbutteris@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-29",
    "2020-06-03",
    "2020-06-04",
    "2020-06-05"
  ]
},
{
  "firstName": "Edward",
  "lastName": "Nogueras",
  "email": "enogueras@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-26",
    "2020-05-30",
    "2020-05-31",
    "2020-06-04",
    "2020-06-05",
    "2020-06-09",
    "2020-06-10"
  ]
},
{
  "firstName": "Oterman",
  "lastName": "Chheang",
  "email": "ochheang@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-30",
    "2020-05-31",
    "2020-06-01",
    "2020-06-03",
    "2020-06-04",
    "2020-06-05",
    "2020-06-06",
    "2020-06-07",
    "2020-06-10"
  ]
},
{
  "firstName": "Jack",
  "lastName": "Eclarinal",
  "email": "jeclarinal@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-28",
    "2020-05-31",
    "2020-06-04",
    "2020-06-05"
  ]
},
{
  "firstName": "Cindy",
  "lastName": "Macallister",
  "email": "cmacallister@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-26",
    "2020-06-02",
    "2020-06-04",
    "2020-06-05",
    "2020-06-06",
    "2020-06-13"
  ]
},
{
  "firstName": "Cloe",
  "lastName": "Handrick",
  "email": "chandrick@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-29",
    "2020-06-01",
    "2020-06-04",
    "2020-06-05",
    "2020-06-09",
    "2020-06-10"
  ]
},
{
  "firstName": "Briane",
  "lastName": "Cutchall",
  "email": "bcutchall@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-29",
    "2020-05-30",
    "2020-05-31",
    "2020-06-03",
    "2020-06-04",
    "2020-06-05",
    "2020-06-14"
  ]
},
{
  "firstName": "Mark",
  "lastName": "Heyer",
  "email": "mheyer@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-23",
    "2020-05-24",
    "2020-05-25",
    "2020-05-26",
    "2020-05-29",
    "2020-05-31",
    "2020-06-01",
    "2020-06-04",
    "2020-06-05",
    "2020-06-06",
    "2020-06-10"
  ]
},
{
  "firstName": "Chau",
  "lastName": "Rundstrom",
  "email": "crundstrom@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-26",
    "2020-05-27",
    "2020-05-29",
    "2020-05-31",
    "2020-06-02",
    "2020-06-04",
    "2020-06-05"
  ]
},
{
  "firstName": "Francis",
  "lastName": "Haywood",
  "email": "fhaywood@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-26",
    "2020-05-27",
    "2020-05-29",
    "2020-06-03",
    "2020-06-04",
    "2020-06-05",
    "2020-06-09"
  ]
},
{
  "firstName": "Maria",
  "lastName": "Seiple",
  "email": "mseiple@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-23",
    "2020-05-24",
    "2020-05-25",
    "2020-06-01",
    "2020-06-04",
    "2020-06-05",
    "2020-06-06",
    "2020-06-08",
    "2020-06-09"
  ]
},
{
  "firstName": "Dan",
  "lastName": "Scavona",
  "email": "dscavona@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-29",
    "2020-06-04",
    "2020-06-05",
    "2020-06-07",
    "2020-06-09"
  ]
},
{
  "firstName": "Mark",
  "lastName": "Kuehler",
  "email": "mkuehler@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-06-01",
    "2020-06-04",
    "2020-06-05",
    "2020-06-06",
    "2020-06-09",
    "2020-06-10"
  ]
},
{
  "firstName": "Dang",
  "lastName": "Come",
  "email": "dcome@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-24",
    "2020-05-25",
    "2020-05-31",
    "2020-06-04",
    "2020-06-05",
    "2020-06-10",
    "2020-06-15"
  ]
},
{
  "firstName": "Neha",
  "lastName": "Torchia",
  "email": "ntorchia@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-06-03",
    "2020-06-06"
  ]
},
{
  "firstName": "Anita",
  "lastName": "Pujals",
  "email": "apujals@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-26",
    "2020-05-30",
    "2020-06-01",
    "2020-06-06"
  ]
},
{
  "firstName": "Lorry",
  "lastName": "Loots",
  "email": "lloots@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-26",
    "2020-06-01",
    "2020-06-08",
    "2020-06-12"
  ]
},
{
  "firstName": "Derik",
  "lastName": "Binner",
  "email": "dbinner@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-23",
    "2020-05-26",
    "2020-05-31",
    "2020-06-03",
    "2020-06-10"
  ]
},
{
  "firstName": "Lasha",
  "lastName": "Grybel",
  "email": "lgrybel@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-23",
    "2020-05-26",
    "2020-05-29",
    "2020-06-01",
    "2020-06-07",
    "2020-06-10"
  ]
},
{
  "firstName": "Bobby",
  "lastName": "Shekels",
  "email": "bshekels@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-23",
    "2020-05-26",
    "2020-05-29",
    "2020-05-30",
    "2020-06-03",
    "2020-06-06"
  ]
},
{
  "firstName": "Linc",
  "lastName": "Dorch",
  "email": "ldorch@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-27",
    "2020-06-01",
    "2020-06-09"
  ]
},
{
  "firstName": "Larsha",
  "lastName": "Terrey",
  "email": "lterrey@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-27",
    "2020-05-29",
    "2020-05-31",
    "2020-06-06"
  ]
},
{
  "firstName": "Dunk",
  "lastName": "Dettmann",
  "email": "ddettmann@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-23",
    "2020-05-27",
    "2020-05-31",
    "2020-06-01",
    "2020-06-09",
    "2020-06-13"
  ]
},
{
  "firstName": "Pearle",
  "lastName": "Laker",
  "email": "plaker@xyz.com",
  "country": "Wales",
  "availableDates": [
    "2020-05-27",
    "2020-05-29",
    "2020-05-31",
    "2020-06-03",
    "2020-06-06",
    "2020-06-08",
    "2020-06-12"
  ]
},
{
  "firstName": "Derek",
  "lastName": "Lessenberry",
  "email": "llessenberry@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-14",
    "2020-04-15",
    "2020-04-21",
    "2020-04-22",
    "2020-04-23",
    "2020-04-24",
    "2020-04-26",
    "2020-04-28",
    "2020-04-29",
    "2020-04-30",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Kobe",
  "lastName": "Carwile",
  "email": "lcarwile@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-21",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Judy",
  "lastName": "Vala",
  "email": "jvala@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-13",
    "2020-04-15",
    "2020-04-18",
    "2020-04-22",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-05-02",
    "2020-05-04",
    "2020-05-06"
  ]
},
{
  "firstName": "Rhian",
  "lastName": "Hirkaler",
  "email": "ghirkaler@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-15",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-05-01",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Shayna",
  "lastName": "Salsberg",
  "email": "msalsberg@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-14",
    "2020-04-15",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-05-06"
  ]
},
{
  "firstName": "Kate",
  "lastName": "Mataalii",
  "email": "smataalii@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-16",
    "2020-04-18",
    "2020-04-22",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-05-06"
  ]
},
{
  "firstName": "Zidan",
  "lastName": "Sefcovic",
  "email": "zsefcovic@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-13",
    "2020-04-15",
    "2020-04-23",
    "2020-04-24",
    "2020-04-26",
    "2020-04-28",
    "2020-04-29",
    "2020-04-30",
    "2020-05-02",
    "2020-05-04",
    "2020-05-06",
    "2020-05-07"
  ]
},
{
  "firstName": "Mario",
  "lastName": "Centner",
  "email": "tcentner@xyz.com",
  "country": "France",
  "availableDates": [
    "2020-04-13",
    "2020-04-16",
    "2020-04-18",
    "2020-04-21",
    "2020-04-23",
    "2020-04-24",
    "2020-04-25",
    "2020-04-27",
    "2020-04-28",
    "2020-04-29",
    "2020-04-30",
    "2020-05-04",
    "2020-05-06"
  ]
},
{
  "firstName": "Nayan",
  "lastName": "Mires",
  "email": "jmires@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-17",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-05-06"
  ]
},
{
  "firstName": "Hadiya",
  "lastName": "Delsoin",
  "email": "odelsoin@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-14",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-04-30",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Lacey",
  "lastName": "Bustos",
  "email": "sbustos@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-14",
    "2020-04-15",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-04-30",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Harrison",
  "lastName": "Bugett",
  "email": "sbugett@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-14",
    "2020-04-17",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-05-06"
  ]
},
{
  "firstName": "Connor",
  "lastName": "Schlembach",
  "email": "lschlembach@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-13",
    "2020-04-14",
    "2020-04-16",
    "2020-04-17",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-04-30",
    "2020-05-06"
  ]
},
{
  "firstName": "Clarissa",
  "lastName": "Stolebarger",
  "email": "cstolebarger@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-14",
    "2020-04-23",
    "2020-04-24",
    "2020-04-28",
    "2020-04-29",
    "2020-04-30",
    "2020-05-06"
  ]
},
{
  "firstName": "Phoebe",
  "lastName": "Mcrea",
  "email": "mmcrea@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-23",
    "2020-04-24",
    "2020-04-26",
    "2020-04-28",
    "2020-04-29",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Avni",
  "lastName": "Vanzant",
  "email": "kvanzant@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-15",
    "2020-04-26",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Fenella",
  "lastName": "Daughton",
  "email": "pdaughton@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-27",
    "2020-05-01",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Yaqub",
  "lastName": "Kokesh",
  "email": "mkokesh@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-14",
    "2020-04-15",
    "2020-05-01",
    "2020-05-06"
  ]
},
{
  "firstName": "Jeane",
  "lastName": "Haight",
  "email": "jhaight@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-13",
    "2020-04-14",
    "2020-04-15",
    "2020-04-18",
    "2020-05-06"
  ]
},
{
  "firstName": "Grant",
  "lastName": "Paleaae",
  "email": "cpaleaae@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-21",
    "2020-04-22",
    "2020-05-01",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Sanjeev",
  "lastName": "Schrupp",
  "email": "rschrupp@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-14",
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Holli",
  "lastName": "Bouley",
  "email": "kbouley@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-26",
    "2020-05-06",
    "2020-05-07"
  ]
},
{
  "firstName": "Preston",
  "lastName": "Dilbeck",
  "email": "ldilbeck@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-30",
    "2020-05-01",
    "2020-05-06"
  ]
},
{
  "firstName": "Ceri",
  "lastName": "Gruening",
  "email": "dgruening@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-05-02",
    "2020-05-06"
  ]
},
{
  "firstName": "Shannan",
  "lastName": "Purkiss",
  "email": "npurkiss@xyz.com",
  "country": "Germany",
  "availableDates": [
    "2020-04-15",
    "2020-04-21",
    "2020-04-22",
    "2020-05-06"
  ]
}
]
}

The above Json has list of Students with multiple available dates for training, I need to transform the json such a way that output Json should have a list of countries with maximum Students who are available on earliest adjacent dates and produces Json as

{
"countries": [
{
  "attendeeCount": 15,
  "attendees": [
    "llessenberry@xtz.com",
    "lcarwile@xtz.com",
    "jvala@xtz.com",
    "ghirkaler@xtz.com",
    "msalsberg@xtz.com",
    "smataalii@xtz.com",
    "zsefcovic@xtz.com",
    "tcentner@xtz.com",
    "jmires@xtz.com",
    "odelsoin@xtz.com",
    "sbustos@xtz.com",
    "sbugett@xtz.com",
    "lschlembach@xtz.com",
    "cstolebarger@xtz.com",
    "mmcrea@xtz.com"
  ],
  "name": "Germany",
  "startDate": "2020-04-23"
},
{
  "attendeeCount": 14,
  "attendees": [
    "vbutteris@xtz.com",
    "enogueras@xtz.com",
    "ochheang@xtz.com",
    "jeclarinal@xtz.com",
    "cmacallister@xtz.com",
    "chandrick@xtz.com",
    "bcutchall@xtz.com",
    "mheyer@xtz.com",
    "crundstrom@xtz.com",
    "fhaywood@xtz.com",
    "mseiple@xtz.com",
    "dscavona@xtz.com",
    "mkuehler@xtz.com",
    "dcome@xtz.com"
  ],
  "name": "Wales",
  "startDate": "2020-05-24"
}
]
}

Below are my DTO classes

public class Students {
    private List<Student> Students;
    //getter setter
}


public class Student {
    String firstName;
    String lastName;
    String email;
    String country;    
    List<String> availableDates;
}

public class CountryStudent {
    private Integer count;
    private List<String> attendees;
    private String name;
    private String startDate;
}

Below is the StudentsService class which fetcheds Students json data and transforms it.

public class StudentsService{

    public String processStudents(){
        Students students = StudentsPayloadGenerator.getPayload(); // fetches the Students json data 

        Map<String,Map<String,List<String>>> countryDatesStudents = new HashMap<>();

        List<Student> StudentsList = students.getStudents();                                           

        for (Student student : StudentsList){
            Map<String,Integer> consecutiveDates = getConsecutiveDatesForPartner(student);
            consecutiveDates.entrySet().forEach(computeStudentsAvailableOnConsecutiveDates(countryDatesStudents, student));
        }
        List<CountryStudent> countryStudents = new ArrayList<>();
        CountriesPayload countriesPayload = new CountriesPayload();
        countriesPayload.setCountries(countryStudents);


        countryDatesStudents.entrySet().forEach(countryDatesPartner-> {
            Map.Entry<String, List<String>> earliestAvailablePartner = countryDatesPartner.getValue().entrySet().stream().sorted((a, b) -> b.getValue().size() - a.getValue().size()).findFirst().get();
            CountryStudent countryAttendee = buildCountryPayload(countryDatesPartner.getKey(), earliestAvailablePartner);
            countryStudents.add(countryAttendee);
        });
        
        return getJson(countriesPayload);
    }
    
    private String getJson(CountriesPayload countriesPayload) {
        ObjectMapper objectMapper = new ObjectMapper();
        String countriesPayloadJson = null;
        try {
            countriesPayloadJson = objectMapper.writeValueAsString(countriesPayload);           
        } catch (JsonProcessingException e) {
            e.printStackTrace();
        }
        return countriesPayloadJson;
    }
    private CountryStudent buildCountryPayload(String country, Map.Entry<String, List<String>> attendeesEntry) {
        String adjacentDatePair = attendeesEntry.getKey();
        String earliestDate = adjacentDatePair.substring(0,adjacentDatePair.indexOf("_"));
        CountryStudent countryAttendee = new CountryStudent();
        countryAttendee.setName(country);
        countryAttendee.setAttendeeCount(attendeesEntry.getValue().size());
        countryAttendee.setAttendees(attendeesEntry.getValue());
        countryAttendee.setStartDate(earliestDate);
        return countryAttendee;
    }

    private Consumer<Map.Entry<String, Integer>> computeStudentsAvailableOnConsecutiveDates(Map<String, Map<String, List<String>>> countryDatesStudents, Student partner) {
        return entry -> {
            countryDatesStudents.computeIfAbsent(partner.getCountry(), v -> new TreeMap<String, List<String>>());
            Map<String, List<String>> datesStudents = countryDatesStudents.get(partner.getCountry());
            datesStudents.computeIfAbsent(entry.getKey(), v -> new ArrayList<>());
            datesStudents.get(entry.getKey()).add(partner.getEmail());

        };
    }

    private Map<String, Integer> getConsecutiveDatesForPartner(Student partner) {
        Map<String,Integer> consecutiveDates = new TreeMap<>();
        List<LocalDate> availableDates = partner.getAvailableDates().stream().map(this::convertToLocalDate).collect(Collectors.toList());
        Collections.sort(availableDates,(a,b) ->{
            if(a.isAfter(b)) return 1;
            else if(a.isBefore(b)) return -1;
            else return 0;
        });

        tupleIterator(availableDates, (date1, date2) -> {
            if(isConsecutive(date1,date2))
                consecutiveDates.put(date1+"_"+date2,1);
        });
        return consecutiveDates;
    }

    private LocalDate convertToLocalDate(String date){
        DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-d");
        return LocalDate.parse(date, formatter);
    }

    private boolean isConsecutive(LocalDate date1, LocalDate date2) {
        return DAYS.between(date1,date2) == 1;
    }


    public static <T> void tupleIterator(Iterable<T> iterable, BiConsumer<T, T> consumer) {
        Iterator<T> it = iterable.iterator();
        if(!it.hasNext()) return;
        T first = it.next();

        while(it.hasNext()) {
            T next = it.next();
            consumer.accept(first, next);
            first = next;
        }
    }
}

My code is not performing optimal if the input json is huge like millions of students, Am wondering if the above code can be optimized any further in terms of memory consumption and to achieve less run time, please provide your valuable feedback.

Improve this question
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Have you profiled the code to understand where the time is spent? \$\endgroup\$ – Emily L. Oct 7 '20 at 13:39
  • \$\begingroup\$ No I did not since its not in production yet and I dont have that much data available now to test, on a high level I feel it can be optimized further since nested and operating on whole initial data set, am wondering whether it can be done using parallel streams or any other Java 8 stream api features \$\endgroup\$ – RanPaul Oct 7 '20 at 14:11
  • 1
    \$\begingroup\$ Please embed the input and output from the links directly into your post. If they are too large, copy a representable piece of it and keep the links to full version. Nobody should be forced to open those links to understand your post. Links can rot and your post must be self-contained. \$\endgroup\$ – slepic Oct 7 '20 at 14:43
  • 1
    \$\begingroup\$ It is better to post the expected input and output in the question instead of via links. Then why the output json has start date 2017 but there is no such year in the input? Please provide a consistent example. \$\endgroup\$ – Marc Oct 7 '20 at 14:53
  • 1
    \$\begingroup\$ Well, if you have enough data to run it with to determine that is slow, you have enough data to profile where it's slow. \$\endgroup\$ – Emily L. Oct 8 '20 at 15:04
3
\$\begingroup\$

Nice implementation, it's already efficient but I noticed something that can be improved, find my suggestion below.

Time complexity

public String processStudents(){                                        
    //...
    // O(s) where s is the number of students 
    for (Student student : StudentsList){
        // O(d*log(d)) d is the number of dates of the student with most available dates
        Map<String,Integer> consecutiveDates = getConsecutiveDatesForPartner(student);
        // O(d)
        consecutiveDates.entrySet().forEach(computeStudentsAvailableOnConsecutiveDates(countryDatesStudents, student));
    }
    //...
    // O(c) c is number of countries
    countryDatesStudents.entrySet().forEach(countryDatesPartner-> {
        // O(D*log(D)) D is the number of all the dates of the students in a country
        Map.Entry<String, List<String>> earliestAvailablePartner = countryDatesPartner.getValue().entrySet().stream().sorted((a, b) -> b.getValue().size() - a.getValue().size()).findFirst().get();
        //...
    });
    return getJson(countriesPayload);
}

So the total complexity is approximately \$O(s*d*log(d) + c*D*log(D))\$. If the input JSON doesn't come with sorted dates then the fist factor cannot be improved.

The second factor can be improved by creating a map with adjacent dates in advance. For example:

  • 2019-01-01_2019-01-02 -> students
  • 2019-01-02_2019-01-03 -> students
  • ...
  • 2020-10-07_2020-10-08 (today) -> students

A method to create the map:

private Map<String,List<Student>> buildDateStudentsMap() {
    Map<String,List<Student>> datesStudents = new HashMap<>();
    LocalDate start = LocalDate.parse("2019-01-01");
    LocalDate end = LocalDate.now();
    while(start.isBefore(end)) {
        LocalDate nextDay = start.plusDays(1);
        datesStudents.put(start+"_"+nextDay, new ArrayList<>());
        start = nextDay;
    }
    return datesStudents;
}

Once the dates of the students are sorted, it's enough to add the student to the map.

The second improvement is parallelization. If the students are divided by country, the successive operations can run in parallel:

  1. Group the students by country. \$O(s)\$
  2. Create map with adjacent dates (as explained before) \$O(days)\$
  3. Fill map with students. \$O(s*d*log(d))\$
  4. Get the entry of the map with most students \$O(days)\$
  5. Generate the result

So the complexity would be \$O(s*d*log(d))\$ and the steps 2-5 can run in parallel. If you can get the dates in the input JSON sorted the complexity would basically be \$O(s)\$.

By running the two solution I got the following runtimes:

Initial solution: 209.4444 ms
Optimized solution: 61.7075 ms

Its more than three time faster which follows by the fact that there are are 3 countries in the example and it uses the precomputed map to avoid the second sort.

Optimized solution:

public List<CountryStudent> processStudents(List<Student> students) throws Exception{
    Map<String, List<Student>> countryStudents = students.stream()
                                                .collect(Collectors.groupingBy(Student::getCountry));
    return countryStudents.entrySet()
            .parallelStream()
            .map(k -> this.toCountryStudent(k.getKey(), k.getValue()) )
            .collect(Collectors.toList());
}

private CountryStudent toCountryStudent(String country, List<Student> students) {
    // Build map with adjacent dates
    Map<String,List<Student>> datesStudents = buildDateStudentsMap();
    
    // Fill map with students.
    for(Student s: students) {
        List<LocalDate> availableDates = s.getAvailableDates().stream()
                .map(this::convertToLocalDate).collect(Collectors.toList());
        // If availableDates are already sorted this can be removed
        Collections.sort(availableDates);
        tupleIterator(availableDates, (date1, date2) -> {
            if(isConsecutive(date1,date2))
                datesStudents.get(date1+"_"+date2).add(s);
        });
    }
    String dates = getMostPopularDates(datesStudents);
    String startDate = dates.substring(0,dates.indexOf("_"));
    return new CountryStudent(country,datesStudents.get(dates), startDate);
}

private String getMostPopularDates(Map<String,List<Student>> datesStudents) {
    int max=0;
    String key=null;
    // Get most popular adjacent dates. O(days) 
    for(Map.Entry<String,List<Student>> entry : datesStudents.entrySet()) {
        if(entry.getValue().size()>=max) {
            key = entry.getKey();
            max = entry.getValue().size();
        }
    }
    return key;
}

Notice how I removed the class Students and the JSON serialization/deserialization, motivations below.

Minor changes

  • The class Students is literally a container for the list of students with no additional methods, so it can be replaced by List<Student>. Same for CountriesPayload.
  • For testing and reusability is better to have a defined input and output, therefore I would remove the JSON serialization/deserialization in that method.
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Really appreciate for improving the run time, can you please share the implementation of getMostPopularDates() as well \$\endgroup\$ – RanPaul Oct 8 '20 at 15:30
  • \$\begingroup\$ @RanPaul glad I could help. That method it's nothing special, but I added it to the answer. \$\endgroup\$ – Marc Oct 8 '20 at 15:36
  • \$\begingroup\$ private String getMostPopularDates(Map<String,List<Student>> datesStudents) { Map<String,List<String>> map = new TreeMap<>(); datesStudents.entrySet().forEach(entry -> map.put(entry.getKey(),entry.getValue().stream().map(student -> student.getEmail()).collect(Collectors.toList()))); Map.Entry<String, List<String>> stringListEntry = map.entrySet().stream().sorted((a, b) -> b.getValue().size() - a.getValue().size()).findFirst().get(); return stringListEntry.getKey(); } \$\endgroup\$ – RanPaul Oct 10 '20 at 4:13
  • \$\begingroup\$ looks like your getMostPopularDates is not sorting and fetching the earliest date, I changed it as above to make it work \$\endgroup\$ – RanPaul Oct 10 '20 at 4:14
  • \$\begingroup\$ @RanPaul my bad, I used an HashMap in buildDateStudentsMap. Changing it to LinkedHashMap should do the trick. But good that you solved. \$\endgroup\$ – Marc Oct 10 '20 at 10:04
2
\$\begingroup\$

I noticed you wrote the following method:

private LocalDate convertToLocalDate(String date){
    DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-d");
    return LocalDate.parse(date, formatter);
}

You are instantianting a new DateTimeFormatter object everytime you calls this method and this is expensive, you could create one DateTimeFormatter static object:

private final static DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-d");

//you could directly invoke LocalDate.parse(date, formatter) in your code instead
//of this function
private LocalDate convertToLocalDate(String date){
    return LocalDate.parse(date, formatter);
}

Second thing is the the following code:

Collections.sort(availableDates,(a,b) ->{
    if(a.isAfter(b)) return 1;
    else if(a.isBefore(b)) return -1;
    else return 0;
});

If you have arrays of ascending dates like "2020-05-24", "2020-05-25", "2020-05-30" like in your json file for every element a.isAfter(b) will be always checked and will always return false and then a.isBefore(b) will be checked and return true ending the method. This is expensive, you could just the natural order of Collections.sort method like below:

Collections.sort(availableDates);

Or better, if you are sure the arrays are always already ascending ordered like your example, there is no need of using a sorting method.

Improve this answer
\$\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.